[PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Justin Chen]

This patch is to change the bitmap index in the bitops from "int" to "unsigned long".

In many bitops implementations, the bitmap index is a signed int.  If the caller passes a large unsigned integer and we interpret it as being negative, we compute an address outside the bitmap.  This can cause memory corruption or other errors.

The issue that triggered me to do this change is the routine mark_bootmem_node() while we ran on an ia64 box with large memory.  As long as the EFI maps the available memory chunk at the physical address 0x200000000000 (or above), the routine mark_bootmem_node() will get the start PFN>=0x80000000.  While it calls the __free() with this sidx=0x80000000 (bit31 set), the bitops (test_and_clear_bit) will treat this idx as a negative number since it accepts it as an "int".  It turns out the memory outside the bitmap will be corrupted.

Following 15 patches will change all the bitmap index "nr" in all bitops from "int" to "unsigned long".

The patch is based on 2.6.29-rc6

Please comment -

--jchen

(00/15): intro
(01/15): generic
(02/15): arm
(03/15): avr32
(04/15): blackfin
(05/15): cris
(06/15): h8300
(07/15): ia64
(08/15): m68k
(09/15): mn10300
(10/15): parisc
(11/15): powerpc
(12/15): sh
(13/15): x86
(14/15): frv
(15/15): m32r

 arch/arm/include/asm/bitops.h           |   39 +++++++++-------
 arch/arm/lib/changebit.S                |    2 
 arch/arm/lib/clearbit.S                 |    2 
 arch/arm/lib/setbit.S                   |    2 
 arch/avr32/include/asm/bitops.h         |   12 ++---
 arch/blackfin/include/asm/bitops.h      |   74 +++++++++++++++++++-------------
 arch/cris/include/asm/bitops.h          |    9 ++-
 arch/h8300/include/asm/bitops.h         |    8 +-
 arch/ia64/include/asm/bitops.h          |   30 ++++++------
 arch/ia64/include/asm/sync_bitops.h     |   21 ++++++---
 arch/m68k/include/asm/bitops_mm.h       |   63 ++++++++++++++++-----------
 arch/m68k/include/asm/bitops_no.h       |   34 +++++++++-----
 arch/mn10300/lib/bitops.c               |    4 -
 arch/parisc/include/asm/bitops.h        |   12 ++---
 arch/powerpc/include/asm/bitops.h       |   14 +++---
 arch/sh/include/asm/bitops-grb.h        |   12 ++---
 arch/sh/include/asm/bitops-llsc.h       |   12 ++---
 arch/sh/include/asm/bitops-op32.h       |   19 ++++----
 arch/x86/boot/bitops.h                  |    6 +-
 arch/x86/include/asm/bitops.h           |   48 +++++++++++++-------
 arch/x86/include/asm/sync_bitops.h      |   18 +++++--
 include/asm-frv/bitops.h                |   29 ++++++------
 include/asm-generic/bitops/atomic.h     |   17 ++++---
 include/asm-generic/bitops/non-atomic.h |   19 ++++----
 include/asm-m32r/bitops.h               |   14 +++---
 include/asm-mn10300/bitops.h            |   12 ++---
 26 files changed, 307 insertions(+), 219 deletions(-)

Re: [PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Peter Zijlstra]

On Tue, 2009-02-24 at 20:41 -0800, Justin Chen wrote:
> his patch is to change the bitmap index in the bitops from "int" to
> "unsigned long".
> 
> In many bitops implementations, the bitmap index is a signed int.  If
> the caller passes a large unsigned integer and we interpret it as
> being negative, we compute an address outside the bitmap.  This can
> cause memory corruption or other errors.
> 
> The issue that triggered me to do this change is the routine
> mark_bootmem_node() while we ran on an ia64 box with large memory.  As
> long as the EFI maps the available memory chunk at the physical
> address 0x200000000000 (or above), the routine mark_bootmem_node()
> will get the start PFN>=0x80000000.  While it calls the __free() with
> this sidx=0x80000000 (bit31 set), the bitops (test_and_clear_bit) will
> treat this idx as a negative number since it accepts it as an "int".
> It turns out the memory outside the bitmap will be corrupted.
> 
> Following 15 patches will change all the bitmap index "nr" in all
> bitops from "int" to "unsigned long".
> 
> The patch is based on 2.6.29-rc6
> 
> Please comment -

unsigned int wasn't large enough?

Re: [PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Matthew Wilcox]

On Wed, Feb 25, 2009 at 07:54:48AM +0100, Peter Zijlstra wrote:
> unsigned int wasn't large enough?

Adding one more bit only doubles the maximum size.  That buys us, what,
another eighteen months until we have to change it again?  Unsigned long
seems most sensible to me.  Unsigned long long probably isn't worth
doing -- you'd have to be using one eighth of your address space on a
single bitmap.

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Peter Zijlstra]

On Wed, 2009-02-25 at 08:37 -0700, Matthew Wilcox wrote:
> On Wed, Feb 25, 2009 at 07:54:48AM +0100, Peter Zijlstra wrote:
> > unsigned int wasn't large enough?
> 
> Adding one more bit only doubles the maximum size.  That buys us, what,
> another eighteen months until we have to change it again?  Unsigned long
> seems most sensible to me.  Unsigned long long probably isn't worth
> doing -- you'd have to be using one eighth of your address space on a
> single bitmap.

Are you serious? Bitmaps of length 4G-bit (512M-byte) are way past the
sanely allocatable size anyway.

The complaint was that the signed thingy resulted in out of bounds
pointers (apparently unsigned doesn't?)

Re: [PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Matthew Wilcox]

On Wed, Feb 25, 2009 at 04:46:00PM +0100, Peter Zijlstra wrote:
> > Adding one more bit only doubles the maximum size.  That buys us, what,
> > another eighteen months until we have to change it again?  Unsigned long
> > seems most sensible to me.  Unsigned long long probably isn't worth
> > doing -- you'd have to be using one eighth of your address space on a
> > single bitmap.
> 
> Are you serious? Bitmaps of length 4G-bit (512M-byte) are way past the
> sanely allocatable size anyway.

Runtime allocatable, yes.  This particular instance was during boot.
Justin wrote:

> If the caller passes a large unsigned integer and we interpret it as
> being negative, we compute an address outside the bitmap.  This can
> cause memory corruption or other errors.

> The issue that triggered me to do this change is the routine
> mark_bootmem_node() while we ran on an ia64 box with large memory.
> As long as the EFI maps the available memory chunk at the physical
> address 0x200000000000 (or above), the routine mark_bootmem_node() will
> get the start PFN>=0x80000000.  While it calls the __free() with this
> sidx=0x80000000 (bit31 set), the bitops (test_and_clear_bit) will treat
> this idx as a negative number since it accepts it as an "int".  It turns
> out the memory outside the bitmap will be corrupted.

If we've got problems with overflowing 'int' on memory size, we'll be
overflowing 'unsigned int' in eighteen months.  0x200000000000 is large,
but we can easily add on an extra four nybbles.

I don't see the downside to using unsigned long instead of unsigned int.

-- 
Matthew Wilcox				Intel Open Source Technology Centre
"Bill, look, we understand that you're interested in selling us this
operating system, but compare it to ours.  We can't possibly take such
a retrograde step."

Re: [PATCH 00/15] bitops: Change bitmap index from int to unsigned long

[Peter Zijlstra]

On Wed, 2009-02-25 at 08:53 -0700, Matthew Wilcox wrote:
> I don't see the downside to using unsigned long instead of unsigned int.

OK, I guess, it just seemed plenty large enough, but if you're actually
running off the end..