find_next bitops on m68k may cause out of bounds memory access

find_next bitops on m68k may cause out of bounds memory access

[Akinobu Mita]

find_next bitops on m68k (find_next_zero_bit, find_next_bit, and
ext2_find_next_bit) may cause out of bounds memory access
when the bitmap size in bits % 32 != 0 and offset (the bitnumber
to start searching at) is very close to the bitmap size.

For example,

	unsigned long bitmap[2] = { 0, 0};
	find_next_bit(bitmap, 63, 62)

1. find_next_bit() tries to find any set bits in bitmap[1], but no bits set

2. Then find_first_bit(bimap + 2, -1)

3. Unfortunately find_fist_bit() takes unsigned int as the size argument.

4. find_first_bit will access bitmap[3~] until it find any set bits.

Here is find_next_bit() in arch/m68k/include/asm/bitops_mm.h:

static inline int find_next_bit(const unsigned long *vaddr, int size,
                                int offset)
{
        const unsigned long *p = vaddr + (offset >> 5);
        int bit = offset & 31UL, res;

        if (offset >= size)
                return size;

        if (bit) {
                unsigned long num = *p++ & (~0UL << bit);
                offset -= bit;

                /* Look for one in first longword */
                __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
                                      : "=d" (res) : "d" (num & -num));
                if (res < 32)
                        return offset + (res ^ 31);
                offset += 32;
        }
        /* No one yet, search remaining full bytes for a one */
        res = find_first_bit(p, size - ((long)p - (long)vaddr) * 8);
        return offset + res;
}

find_next_zero_bit and ext2_find_next_bit also have same problem.
Actually I found this while testing ext2_find_next_bit in user space.

The easiest and reliable way to fix this is that switching to generic
implementation of find bitops.

Re: find_next bitops on m68k may cause out of bounds memory access

[Michael Schmitz]

Thanks for spotting this - does anyone remember when this version of
find_next bitops was first introduced?

I wonder whether this might explain our crashes while using SLUB in
recent kernels.

  Michael

On Tue, Feb 8, 2011 at 1:37 AM, Akinobu Mita <akinobu.mita@gmail.com> wrote:
> find_next bitops on m68k (find_next_zero_bit, find_next_bit, and
> ext2_find_next_bit) may cause out of bounds memory access
> when the bitmap size in bits % 32 != 0 and offset (the bitnumber
> to start searching at) is very close to the bitmap size.
>
> For example,
>
>        unsigned long bitmap[2] = { 0, 0};
>        find_next_bit(bitmap, 63, 62)
>
> 1. find_next_bit() tries to find any set bits in bitmap[1], but no bits set
>
> 2. Then find_first_bit(bimap + 2, -1)
>
> 3. Unfortunately find_fist_bit() takes unsigned int as the size argument.

Can't that be changed? After all, find_next_bit takes int as size as well.

> 4. find_first_bit will access bitmap[3~] until it find any set bits.
>
> Here is find_next_bit() in arch/m68k/include/asm/bitops_mm.h:
>
> static inline int find_next_bit(const unsigned long *vaddr, int size,
>                                int offset)
> {
>        const unsigned long *p = vaddr + (offset >> 5);
>        int bit = offset & 31UL, res;
>
>        if (offset >= size)
>                return size;
>
>        if (bit) {
>                unsigned long num = *p++ & (~0UL << bit);
>                offset -= bit;
>
>                /* Look for one in first longword */
>                __asm__ __volatile__ ("bfffo %1{#0,#0},%0"
>                                      : "=d" (res) : "d" (num & -num));
>                if (res < 32)
>                        return offset + (res ^ 31);
>                offset += 32;
>        }
>        /* No one yet, search remaining full bytes for a one */

I'll try adding a sanity check here to see whether this actually
causes any trouble with SLUB.

>        res = find_first_bit(p, size - ((long)p - (long)vaddr) * 8);
>        return offset + res;
> }
>
> find_next_zero_bit and ext2_find_next_bit also have same problem.
> Actually I found this while testing ext2_find_next_bit in user space.
>
> The easiest and reliable way to fix this is that switching to generic
> implementation of find bitops.
> --
> To unsubscribe from this list: send the line "unsubscribe linux-m68k" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: find_next bitops on m68k may cause out of bounds memory access

[Andreas Schwab]

Michael Schmitz <schmitzmic@googlemail.com> writes:

> Thanks for spotting this - does anyone remember when this version of
> find_next bitops was first introduced?

c82db5b in git.kernel.org:ralf/linux-m68k.git

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: find_next bitops on m68k may cause out of bounds memory access

[Michael Schmitz]

Thanks Andreas - there goes my theory I guess. Ralf's linux-m68k CVS
conversion tree predates 2.6.32 by quite some time.

  Michael


On Tue, Feb 8, 2011 at 11:33 AM, Andreas Schwab <schwab@linux-m68k.org> wrote:
> Michael Schmitz <schmitzmic@googlemail.com> writes:
>
>> Thanks for spotting this - does anyone remember when this version of
>> find_next bitops was first introduced?
>
> c82db5b in git.kernel.org:ralf/linux-m68k.git
>
> Andreas.
>
> --
> Andreas Schwab, schwab@linux-m68k.org
> GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
> "And now for something completely different."
>