Bug in find_vma_prev - mmap.c

Bug in find_vma_prev - mmap.c

[Tony Perkins]

This code returns vma (mm->mmap) if it sees that addr is lower than first VMA.
However, I think it falsely returns vma (mm->mmap) on the case where
addr is in the first VMA.

If it is the first VMA region:
- *pprev should be set to NULL
- implying prev is NULL
- and should therefore return vma (so in this case, I just added if
it's the first VMA and it's within range)

/* Same as find_vma, but also return a pointer to the previous VMA in *pprev. */
struct vm_area_struct *
find_vma_prev(struct mm_struct *mm, unsigned long addr,
            struct vm_area_struct **pprev)
{
    struct vm_area_struct *vma = NULL, *prev = NULL;
    struct rb_node *rb_node;
    if (!mm)
        goto out;

    /* Guard against addr being lower than the first VMA */
    vma = mm->mmap;

    /* Go through the RB tree quickly. */
    rb_node = mm->mm_rb.rb_node;

    while (rb_node) {
        struct vm_area_struct *vma_tmp;
        vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);

        if (addr < vma_tmp->vm_end) {
            // TONY: if (vma_tmp->vm_start <= addr) vma = vma_tmp; //
this returns the correct 'vma' when vma is the first node (i.e., no
prev)
            rb_node = rb_node->rb_left;
        } else {
            prev = vma_tmp;
            if (!prev->vm_next || (addr < prev->vm_next->vm_end))
                break;
            rb_node = rb_node->rb_right;
        }
    }

out:
    *pprev = prev;
    return prev ? prev->vm_next : vma;
}

Is this a known issue and/or has this problem been addressed?
Also, please CC my email address with responses.

Thanks,
--tony

--
Aim for Perfection!

Re: Bug in find_vma_prev - mmap.c

[Rafael J. Wysocki]

[Adding CCs]

On Saturday 30 January 2010, Tony Perkins wrote:
> This code returns vma (mm->mmap) if it sees that addr is lower than first VMA.
> However, I think it falsely returns vma (mm->mmap) on the case where
> addr is in the first VMA.
> 
> If it is the first VMA region:
> - *pprev should be set to NULL
> - implying prev is NULL
> - and should therefore return vma (so in this case, I just added if
> it's the first VMA and it's within range)
> 
> /* Same as find_vma, but also return a pointer to the previous VMA in *pprev. */
> struct vm_area_struct *
> find_vma_prev(struct mm_struct *mm, unsigned long addr,
>             struct vm_area_struct **pprev)
> {
>     struct vm_area_struct *vma = NULL, *prev = NULL;
>     struct rb_node *rb_node;
>     if (!mm)
>         goto out;
> 
>     /* Guard against addr being lower than the first VMA */
>     vma = mm->mmap;
> 
>     /* Go through the RB tree quickly. */
>     rb_node = mm->mm_rb.rb_node;
> 
>     while (rb_node) {
>         struct vm_area_struct *vma_tmp;
>         vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
> 
>         if (addr < vma_tmp->vm_end) {
>             // TONY: if (vma_tmp->vm_start <= addr) vma = vma_tmp; //
> this returns the correct 'vma' when vma is the first node (i.e., no
> prev)
>             rb_node = rb_node->rb_left;
>         } else {
>             prev = vma_tmp;
>             if (!prev->vm_next || (addr < prev->vm_next->vm_end))
>                 break;
>             rb_node = rb_node->rb_right;
>         }
>     }
> 
> out:
>     *pprev = prev;
>     return prev ? prev->vm_next : vma;
> }
> 
> Is this a known issue and/or has this problem been addressed?
> Also, please CC my email address with responses.

Well, I guess you should let the mm people know (CCs added).

Rafael

Re: Bug in find_vma_prev - mmap.c

[Hugh Dickins]

On Sat, 30 Jan 2010, Rafael J. Wysocki wrote:

> [Adding CCs]
> 
> On Saturday 30 January 2010, Tony Perkins wrote:
> > This code returns vma (mm->mmap) if it sees that addr is lower than first VMA.
> > However, I think it falsely returns vma (mm->mmap) on the case where
> > addr is in the first VMA.
> > 
> > If it is the first VMA region:
> > - *pprev should be set to NULL
> > - implying prev is NULL
> > - and should therefore return vma (so in this case, I just added if
> > it's the first VMA and it's within range)
> > 
> > /* Same as find_vma, but also return a pointer to the previous VMA in *pprev. */
> > struct vm_area_struct *
> > find_vma_prev(struct mm_struct *mm, unsigned long addr,
> >             struct vm_area_struct **pprev)
> > {
> >     struct vm_area_struct *vma = NULL, *prev = NULL;
> >     struct rb_node *rb_node;
> >     if (!mm)
> >         goto out;
> > 
> >     /* Guard against addr being lower than the first VMA */
> >     vma = mm->mmap;
> > 
> >     /* Go through the RB tree quickly. */
> >     rb_node = mm->mm_rb.rb_node;
> > 
> >     while (rb_node) {
> >         struct vm_area_struct *vma_tmp;
> >         vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
> > 
> >         if (addr < vma_tmp->vm_end) {
> >             // TONY: if (vma_tmp->vm_start <= addr) vma = vma_tmp; //
> > this returns the correct 'vma' when vma is the first node (i.e., no
> > prev)
> >             rb_node = rb_node->rb_left;
> >         } else {
> >             prev = vma_tmp;
> >             if (!prev->vm_next || (addr < prev->vm_next->vm_end))
> >                 break;
> >             rb_node = rb_node->rb_right;
> >         }
> >     }
> > 
> > out:
> >     *pprev = prev;
> >     return prev ? prev->vm_next : vma;
> > }
> > 
> > Is this a known issue and/or has this problem been addressed?
> > Also, please CC my email address with responses.
> 
> Well, I guess you should let the mm people know (CCs added).

