bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area
Subsystems (8)
PATCH 1/7 bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area
This introduces new bitmap functions:
bitmap_set: Set specified bit areabitmap_clear: Clear specified bit areabitmap_find_next_zero_area: Find free bit area
These are mostly stolen from iommu helper. The differences are:
- Use find_next_bit instead of doing test_bit for each bit
- Rewrite bitmap_set and bitmap_clear
Instead of setting or clearing for each bit.
- Check the last bit of the limit
iommu-helper doesn't want to find such area
- The return value if there is no zero area
find_next_zero_area in iommu helper: returns -1 bitmap_find_next_zero_area: return >= bitmap size
--- include/linux/bitmap.h | 11 ++++++ lib/bitmap.c | 81 ++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+), 0 deletions(-)
include/linux/bitmap.h +11 -0
@@ -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 +81 -0
87 lines not on this page · raw message
Signature · 1 line
1.6.5.1
PATCH 2/7 iommu-helper: Use bitmap library
Use bitmap library and kill some unused iommu helper functions.
1. s/iommu_area_free/bitmap_clear/
2. s/iommu_area_reserve/bitmap_set/
3. Use bitmap_find_next_zero_area instead of find_next_zero_area
This cannot be simple substitution because find_next_zero_area doesn't check the last bit of the limit in bitmap
4. Remove iommu_area_free, iommu_area_reserve, and find_next_zero_area
--- 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 | 59 ++++++-------------------------------- 7 files changed, 21 insertions(+), 64 deletions(-)
arch/powerpc/kernel/iommu.c +2 -2
@@ -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
@@ -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
@@ -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
@@ -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
@@ -23,7 +23,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>
@@ -123,7 +123,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);
@@ -782,7 +782,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
@@ -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 +9 -50
81 lines not on this page · raw message
Signature · 1 line
1.6.5.1
PATCH 3/7 isp1362-hcd: Use bitmap_find_next_zero_area
In reply to Akinobu Mita--- drivers/usb/host/isp1362-hcd.c | 26 ++++++-------------------- 1 files changed, 6 insertions(+), 20 deletions(-)
drivers/usb/host/isp1362-hcd.c +6 -20
@@ -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.6.5.1
PATCH 4/7 mlx4: Use bitmap_find_next_zero_area
In reply to Akinobu Mita--- drivers/net/mlx4/alloc.c | 37 ++++--------------------------------- 1 files changed, 4 insertions(+), 33 deletions(-)
drivers/net/mlx4/alloc.c +4 -33
@@ -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.6.5.1
PATCH 5/7 sparc: Use bitmap_find_next_zero_area
In reply to Akinobu Mita--- 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
@@ -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
@@ -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.6.5.1
PATCH 6/7 ia64: Use bitmap_find_next_zero_area
In reply to Akinobu Mita--- arch/ia64/sn/pci/tioca_provider.c | 19 +++++-------------- 1 files changed, 5 insertions(+), 14 deletions(-)
arch/ia64/sn/pci/tioca_provider.c +5 -14
@@ -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.6.5.1
PATCH 7/7 genalloc: Use bitmap_find_next_zero_area
In reply to Akinobu Mita--- lib/genalloc.c | 33 ++++++++++++--------------------- 1 files changed, 12 insertions(+), 21 deletions(-)
lib/genalloc.c +12 -21
@@ -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.6.5.1
Andrew Morton
maintainerWhy were these patches resent? What changed?
Everybody who is going to review these patches has already reviewed them and now they need to review them all again?
2009/10/29 Andrew Morton <[email protected]>:
Quoted 5 lines
Why were these patches resent? What changed?
Everybody who is going to review these patches has already reviewed them and now they need to review them all again?
I resent the patches because the iommu-helper change was not correct and I introduced serious bug in bitmap_find_next_zero_area() if align_mask != 0 in follow-up patch then those were dropped from the -mm tree.
Only [PATCH 1/7] and [PATCH 2/7] have changes since the first submission of this patch set.
* [PATCH 1/7]
- Rewrite bitmap_set() and bitmap_clear()
- Let bitmap_find_next_zero_area() check the last bit of the limit
- Add kerneldoc for bitmap_find_next_zero_area()
* [PATCH 2/7]
- Convert find_next_zero_area() to use bitmap_find_next_zero_area() correctly iommu-helper doesn't want to search the last bit of the limist in bitmap
* [PATCH 3/7] - [PATCH 7/7]
- No changes