WARNING - OLD ARCHIVES

This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
   
 
 
Xen 
 
Home Products Support Community News
 
   
 

xen-devel

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

To: wei huang <huanwei@xxxxxxxxxxxxxxxxxx>
Subject: Re: [Xen-devel] Possible bug in gntdev.c
From: Derek Murray <Derek.Murray@xxxxxxxxxxxx>
Date: Tue, 23 Oct 2007 09:39:11 +0100
Cc: xen-devel@xxxxxxxxxxxxxxxxxxx
Delivery-date: Tue, 23 Oct 2007 01:39:55 -0700
Envelope-to: www-data@xxxxxxxxxxxxxxxxxx
In-reply-to: <Pine.GSO.4.40.0710221337480.13660-100000@xxxxxxxxxxxxxxxxxxxxx>
List-help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-id: Xen developer discussion <xen-devel.lists.xensource.com>
List-post: <mailto:xen-devel@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/cgi-bin/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
References: <Pine.GSO.4.40.0710221337480.13660-100000@xxxxxxxxxxxxxxxxxxxxx>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
User-agent: Thunderbird 2.0.0.5 (X11/20070727)
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