Skip to contentSkip to conversation

iommu-helper: Simplify find_next_zero_area

PATCH In review Akinobu Mita 5 participants 20 messages Oct 9, 2009 – Oct 17, 2009

Subsystems (8)
Networking Network drivers x86 USB +4 more subsystems
lore
Share & tools
lore
#0 lore raw

PATCH 1/8 iommu-helper: Simplify find_next_zero_area

Use find_next_bit instead of doing test_bit for each bit

Cc FUJITA Tomonori <[email protected]>
---
 lib/iommu-helper.c |    9 ++++-----
 1 files changed, 4 insertions(+), 5 deletions(-)
lib/iommu-helper.c +4 -5
index 75dbda0..dddbf22 100644
@@ -21,11 +21,10 @@ again:
 	end = index + nr;
 	if (end >= size)
 		return -1;
-	for (i = index; i < end; i++) {
-		if (test_bit(i, map)) {
-			start = i+1;
-			goto again;
-		}
+	i = find_next_bit(map, end, index);
+	if (i < end) {
+		start = i + 1;
+		goto again;
 	}
 	return index;
 }
Signature · 1 line
1.5.4.3
#1 lore raw

PATCH 2/8 bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

This introduces new bitmap functions:

bitmap_set: Set specified bit area
bitmap_clear: Clear specified bit area
bitmap_find_next_zero_area: Find free bit area

These are stolen from iommu helper.

I changed the return value of bitmap_find_next_zero_area if there is no zero area.

find_next_zero_area in iommu helper: returns -1
bitmap_find_next_zero_area: return >= bitmap size

Cc FUJITA Tomonori <[email protected]>
Cc "David S. Miller" <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
Cc Paul Mackerras <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc Greg Kroah-Hartman <[email protected]>
Cc Lothar Wassmann <[email protected]>
Cc Roland Dreier <[email protected]>
Cc Yevgeny Petrilin <[email protected]>
Cc Tony Luck <[email protected]>
Cc Fenghua Yu <[email protected]>
---
 include/linux/bitmap.h |   11 +++++++++++
 lib/bitmap.c           |   47 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+), 0 deletions(-)
include/linux/bitmap.h +11 -0
index 756d78b..daf8c48 100644
@@ -42,6 +42,9 @@
  * bitmap_empty(src, nbits)			Are all bits zero in *src?
  * bitmap_full(src, nbits)			Are all bits set in *src?
  * bitmap_weight(src, nbits)			Hamming Weight: number set bits
+ * bitmap_set(dst, pos, nbits)			Set specified bit area
+ * bitmap_clear(dst, pos, nbits)		Clear specified bit area
+ * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
  * bitmap_shift_right(dst, src, n, nbits)	*dst = *src >> n
  * bitmap_shift_left(dst, src, n, nbits)	*dst = *src << n
  * bitmap_remap(dst, src, old, new, nbits)	*dst = map(old, new)(src)
@@ -108,6 +111,14 @@ extern int __bitmap_subset(const unsigned long *bitmap1,
 			const unsigned long *bitmap2, int bits);
 extern int __bitmap_weight(const unsigned long *bitmap, int bits);
 
+extern void bitmap_set(unsigned long *map, int i, int len);
+extern void bitmap_clear(unsigned long *map, int start, int nr);
+extern unsigned long bitmap_find_next_zero_area(unsigned long *map,
+					 unsigned long size,
+					 unsigned long start,
+					 unsigned int nr,
+					 unsigned long align_mask);
+
 extern int bitmap_scnprintf(char *buf, unsigned int len,
 			const unsigned long *src, int nbits);
 extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
lib/bitmap.c +47 -0

53 lines not on this page · raw message

Signature · 1 line
1.5.4.3
#2 lore raw

PATCH 3/8 iommu-helper: Use bitmap library

Use bitmap library and kill some unused iommu helper functions.

Cc "David S. Miller" <[email protected]>
Cc Benjamin Herrenschmidt <[email protected]>
Cc Paul Mackerras <[email protected]>
Cc Thomas Gleixner <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc "H. Peter Anvin" <[email protected]>
Cc FUJITA Tomonori <[email protected]>
---
 arch/powerpc/kernel/iommu.c      |    4 +-
 arch/sparc/kernel/iommu.c        |    3 +-
 arch/x86/kernel/amd_iommu.c      |    4 +-
 arch/x86/kernel/pci-calgary_64.c |    6 ++--
 arch/x86/kernel/pci-gart_64.c    |    6 ++--
 include/linux/iommu-helper.h     |    3 --
 lib/iommu-helper.c               |   55 ++++---------------------------------
 7 files changed, 18 insertions(+), 63 deletions(-)
arch/powerpc/kernel/iommu.c +2 -2
index fd51578..5547ae6 100644
@@ -30,7 +30,7 @@
 #include <linux/spinlock.h>
 #include <linux/string.h>
 #include <linux/dma-mapping.h>
-#include <linux/bitops.h>
+#include <linux/bitmap.h>
 #include <linux/iommu-helper.h>
 #include <linux/crash_dump.h>
 #include <asm/io.h>
@@ -251,7 +251,7 @@ static void __iommu_free(struct iommu_table *tbl, dma_addr_t dma_addr,
 	}
 
 	ppc_md.tce_free(tbl, entry, npages);