Sorry, I don't see what the problem is: I may be misunderstanding.
Why do you think it is wrong to return the vma which addr is in
(whether or not that's the first vma)?

find_vma_prev() is supposed to return the same vma as find_vma()
does, but additionally fill in *pprev.  And find_vma() is supposed
to return the vma containing or the next vma above the addr supplied.

Hugh

Re: Bug in find_vma_prev - mmap.c

[Tony Perkins]

On Sun, Jan 31, 2010 at 8:25 AM, Hugh Dickins
<hugh.dickins@tiscali.co.uk> wrote:
> On Sat, 30 Jan 2010, Rafael J. Wysocki wrote:
>
>> [Adding CCs]
>>
>> On Saturday 30 January 2010, Tony Perkins wrote:
>> > This code returns vma (mm->mmap) if it sees that addr is lower than first VMA.
>> > However, I think it falsely returns vma (mm->mmap) on the case where
>> > addr is in the first VMA.
>> >
>> > If it is the first VMA region:
>> > - *pprev should be set to NULL
>> > - implying prev is NULL
>> > - and should therefore return vma (so in this case, I just added if
>> > it's the first VMA and it's within range)
>> >
>> > /* Same as find_vma, but also return a pointer to the previous VMA in *pprev. */
>> > struct vm_area_struct *
>> > find_vma_prev(struct mm_struct *mm, unsigned long addr,
>> >             struct vm_area_struct **pprev)
>> > {
>> >     struct vm_area_struct *vma = NULL, *prev = NULL;
>> >     struct rb_node *rb_node;
>> >     if (!mm)
>> >         goto out;
>> >
>> >     /* Guard against addr being lower than the first VMA */
>> >     vma = mm->mmap;
>> >
>> >     /* Go through the RB tree quickly. */
>> >     rb_node = mm->mm_rb.rb_node;
>> >
>> >     while (rb_node) {
>> >         struct vm_area_struct *vma_tmp;
>> >         vma_tmp = rb_entry(rb_node, struct vm_area_struct, vm_rb);
>> >
>> >         if (addr < vma_tmp->vm_end) {
>> >             // TONY: if (vma_tmp->vm_start <= addr) vma = vma_tmp; //
>> > this returns the correct 'vma' when vma is the first node (i.e., no
>> > prev)
>> >             rb_node = rb_node->rb_left;
>> >         } else {
>> >             prev = vma_tmp;
>> >             if (!prev->vm_next || (addr < prev->vm_next->vm_end))
>> >                 break;
>> >             rb_node = rb_node->rb_right;
>> >         }
>> >     }
>> >
>> > out:
>> >     *pprev = prev;
>> >     return prev ? prev->vm_next : vma;
>> > }
>> >
>> > Is this a known issue and/or has this problem been addressed?
>> > Also, please CC my email address with responses.
>>
>> Well, I guess you should let the mm people know (CCs added).
>
> Sorry, I don't see what the problem is: I may be misunderstanding.
> Why do you think it is wrong to return the vma which addr is in
> (whether or not that's the first vma)?
>
> find_vma_prev() is supposed to return the same vma as find_vma()
> does, but additionally fill in *pprev.  And find_vma() is supposed
> to return the vma containing or the next vma above the addr supplied.
>
> Hugh
>


Right Hugh,

Say for instance, that addr is not in the list (but is greater than
the last element).
find_vma_prev will return the last node in the list, whereas find_vma
will return NULL.

It seems that it is just inconsistent, in what it should return
regarding the two.
For instance, find_vma_prev will never return NULL, if there's at
least one node within the tree, whereas find_vma would.
find_extend_vma uses find_vma_prev and checks to see if it returns
NULL and is less than the return address (which would always be the
case).

Thanks!

-- 
Aim for Perfection!

Re: Bug in find_vma_prev - mmap.c

[Hugh Dickins]

On Sun, 31 Jan 2010, Tony Perkins wrote:
> 
> Say for instance, that addr is not in the list (but is greater than
> the last element).

Before, you appeared to be talking about a discrepancy with the first
vma; now you're talking about a discrepancy with the last vma?
Or a discrepancy when the first vma is the last vma?

> find_vma_prev will return the last node in the list, whereas find_vma
> will return NULL.

I'd expect find_vma_prev to return prev->vm_next, which would be NULL.

> 
> It seems that it is just inconsistent, in what it should return
> regarding the two.
> For instance, find_vma_prev will never return NULL, if there's at
> least one node within the tree, whereas find_vma would.
> find_extend_vma uses find_vma_prev and checks to see if it returns
> NULL and is less than the return address (which would always be the
> case).

Are we disagreeing about our readings of the code, or have you seen a
problem in practice?

I admit I've not tried running this, injecting addresses into find_vma_prev
and printk'ing the result; but I'm missing what leads you to say that
find_vma_prev will never return NULL.

Hugh