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

[Derek Murray <Derek.Murray@xxxxxxxxxxxx>]

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