-	iommu_area_free(tbl->it_map, free_entry, npages);
+	bitmap_clear(tbl->it_map, free_entry, npages);
 }
 
 static void iommu_free(struct iommu_table *tbl, dma_addr_t dma_addr,
arch/sparc/kernel/iommu.c +2 -1
index 7690cc2..5fad949 100644
@@ -11,6 +11,7 @@
 #include <linux/dma-mapping.h>
 #include <linux/errno.h>
 #include <linux/iommu-helper.h>
+#include <linux/bitmap.h>
 
 #ifdef CONFIG_PCI
 #include <linux/pci.h>
@@ -169,7 +170,7 @@ void iommu_range_free(struct iommu *iommu, dma_addr_t dma_addr, unsigned long np
 
 	entry = (dma_addr - iommu->page_table_map_base) >> IO_PAGE_SHIFT;
 
-	iommu_area_free(arena->map, entry, npages);
+	bitmap_clear(arena->map, entry, npages);
 }
 
 int iommu_table_init(struct iommu *iommu, int tsbsize,
arch/x86/kernel/amd_iommu.c +2 -2
index 98f230f..08b1d20 100644
@@ -19,7 +19,7 @@
 
 #include <linux/pci.h>
 #include <linux/gfp.h>
-#include <linux/bitops.h>
+#include <linux/bitmap.h>
 #include <linux/debugfs.h>
 #include <linux/scatterlist.h>
 #include <linux/dma-mapping.h>
@@ -959,7 +959,7 @@ static void dma_ops_free_addresses(struct dma_ops_domain *dom,
 
 	address = (address % APERTURE_RANGE_SIZE) >> PAGE_SHIFT;
 
-	iommu_area_free(range->bitmap, address, pages);
+	bitmap_clear(range->bitmap, address, pages);
 
 }
 
arch/x86/kernel/pci-calgary_64.c +3 -3
index 971a3be..c87bb20 100644
@@ -31,7 +31,7 @@
 #include <linux/string.h>
 #include <linux/crash_dump.h>
 #include <linux/dma-mapping.h>
-#include <linux/bitops.h>
+#include <linux/bitmap.h>
 #include <linux/pci_ids.h>
 #include <linux/pci.h>
 #include <linux/delay.h>
@@ -211,7 +211,7 @@ static void iommu_range_reserve(struct iommu_table *tbl,
 
 	spin_lock_irqsave(&tbl->it_lock, flags);
 
-	iommu_area_reserve(tbl->it_map, index, npages);
+	bitmap_set(tbl->it_map, index, npages);
 
 	spin_unlock_irqrestore(&tbl->it_lock, flags);
 }
@@ -305,7 +305,7 @@ static void iommu_free(struct iommu_table *tbl, dma_addr_t dma_addr,
 
 	spin_lock_irqsave(&tbl->it_lock, flags);
 
-	iommu_area_free(tbl->it_map, entry, npages);
+	bitmap_clear(tbl->it_map, entry, npages);
 
 	spin_unlock_irqrestore(&tbl->it_lock, flags);
 }
arch/x86/kernel/pci-gart_64.c +3 -3
index 98a827e..3010cd1 100644
@@ -22,7 +22,7 @@
 #include <linux/module.h>
 #include <linux/topology.h>
 #include <linux/interrupt.h>
-#include <linux/bitops.h>
+#include <linux/bitmap.h>
 #include <linux/kdebug.h>
 #include <linux/scatterlist.h>
 #include <linux/iommu-helper.h>
@@ -122,7 +122,7 @@ static void free_iommu(unsigned long offset, int size)
 	unsigned long flags;
 
 	spin_lock_irqsave(&iommu_bitmap_lock, flags);
-	iommu_area_free(iommu_gart_bitmap, offset, size);
+	bitmap_clear(iommu_gart_bitmap, offset, size);
 	if (offset >= next_bit)
 		next_bit = offset + size;
 	spin_unlock_irqrestore(&iommu_bitmap_lock, flags);
@@ -781,7 +781,7 @@ void __init gart_iommu_init(void)
 	 * Out of IOMMU space handling.
 	 * Reserve some invalid pages at the beginning of the GART.
 	 */
-	iommu_area_reserve(iommu_gart_bitmap, 0, EMERGENCY_PAGES);
+	bitmap_set(iommu_gart_bitmap, 0, EMERGENCY_PAGES);
 
 	agp_memory_reserved = iommu_size;
 	printk(KERN_INFO
include/linux/iommu-helper.h +0 -3
index 3b068e5..64d1b63 100644
@@ -14,14 +14,11 @@ static inline unsigned long iommu_device_max_index(unsigned long size,
 extern int iommu_is_span_boundary(unsigned int index, unsigned int nr,
 				  unsigned long shift,
 				  unsigned long boundary_size);
-extern void iommu_area_reserve(unsigned long *map, unsigned long i, int len);
 extern unsigned long iommu_area_alloc(unsigned long *map, unsigned long size,
 				      unsigned long start, unsigned int nr,
 				      unsigned long shift,
 				      unsigned long boundary_size,
 				      unsigned long align_mask);
-extern void iommu_area_free(unsigned long *map, unsigned long start,
-			    unsigned int nr);
 
 extern unsigned long iommu_num_pages(unsigned long addr, unsigned long len,
 				     unsigned long io_page_size);
lib/iommu-helper.c +6 -49

76 lines not on this page · raw message

Signature · 1 line
1.5.4.3
#3 lore raw

PATCH 4/8 isp1362-hcd: Use bitmap_find_next_zero_area

Cc Greg Kroah-Hartman <[email protected]>
Cc Lothar Wassmann <[email protected]>
---
 drivers/usb/host/isp1362-hcd.c |   26 ++++++--------------------
 1 files changed, 6 insertions(+), 20 deletions(-)
drivers/usb/host/isp1362-hcd.c +6 -20
index e35d828..f9221fe 100644
@@ -80,7 +80,7 @@
 #include <linux/platform_device.h>
 #include <linux/pm.h>
 #include <linux/io.h>
-#include <linux/bitops.h>
+#include <linux/bitmap.h>
 
 #include <asm/irq.h>
 #include <asm/system.h>
@@ -190,10 +190,8 @@ static int claim_ptd_buffers(struct isp1362_ep_queue *epq,
 			     struct isp1362_ep *ep, u16 len)
 {
 	int ptd_offset = -EINVAL;
-	int index;
 	int num_ptds = ((len + PTD_HEADER_SIZE - 1) / epq->blk_size) + 1;
-	int found = -1;
-	int last = -1;
+	int found;
 
 	BUG_ON(len > epq->buf_size);
 
@@ -205,20 +203,9 @@ static int claim_ptd_buffers(struct isp1362_ep_queue *epq,
 		    epq->name, len, epq->blk_size, num_ptds, epq->buf_map, epq->skip_map);
 	BUG_ON(ep->num_ptds != 0);
 
-	for (index = 0; index <= epq->buf_count - num_ptds; index++) {
-		if (test_bit(index, &epq->buf_map))
-			continue;
-		found = index;
-		for (last = index + 1; last < index + num_ptds; last++) {
-			if (test_bit(last, &epq->buf_map)) {
-				found = -1;
-				break;
-			}
-		}
-		if (found >= 0)
-			break;
-	}
-	if (found < 0)
+	found = bitmap_find_next_zero_area(&epq->buf_map, epq->buf_count, 0,
+						num_ptds, 0);
+	if (found >= epq->buf_count)
 		return -EOVERFLOW;
 
 	DBG(1, "%s: Found %d PTDs[%d] for %d/%d byte\n", __func__,
@@ -230,8 +217,7 @@ static int claim_ptd_buffers(struct isp1362_ep_queue *epq,
 	epq->buf_avail -= num_ptds;
 	BUG_ON(epq->buf_avail > epq->buf_count);
 	ep->ptd_index = found;
-	for (index = found; index < last; index++)
-		__set_bit(index, &epq->buf_map);
+	bitmap_set(&epq->buf_map, found, num_ptds);
 	DBG(1, "%s: Done %s PTD[%d] $%04x, avail %d count %d claimed %d %08lx:%08lx\n",
 	    __func__, epq->name, ep->ptd_index, ep->ptd_offset,
 	    epq->buf_avail, epq->buf_count, num_ptds, epq->buf_map, epq->skip_map);
Signature · 1 line
1.5.4.3
#4 lore raw

PATCH 5/8 mlx4: Use bitmap_find_next_zero_area

Cc Roland Dreier <[email protected]>
Cc Yevgeny Petrilin <[email protected]>
---
 drivers/net/mlx4/alloc.c |   37 ++++---------------------------------
 1 files changed, 4 insertions(+), 33 deletions(-)
drivers/net/mlx4/alloc.c +4 -33
index ad95d5f..8c85156 100644
@@ -72,35 +72,6 @@ void mlx4_bitmap_free(struct mlx4_bitmap *bitmap, u32 obj)
 	mlx4_bitmap_free_range(bitmap, obj, 1);
 }
 
-static unsigned long find_aligned_range(unsigned long *bitmap,
-					u32 start, u32 nbits,
-					int len, int align)
-{
-	unsigned long end, i;
-
-again:
-	start = ALIGN(start, align);
-
-	while ((start < nbits) && test_bit(start, bitmap))
-		start += align;
-
-	if (start >= nbits)
-		return -1;
-
-	end = start+len;
-	if (end > nbits)
-		return -1;
-
-	for (i = start + 1; i < end; i++) {
-		if (test_bit(i, bitmap)) {
-			start = i + 1;
-			goto again;
-		}
-	}
-
-	return start;
-}
-
 u32 mlx4_bitmap_alloc_range(struct mlx4_bitmap *bitmap, int cnt, int align)
 {
 	u32 obj, i;
@@ -110,13 +81,13 @@ u32 mlx4_bitmap_alloc_range(struct mlx4_bitmap *bitmap, int cnt, int align)
 
 	spin_lock(&bitmap->lock);
 
-	obj = find_aligned_range(bitmap->table, bitmap->last,
-				 bitmap->max, cnt, align);
+	obj = bitmap_find_next_zero_area(bitmap->table, bitmap->max,
+				bitmap->last, cnt, align - 1);
 	if (obj >= bitmap->max) {
 		bitmap->top = (bitmap->top + bitmap->max + bitmap->reserved_top)
 				& bitmap->mask;
-		obj = find_aligned_range(bitmap->table, 0, bitmap->max,
-					 cnt, align);
+		obj = bitmap_find_next_zero_area(bitmap->table, bitmap->max,
+						0, cnt, align - 1);
 	}
 
 	if (obj < bitmap->max) {
Signature · 1 line
1.5.4.3
#5 lore raw

PATCH 6/8 sparc: Use bitmap_find_next_zero_area

---
 arch/sparc/kernel/ldc.c |   16 ++++------------
 arch/sparc/mm/sun4c.c   |   17 +++++------------
 2 files changed, 9 insertions(+), 24 deletions(-)
arch/sparc/kernel/ldc.c +4 -12
index adf5f27..aa27d26 100644
@@ -14,6 +14,7 @@
 #include <linux/interrupt.h>
 #include <linux/list.h>
 #include <linux/init.h>
+#include <linux/bitmap.h>
 
 #include <asm/hypervisor.h>
 #include <asm/iommu.h>
@@ -1875,7 +1876,7 @@ EXPORT_SYMBOL(ldc_read);
 static long arena_alloc(struct ldc_iommu *iommu, unsigned long npages)
 {
 	struct iommu_arena *arena = &iommu->arena;
-	unsigned long n, i, start, end, limit;
+	unsigned long n, start, end, limit;
 	int pass;
 
 	limit = arena->limit;
@@ -1883,7 +1884,7 @@ static long arena_alloc(struct ldc_iommu *iommu, unsigned long npages)
 	pass = 0;
 
 again:
-	n = find_next_zero_bit(arena->map, limit, start);
+	n = bitmap_find_next_zero_area(arena->map, limit, start, npages, 0);
 	end = n + npages;
 	if (unlikely(end >= limit)) {
 		if (likely(pass < 1)) {
@@ -1896,16 +1897,7 @@ again:
 			return -1;
 		}
 	}
-
-	for (i = n; i < end; i++) {
-		if (test_bit(i, arena->map)) {
-			start = i + 1;
-			goto again;
-		}
-	}
-
-	for (i = n; i < end; i++)
-		__set_bit(i, arena->map);
+	bitmap_set(arena->map, n, npages);
 
 	arena->hint = end;
 
arch/sparc/mm/sun4c.c +5 -12
index 2ffacd6..a89baf0 100644
@@ -17,6 +17,7 @@
 #include <linux/fs.h>
 #include <linux/seq_file.h>
 #include <linux/scatterlist.h>
+#include <linux/bitmap.h>
 
 #include <asm/sections.h>
 #include <asm/page.h>
@@ -1021,20 +1022,12 @@ static char *sun4c_lockarea(char *vaddr, unsigned long size)
 	npages = (((unsigned long)vaddr & ~PAGE_MASK) +
 		  size + (PAGE_SIZE-1)) >> PAGE_SHIFT;
 
-	scan = 0;
 	local_irq_save(flags);
-	for (;;) {
-		scan = find_next_zero_bit(sun4c_iobuffer_map,
-					  iobuffer_map_size, scan);
-		if ((base = scan) + npages > iobuffer_map_size) goto abend;
-		for (;;) {
-			if (scan >= base + npages) goto found;
-			if (test_bit(scan, sun4c_iobuffer_map)) break;
-			scan++;
-		}
-	}
+	base = bitmap_find_next_zero_area(sun4c_iobuffer_map, iobuffer_map_size,
+						0, npages, 0);
+	if (base >= iobuffer_map_size)
+		goto abend;
 
-found:
 	high = ((base + npages) << PAGE_SHIFT) + sun4c_iobuffer_start;
 	high = SUN4C_REAL_PGDIR_ALIGN(high);
 	while (high > sun4c_iobuffer_high) {
Signature · 1 line
1.5.4.3
#6 lore raw

PATCH 7/8 ia64: Use bitmap_find_next_zero_area

---
 arch/ia64/sn/pci/tioca_provider.c |   19 +++++--------------
 1 files changed, 5 insertions(+), 14 deletions(-)
arch/ia64/sn/pci/tioca_provider.c +5 -14
index 35b2a27..efb4545 100644
@@ -9,6 +9,7 @@
 #include <linux/types.h>
 #include <linux/interrupt.h>
 #include <linux/pci.h>
+#include <linux/bitmap.h>
 #include <asm/sn/sn_sal.h>
 #include <asm/sn/addrs.h>
 #include <asm/sn/io.h>
@@ -369,7 +370,7 @@ tioca_dma_d48(struct pci_dev *pdev, u64 paddr)
 static dma_addr_t
 tioca_dma_mapped(struct pci_dev *pdev, unsigned long paddr, size_t req_size)
 {
-	int i, ps, ps_shift, entry, entries, mapsize, last_entry;
+	int ps, ps_shift, entry, entries, mapsize;
 	u64 xio_addr, end_xio_addr;
 	struct tioca_common *tioca_common;
 	struct tioca_kernel *tioca_kern;
@@ -410,23 +411,13 @@ tioca_dma_mapped(struct pci_dev *pdev, unsigned long paddr, size_t req_size)
 	map = tioca_kern->ca_pcigart_pagemap;
 	mapsize = tioca_kern->ca_pcigart_entries;
 
-	entry = find_first_zero_bit(map, mapsize);
-	while (entry < mapsize) {
-		last_entry = find_next_bit(map, mapsize, entry);
-
-		if (last_entry - entry >= entries)
-			break;
-
-		entry = find_next_zero_bit(map, mapsize, last_entry);
-	}
-
-	if (entry > mapsize) {
+	entry = bitmap_find_next_zero_area(map, mapsize, 0, entries, 0);
+	if (entry >= mapsize) {
 		kfree(ca_dmamap);
 		goto map_return;
 	}
 
-	for (i = 0; i < entries; i++)
-		set_bit(entry + i, map);
+	bitmap_set(map, entry, entries);
 
 	bus_addr = tioca_kern->ca_pciap_base + (entry * ps);
 
Signature · 1 line
1.5.4.3
#7 lore raw

PATCH 8/8 genalloc: Use bitmap_find_next_zero_area

---
 lib/genalloc.c |   33 ++++++++++++---------------------
 1 files changed, 12 insertions(+), 21 deletions(-)
lib/genalloc.c +12 -21
index eed2bdb..e67f974 100644
@@ -11,6 +11,7 @@
  */
 
 #include <linux/module.h>
+#include <linux/bitmap.h>
 #include <linux/genalloc.h>
 
 
@@ -114,7 +115,7 @@ unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
 	struct gen_pool_chunk *chunk;
 	unsigned long addr, flags;
 	int order = pool->min_alloc_order;
-	int nbits, bit, start_bit, end_bit;
+	int nbits, start_bit, end_bit;
 
 	if (size == 0)
 		return 0;
@@ -129,29 +130,19 @@ unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
 		end_bit -= nbits + 1;
 
 		spin_lock_irqsave(&chunk->lock, flags);
-		bit = -1;
-		while (bit + 1 < end_bit) {
-			bit = find_next_zero_bit(chunk->bits, end_bit, bit + 1);
-			if (bit >= end_bit)
-				break;
-
-			start_bit = bit;
-			if (nbits > 1) {
-				bit = find_next_bit(chunk->bits, bit + nbits,
-							bit + 1);
-				if (bit - start_bit < nbits)
-					continue;
-			}
-
-			addr = chunk->start_addr +
-					    ((unsigned long)start_bit << order);
-			while (nbits--)
-				__set_bit(start_bit++, chunk->bits);
+		start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit, 0,
+						nbits, 0);
+		if (start_bit >= end_bit) {
 			spin_unlock_irqrestore(&chunk->lock, flags);
-			read_unlock(&pool->lock);
-			return addr;
+			continue;
 		}
+
+		addr = chunk->start_addr + ((unsigned long)start_bit << order);
+
+		bitmap_set(chunk->bits, start_bit, nbits);
 		spin_unlock_irqrestore(&chunk->lock, flags);
+		read_unlock(&pool->lock);
+		return addr;
 	}
 	read_unlock(&pool->lock);
 	return 0;
Signature · 1 line
1.5.4.3
maintainer
#9 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

In reply to Akinobu Mita
Quoted 6 lines · On Fri, 9 Oct 2009 17:29:15 +0900 Akinobu Mita <[email protected]> wrote:

This introduces new bitmap functions:

bitmap_set: Set specified bit area
bitmap_clear: Clear specified bit area bitmap_find_next_zero_area: Find free bit area

Quoted 7 lines

These are stolen from iommu helper.

I changed the return value of bitmap_find_next_zero_area if there is no zero area.

find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size

I'll plan to merge this patch into 2.6.32 so we can trickle all the other patches into subsystems in an orderly fashion.

lib/bitmap.c int __bitmap_weight(const unsigned long *bitmap, int bits) · line 282

Quoted 9 lines
lib/bitmap.c +9 -0
+void bitmap_set(unsigned long *map, int i, int len)
+{
+	int end = i + len;
+
+	while (i < end) {
+		__set_bit(i, map);
+		i++;
+	}
+}

This is really inefficient, isn't it? It's a pretty trivial matter to romp through memory 32 or 64 bits at a time.

lib/bitmap.c int __bitmap_weight(const unsigned long *bitmap, int bits) · line 294

Quoted 12 lines
lib/bitmap.c +12 -0
+EXPORT_SYMBOL(bitmap_set);
+
+void bitmap_clear(unsigned long *map, int start, int nr)
+{
+	int end = start + nr;
+
+	while (start < end) {
+		__clear_bit(start, map);
+		start++;
+	}
+}
+EXPORT_SYMBOL(bitmap_clear);

Ditto.

Quoted 14 lines
lib/bitmap.c +14 -0
+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 = (index + align_mask) & ~align_mask;
+
+	end = index + nr;

lib/bitmap.c int __bitmap_weight(const unsigned long *bitmap, int bits) · line 319

Quoted 10 lines
lib/bitmap.c +10 -0
+	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);

This needs documentation, please. It appears that size' is the size of the bitmap and nr' is the number of zeroed bits we're looking for, but an inattentive programmer could get those reversed.

Also the semantics of align_mask' could benefit from spelling out. Is the alignment with respect to memory boundaries or with respect to map' or with respect to map+start or what?

And why does align_mask exist at all? I was a bit surprised to see it there. In which scenarios will it be non-zero?

#10 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

Quoted 11 lines · Andrew Morton
Quoted 8 lines · On Fri, 9 Oct 2009 17:29:15 +0900 Akinobu Mita <[email protected]> wrote:

This introduces new bitmap functions:

bitmap_set: Set specified bit area
bitmap_clear: Clear specified bit area bitmap_find_next_zero_area: Find free bit area

These are stolen from iommu helper.

Quoted 8 lines
Quoted 5 lines

I changed the return value of bitmap_find_next_zero_area if there is no zero area.

find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size

I'll plan to merge this patch into 2.6.32 so we can trickle all the other patches into subsystems in an orderly fashion.

Sounds good.

Quoted 4 lines
Quoted 4 lines
lib/bitmap.c +4 -0
+void bitmap_set(unsigned long *map, int i, int len)
+{
+	int end = i + len;
+
Quoted 8 lines

lib/bitmap.c int __bitmap_weight(const unsigned long *bitmap, int bits) · line 282

Quoted 5 lines
lib/bitmap.c +5 -0
+	while (i < end) {
+		__set_bit(i, map);
+		i++;
+	}
+}

This is really inefficient, isn't it? It's a pretty trivial matter to romp through memory 32 or 64 bits at a time.

OK. I'll do

Quoted 29 lines
Quoted 14 lines
lib/bitmap.c +14 -0
+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 = (index + align_mask) & ~align_mask;
+
+	end = index + nr;

lib/bitmap.c int __bitmap_weight(const unsigned long *bitmap, int bits) · line 319

Quoted 10 lines
lib/bitmap.c +10 -0
+	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);

This needs documentation, please. It appears that size' is the size of the bitmap and nr' is the number of zeroed bits we're looking for, but an inattentive programmer could get those reversed.

Quoted 3 lines

Also the semantics of align_mask' could benefit from spelling out. Is the alignment with respect to memory boundaries or with respect to map' or with respect to map+start or what?

OK. I will document it.

And I plan to change bitmap_find_next_zero_area() to take the alignment instead of an align_mask as Roland said.

Quoted 2 lines

And why does align_mask exist at all? I was a bit surprised to see it there. In which scenarios will it be non-zero?

Because the users of iommu-helper and mlx4 need the alignment requirement for the zero area.

arch/powerpc/kernel/iommu.c
arch/x86/kernel/amd_iommu.c
arch/x86/kernel/pci-gart_64.c
drivers/net/mlx4/alloc.c

#11 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper. Some zero area cannot be found by this bug.

Subject: [PATCH] Fix off-by-one error in find_next_zero_area

---
 lib/iommu-helper.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
lib/iommu-helper.c +1 -1
index 75dbda0..afc58bc 100644
@@ -19,7 +19,7 @@ again:
 	index = (index + align_mask) & ~align_mask;
 
 	end = index + nr;
-	if (end >= size)
+	if (end > size)
 		return -1;
 	for (i = index; i < end; i++) {
 		if (test_bit(i, map)) {
Signature · 1 line
1.5.4.3
#12 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

Quoted 2 lines · Akinobu Mita

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper.

Why not merge those tests into the kernel as a configurable boot-time self-test?

cheers

#13 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

Quoted 6 lines · Michael Ellerman
Quoted 2 lines · Akinobu Mita

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper.

Why not merge those tests into the kernel as a configurable boot-time self-test?

I send the test program that I used. Obviously it needs better diagnostic messages and cleanup to be added into kernel tests.

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>

#if 1 /* Copy and paste from kernel source */

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(long) * BITS_PER_BYTE)

#define BIT_WORD(nr) ((nr) / BITS_PER_LONG)
#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)

#define BITMAP_LAST_WORD_MASK(nbits)                                    \
(                                                                       \
        ((nbits) % BITS_PER_LONG) ?                                     \
                (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \

)

#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))

void bitmap_set(unsigned long *map, int start, int nr)

{
	unsigned long *p = map + BIT_WORD(start);
	const int size = start + nr;
	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);

	while (nr - bits_to_set >= 0) {
		*p |= mask_to_set;
		nr -= bits_to_set;
		bits_to_set = BITS_PER_LONG;
		mask_to_set = ~0UL;
		p++;
	}
	if (nr) {
		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
		*p |= mask_to_set;
	}
}

void bitmap_clear(unsigned long *map, int start, int nr)

{
	unsigned long *p = map + BIT_WORD(start);
	const int size = start + nr;
	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);

	while (nr - bits_to_clear >= 0) {
		*p &= ~mask_to_clear;
		nr -= bits_to_clear;
		bits_to_clear = BITS_PER_LONG;
		mask_to_clear = ~0UL;
		p++;
	}
	if (nr) {
		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
		*p &= ~mask_to_clear;
	}
}

static unsigned long __ffs(unsigned long word)

{
	int num = 0;

	if ((word & 0xffff) = 0) {
		num += 16;
		word >>= 16;
	}
	if ((word & 0xff) = 0) {
		num += 8;
		word >>= 8;
	}
	if ((word & 0xf) = 0) {
		num += 4;
		word >>= 4;
	}
	if ((word & 0x3) = 0) {
		num += 2;
		word >>= 2;
	}
	if ((word & 0x1) = 0)
		num += 1;
	return num;
}

unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
unsigned long offset)

{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG-1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset %= BITS_PER_LONG;
	if (offset) {
		tmp = *(p++);
		tmp &= (~0UL << offset);
		if (size < BITS_PER_LONG)
			goto found_first;
		if (tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}
	while (size & ~(BITS_PER_LONG-1)) {
		if ((tmp = *(p++)))
			goto found_middle;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = *p;

found_first:

	tmp &= (~0UL >> (BITS_PER_LONG - size));
	if (tmp = 0UL)		/* Are any bits set? */
		return result + size;	/* Nope. */
found_middle:
	return result + __ffs(tmp);
}

#define ffz(x) __ffs(~(x))

unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
unsigned long offset)

{
	const unsigned long *p = addr + BITOP_WORD(offset);
	unsigned long result = offset & ~(BITS_PER_LONG-1);
	unsigned long tmp;

	if (offset >= size)
		return size;
	size -= result;
	offset %= BITS_PER_LONG;
	if (offset) {
		tmp = *(p++);
		tmp |= ~0UL >> (BITS_PER_LONG - offset);
		if (size < BITS_PER_LONG)
			goto found_first;
		if (~tmp)
			goto found_middle;
		size -= BITS_PER_LONG;
		result += BITS_PER_LONG;
	}
	while (size & ~(BITS_PER_LONG-1)) {
		if (~(tmp = *(p++)))
			goto found_middle;
		result += BITS_PER_LONG;
		size -= BITS_PER_LONG;
	}
	if (!size)
		return result;
	tmp = *p;

found_first:

	tmp |= ~0UL << size;
	if (tmp = ~0UL)	/* Are any bits zero? */
		return result + size;	/* Nope. */
found_middle:
	return result + ffz(tmp);
}

#define __ALIGN_MASK(x,mask) (((x)+(mask))&~(mask))

static inline int test_bit(int nr, const volatile unsigned long *addr)

{
	return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1)));
}

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;

#ifdef ORIGINAL
if (end >= size)
#else
if (end > size)

#endif
		return end;
#ifdef ORIGINAL
	for (i = index; i < end; i++) {
		if (test_bit(i, map)) {
			start = i+1;
			goto again;
		}
	}
#else
	i = find_next_bit(map, end, index);
	if (i < end) {
		start = i + 1;
		goto again;
	}
#endif
	return index;
}

#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
#define BITS_TO_LONGS(nr) DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
#define DECLARE_BITMAP(name,bits) unsigned long name[BITS_TO_LONGS(bits)]

#endif /* Copy and paste from kernel source */

static DECLARE_BITMAP(bitmap, 1000);
static DECLARE_BITMAP(empty, 1000);
static DECLARE_BITMAP(full, 1000);

static void bitmap_dump(unsigned long *bitmap, int size)

{
	int i;

	for (i = 0; i < size; i++) {
		if (test_bit(i, bitmap))
			printf("1 ");
		else
			printf("0 ");
		if (i % 10 = 9)
			printf("\n");
	}
	printf("\n");
}

static int test1(int size)
{

	int start = random() % size;
	int nr = random() % (size - start);

	memset(bitmap, 0x00, BITS_TO_LONGS(size) * sizeof(unsigned long));

	bitmap_set(bitmap, start, nr);
	bitmap_clear(bitmap, start, nr);

	if (memcmp(empty, bitmap, BITS_TO_LONGS(size) * sizeof(unsigned long)))
		goto error;

	return 0;
error:
	bitmap_dump(bitmap, size);
	return 1;
}

int test2(int size)

{
	int start = random() % size;
	int nr = random() % (size - start);

	memset(bitmap, 0xff, BITS_TO_LONGS(size) * sizeof(unsigned long));

	bitmap_clear(bitmap, start, nr);
	bitmap_set(bitmap, start, nr);

	if (memcmp(full, bitmap, BITS_TO_LONGS(size) * sizeof(unsigned long)))
		goto error;

	return 0;
error:
	bitmap_dump(bitmap, size);
	return 1;
}

int test3(int size)

{
	int start = random() % size;
	int nr = random() % (size - start);
	unsigned long offset;

	memset(bitmap, 0x00, BITS_TO_LONGS(size) * sizeof(unsigned long));
	bitmap_set(bitmap, start, nr);
	if (start) {
		offset = bitmap_find_next_zero_area(bitmap, size, 0, start, 0);
		if (offset != 0) {
			printf("start %ld nr %ld\n", start, nr);
			printf("offset %ld != 0\n", offset);
			goto error;
		}
	}
	offset = bitmap_find_next_zero_area(bitmap, size, start,
						size - (start + nr), 0);
	if (offset != start + nr) {
		printf("start %ld nr %ld\n", start, nr);
		printf("offset %ld != size + nr %ld\n", offset, start + nr);
		goto error;
	}

	return 0;
error:
	bitmap_dump(bitmap, size);

	return 1;
}

int test4(int size)

{
	int start = random() % size;
	int nr = random() % (size - start);
	unsigned long offset;

	memset(bitmap, 0xff, BITS_TO_LONGS(size) * sizeof(unsigned long));
	bitmap_clear(bitmap, start, nr);
	offset = bitmap_find_next_zero_area(bitmap, size, start, nr, 0);
	if (nr != 0) {
		if (offset != start) {
			printf("start %ld nr %ld\n", start, nr);
			printf("offset %ld != start %ld\n", offset, start);
			goto error;
		}
	}
	return 0;
error:
	bitmap_dump(bitmap, size);

	return 1;
}

int main(int argc, char *argv[])

{
	int err = 0;

	srandom(time(NULL));

	memset(empty, 0x00, sizeof(empty));
	memset(full, 0xff, sizeof(full));

	while (!err) {
		err |= test1(1000);
		err |= test2(1000);
		err |= test3(1000);
		err |= test4(1000);
	}
	return 0;
}
#14 lore raw

PATCH 1/1 Fix bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area. patch

In reply to Akinobu Mita

Update PATCH 2/8 based on review comments by Andrew and bugfix exposed by user space testing.

I didn't change argument of align_mask at this time because it turned out that it needs more changes in iommu-helper users.

From: Akinobu Mita <[email protected]>
Subject: Fix bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area.patch

- Rewrite bitmap_set and bitmap_clear

Instead of setting or clearing for each bit.

- Fix off-by-one error in bitmap_find_next_zero_area

This bug was derived from find_next_zero_area in iommu-helper.

- Add kerneldoc for bitmap_find_next_zero_area

This patch is supposed to be folded into bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area.patch

---
 lib/bitmap.c |   60 +++++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 47 insertions(+), 13 deletions(-)
lib/bitmap.c +47 -13
index 2415da4..84292c9 100644
@@ -271,28 +271,62 @@ int __bitmap_weight(const unsigned long *bitmap, int bits)
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
-void bitmap_set(unsigned long *map, int i, int len)
-{
-	int end = i + len;
+#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
 
-	while (i < end) {
-		__set_bit(i, map);
-		i++;
+void bitmap_set(unsigned long *map, int start, int nr)
+{
+	unsigned long *p = map + BIT_WORD(start);
+	const int size = start + nr;
+	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+	while (nr - bits_to_set >= 0) {
+		*p |= mask_to_set;
+		nr -= bits_to_set;
+		bits_to_set = BITS_PER_LONG;
+		mask_to_set = ~0UL;
+		p++;
+	}
+	if (nr) {
+		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+		*p |= mask_to_set;
 	}
 }
 EXPORT_SYMBOL(bitmap_set);
 
 void bitmap_clear(unsigned long *map, int start, int nr)
 {
-	int end = start + nr;
-
-	while (start < end) {
-		__clear_bit(start, map);
-		start++;
+	unsigned long *p = map + BIT_WORD(start);
+	const int size = start + nr;
+	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+
+	while (nr - bits_to_clear >= 0) {
+		*p &= ~mask_to_clear;
+		nr -= bits_to_clear;
+		bits_to_clear = BITS_PER_LONG;
+		mask_to_clear = ~0UL;
+		p++;
+	}
+	if (nr) {
+		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+		*p &= ~mask_to_clear;
 	}
 }
 EXPORT_SYMBOL(bitmap_clear);
 
+/*
+ * 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,
@@ -304,10 +338,10 @@ again:
 	index = find_next_zero_bit(map, size, start);
 
 	/* Align allocation */
-	index = (index + align_mask) & ~align_mask;
+	index = __ALIGN_MASK(index, align_mask);
 
 	end = index + nr;
-	if (end >= size)
+	if (end > size)
 		return end;
 	i = find_next_bit(map, end, index);
 	if (i < end) {
Signature · 1 line
1.5.4.3
#15 lore raw

PATCH 1/1 Fix bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area. patch

From: Akinobu Mita <[email protected]>
Subject: Fix bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area.patch

- Rewrite bitmap_set and bitmap_clear

Instead of setting or clearing for each bit.

- Fix off-by-one errors in bitmap_find_next_zero_area

This bug was derived from find_next_zero_area in iommu-helper.

- Add kerneldoc for bitmap_find_next_zero_area

This patch is supposed to be folded into bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area.patch

* -v2
- Remove an extra test at the "index" value by find_next_bit

Index was just returned by find_next_zero_bit, so we know it's zero.

---
 lib/bitmap.c |   62 ++++++++++++++++++++++++++++++++++++++++++++-------------
 1 files changed, 48 insertions(+), 14 deletions(-)
lib/bitmap.c +48 -14
index 2415da4..962b863 100644
@@ -271,28 +271,62 @@ int __bitmap_weight(const unsigned long *bitmap, int bits)
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
-void bitmap_set(unsigned long *map, int i, int len)
-{
-	int end = i + len;
+#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
 
-	while (i < end) {
-		__set_bit(i, map);
-		i++;
+void bitmap_set(unsigned long *map, int start, int nr)
+{
+	unsigned long *p = map + BIT_WORD(start);
+	const int size = start + nr;
+	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+	while (nr - bits_to_set >= 0) {
+		*p |= mask_to_set;
+		nr -= bits_to_set;
+		bits_to_set = BITS_PER_LONG;
+		mask_to_set = ~0UL;
+		p++;
+	}
+	if (nr) {
+		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+		*p |= mask_to_set;
 	}
 }
 EXPORT_SYMBOL(bitmap_set);
 
 void bitmap_clear(unsigned long *map, int start, int nr)
 {
-	int end = start + nr;
-
-	while (start < end) {
-		__clear_bit(start, map);
-		start++;
+	unsigned long *p = map + BIT_WORD(start);
+	const int size = start + nr;
+	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+
+	while (nr - bits_to_clear >= 0) {
+		*p &= ~mask_to_clear;
+		nr -= bits_to_clear;
+		bits_to_clear = BITS_PER_LONG;
+		mask_to_clear = ~0UL;
+		p++;
+	}
+	if (nr) {
+		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+		*p &= ~mask_to_clear;
 	}
 }
 EXPORT_SYMBOL(bitmap_clear);
 
+/*
+ * 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,
@@ -304,12 +338,12 @@ again:
 	index = find_next_zero_bit(map, size, start);
 
 	/* Align allocation */
-	index = (index + align_mask) & ~align_mask;
+	index = __ALIGN_MASK(index, align_mask);
 
 	end = index + nr;
-	if (end >= size)
+	if (end > size)
 		return end;
-	i = find_next_bit(map, end, index);
+	i = find_next_bit(map, end, index + 1);
 	if (i < end) {
 		start = i + 1;
 		goto again;
Signature · 1 line
1.5.4.3
#16 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

In reply to Akinobu Mita
Quoted 15 lines · On Tue, 13 Oct 2009 18:10:17 +0900 Akinobu Mita <[email protected]> wrote:

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper. Some zero area cannot be found by this bug.

Subject: [PATCH] Fix off-by-one error in find_next_zero_area

---
 lib/iommu-helper.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)
lib/iommu-helper.c +0 -0
index 75dbda0..afc58bc 100644

lib/iommu-helper.c again: · line 22

Quoted 5 lines
lib/iommu-helper.c +1 -1
@@ -19,7 +19,7 @@ again:
 	index = (index + align_mask) & ~align_mask;
 
 	end = index + nr;
-	if (end >= size)
+	if (end > size)

I think that this is intentional; the last byte of the limit doesn't work.

#17 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

2009/10/17 FUJITA Tomonori <[email protected]>:

Quoted 20 lines
Quoted 17 lines · On Tue, 13 Oct 2009 18:10:17 +0900 Akinobu Mita <[email protected]> wrote:

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper. Some zero area cannot be found by this bug.

Subject: [PATCH] Fix off-by-one error in find_next_zero_area

---
 lib/iommu-helper.c |    2 +-

 1 files changed, 1 insertions(+), 1 deletions(-)
lib/iommu-helper.c +0 -0
index 75dbda0..afc58bc 100644
@@ -19,7 +19,7 @@ again:
       index = (index + align_mask) & ~align_mask;
 
Quoted 6 lines

lib/iommu-helper.c again: · line 22

Quoted 3 lines
lib/iommu-helper.c +1 -1
       end = index + nr;
-     if (end >= size)
+     if (end > size)

I think that this is intentional; the last byte of the limit doesn't work.

It looks ok to me. Without above change, find_next_zero_area cannot find a 64 bits zeroed area in next sample code.

        unsigned long offset;

        DECLARE_BITMAP(map, 64);

        bitmap_clear(map, 0, 64);
        offset = find_next_zero_area(map, 64, 0, 64, 0);
        if (offset >= 64)
                printf("not found\n");
        else
                printf("found\n");
#18 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

Quoted 28 lines · On Sat, 17 Oct 2009 23:43:56 +0900 Akinobu Mita <[email protected]> wrote:

2009/10/17 FUJITA Tomonori <[email protected]>:

Quoted 20 lines
Quoted 17 lines · On Tue, 13 Oct 2009 18:10:17 +0900 Akinobu Mita <[email protected]> wrote:

My user space testing exposed off-by-one error find_next_zero_area in iommu-helper. Some zero area cannot be found by this bug.

Subject: [PATCH] Fix off-by-one error in find_next_zero_area

---
 lib/iommu-helper.c |    2 +-

 1 files changed, 1 insertions(+), 1 deletions(-)
lib/iommu-helper.c +0 -0
index 75dbda0..afc58bc 100644
@@ -19,7 +19,7 @@ again:
       index = (index + align_mask) & ~align_mask;
 
Quoted 6 lines

lib/iommu-helper.c again: · line 22

Quoted 3 lines
lib/iommu-helper.c +1 -1
       end = index + nr;
-     if (end >= size)
+     if (end > size)

I think that this is intentional; the last byte of the limit doesn't work.

Quoted 2 lines

It looks ok to me. Without above change, find_next_zero_area cannot find a 64 bits zeroed area in next sample code.

I meant that we don't want to find such area for IOMMUs (IIRC, it code came from POWER IOMMU).

Quoted 14 lines
        unsigned long offset;

        DECLARE_BITMAP(map, 64);

        bitmap_clear(map, 0, 64);
        offset = find_next_zero_area(map, 64, 0, 64, 0);
        if (offset >= 64)
                printf("not found\n");
        else
                printf("found\n");

--
To unsubscribe from this list: send the line "unsubscribe linux-ia64" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#19 lore raw

Re: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

Quoted 12 lines
Quoted 12 lines
Quoted 11 lines

lib/iommu-helper.c again: · line 22

Quoted 8 lines
lib/iommu-helper.c +1 -1
@@ -19,7 +19,7 @@ again:
       index = (index + align_mask) & ~align_mask;
 
       end = index + nr;
-     if (end >= size)
+     if (end > size)

I think that this is intentional; the last byte of the limit doesn't work.

Quoted 5 lines
Quoted 2 lines

It looks ok to me. Without above change, find_next_zero_area cannot find a 64 bits zeroed area in next sample code.

I meant that we don't want to find such area for IOMMUs (IIRC, it code came from POWER IOMMU).

OK, I see. I think we need the comment about it.

So we cannot replace find_next_zero_area by bitmap_find_next_zero_area and current -mmotm has the bug introduced by this patch in iommu-helper and I also introduced the bug in bitmap_find_next_zero_area if align_mask != 0 in bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area-fix.patch

Andrew, please drop

lib-iommu-helperc-fix-off-by-one-error-in-find_next_zero_area.patch iommu-helper-simplify-find_next_zero_area.patch bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area.patch bitmap-introduce-bitmap_set-bitmap_clear-bitmap_find_next_zero_area-fix.patch iommu-helper-use-bitmap-library.patch isp1362-hcd-use-bitmap_find_next_zero_area.patch mlx4-use-bitmap_find_next_zero_area.patch sparc-use-bitmap_find_next_zero_area.patch ia64-use-bitmap_find_next_zero_area.patch genalloc-use-bitmap_find_next_zero_area.patch

I'll overhaul the patchset and retry again.