Re: [Xen-devel] Possible bug in gntdev.c

[wei huang <huanwei@xxxxxxxxxxxxxxxxxx>]

Hi Derek

I had a slightly modified version of this (I add some other stuff to
discover the VMs on the same host). And apparently I got the problem I
decribed using my version. I came up with this question when I was going
through line-by-line comparison trying to figure out my mistakes.

Perhaps the error is at my side that I have not fully understood your
code. I will work on it more and let you know.

Thanks.

- Wei


> Hi,
>
> Have you tried executing this example and observing if it does cause a
> bug and/or an unexpected error (such as ENOMEM)?
>
> When you map the single grant in your third step, it does not take the
> first free slot in the grants array; instead it takes the slot that is
> at the end of the free_list, which would be entry #3 in your example.
> When this grant is unmapped, entry #3 is re-appended to the free_list.
>
> The rationale behind this algorithm is that it is able to find a free
> single slot (the assumed common case) in O(1) time, rather than
> performing an O(n) search of the grants array.
>
> Regards,
>
> Derek Murray.
>
> wei huang wrote:
> > Hi list,
> >
> > I am playing with grant table device in xen-3.1
> > (http://xenbits.xensource.com/xen-3.1-testing.hg) these days and I am not
> > sure about the following code snippet for gntdev_ioctl function. These
> > could be a bug IMO:
> >
> > gntdev.c: line 899-912
> > ====================================================================
> > /* Unmap pages and add them to the free list.
> >  */
> > for (i = 0; i < op.count; ++i) {
> >     private_data->grants[start_index+i].state =
> >                                 GNTDEV_SLOT_INVALID;
> >
> >     private_data->grants[start_index+i].u.free_list_index =
> >                                 private_data->free_list_size;
> >
> >     private_data->free_list[private_data->free_list_size] =
> >                                 start_index + i;
> >         ++private_data->free_list_size;
> > }
> > compress_free_list(flip);
> > ====================================================================
> >
> > The reason I think this could be a bug is through this simple example.
> > Take the case MAX_GRANTS=4. In gntdev_open,
> > private_data->grants[i].u.free_list_index is initialized as (MAX_GRANTS -
> > i - 1), so for entry 0, 1, 2, 3, their corresponding free_list_index is:
> > entry #             free_list_index
> > 0           3
> > 1           2
> > 2           1
> > 3           0
> >
> > Now, suppose we map 4 pages one by one, and then unmap those pages one by
> > one. According to the above code, the free_list_index will become the
> > following. When you unmap and unset the 0th entry, the free_list_size at
> > that time is 0, ...:
> >
> > entry #         free_list_index
> > 0               0
> > 1               1
> > 2               2
> > 3               3
> >
> > Now, let's again map 1 page and unmap it. After
> > IOCTL_GNTDEV_UNMAP_GRANT_REF, the indices will be (free_list_size will be
> > 3 at the point of unmap):
> > entry #         free_list_index
> > 0               3
> > 1               1
> > 2               2
> > 3               3
> >
> > To here, the does not look correct to me. Actually if now I map 4 pages
> > at at one, we will think we still have 1 mapping slot not used.
> >
> > Am I making the correct observation?
> >
> > Thanks.
> >
> > Regards,
> > Wei Huang
> >
> > Dept. of Computer Science and Engineering
> > Ohio State University
> >
> >
> >
> >
> > _______________________________________________
> > Xen-devel mailing list
> > Xen-devel@xxxxxxxxxxxxxxxxxxx
> > http://lists.xensource.com/xen-devel
>


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel