[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants


  • To: Juergen Gross <jgross@xxxxxxxx>, Oleksandr Tyshchenko <olekstysh@xxxxxxxxx>, xen-devel@xxxxxxxxxxxxxxxxxxxx, linux-kernel@xxxxxxxxxxxxxxx, linux-arm-kernel@xxxxxxxxxxxxxxxxxxx
  • From: Boris Ostrovsky <boris.ostrovsky@xxxxxxxxxx>
  • Date: Fri, 13 May 2022 22:34:19 -0400
  • Arc-authentication-results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=oracle.com; dmarc=pass action=none header.from=oracle.com; dkim=pass header.d=oracle.com; arc=none
  • Arc-message-signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=cgqPCP3tT+Zuaez1zVSdaesB5qCjT220JkLszKaXsrw=; b=BSmwJO4imFqjAx1CpEAsXGifiXE280wOpIdNu88Nqhsiw9BJQVq4+07WO4rveZC1XT3e27zVDdxlqztzvJzuPEcNAIv8i1xepw0fiB47qYba3iHfSgXNCM/VObgP3gQuxlOpkVZlCa0Wmntt0j0Ak8eAI+ZDItyalZDQ3CFOXbhKxTC6b6CIGCpk3heQq2hv+qUWHDTG9arlbVf6laiD5SE6Q0H61Kv1ZXDf2/M67V9j6jgLG430Xd+cIfvMb7oAOlha2eYw9/U/uSNINmACBOkyx4jC7xVt0Kj0FWaaJQndy44bX8qHGwN1yh2uduRgdxxgpn+PW4NbpDneI5k1Pw==
  • Arc-seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=YD1jdNOgTF9aDfyye/5LoMp9bwaC0Vz5sMwBs0UO6P4rbiBWRSaP3AAXwljkjq0ruw65tXYRaV4uTpFT0Y+LgLC298qdCPCxPtNr9ZrrQHx7FbKK+bRbpBjlgW630DUjE8BpKSsn8w8iPFTBVmTQoChOWYqjA9MUDAQXbUEN+P8JdcmSK3GaPXtRqZ2KJO8xVqxqOAU+UPOq0VIRmXnXWCKoPTDqKg5+7hyQ5Vp5yGEKaLEJLwacNJzCQ9iLMOaOFnDYI58i7pyVulWegGG60d517pqHq96K4LBXJbvgirD3ZSf/RNYILHF5HtB7pHjMr73NetPyBhZtofchO2VVuA==
  • Cc: Stefano Stabellini <sstabellini@xxxxxxxxxx>, Julien Grall <julien@xxxxxxx>, Oleksandr Tyshchenko <oleksandr_tyshchenko@xxxxxxxx>, "Michael S. Tsirkin" <mst@xxxxxxxxxx>, Christoph Hellwig <hch@xxxxxxxxxxxxx>
  • Delivery-date: Sat, 14 May 2022 02:34:57 +0000
  • List-id: Xen developer discussion <xen-devel.lists.xenproject.org>



On 5/13/22 1:33 AM, Juergen Gross wrote:
On 12.05.22 22:01, Boris Ostrovsky wrote:

On 5/7/22 2:19 PM, Oleksandr Tyshchenko wrote:

+/* Rebuilds the free grant list and tries to find count consecutive entries. */
+static int get_free_seq(unsigned int count)
+{
+    int ret = -ENOSPC;
+    unsigned int from, to;
+    grant_ref_t *last;
+
+    gnttab_free_tail_ptr = &gnttab_free_head;
+    last = &gnttab_free_head;
+
+    for (from = find_first_bit(gnttab_free_bitmap, gnttab_size);
+         from < gnttab_size;
+         from = find_next_bit(gnttab_free_bitmap, gnttab_size, to + 1)) {
+        to = find_next_zero_bit(gnttab_free_bitmap, gnttab_size,
+                    from + 1);
+        if (ret < 0 && to - from >= count) {
+            ret = from;
+            bitmap_clear(gnttab_free_bitmap, ret, count);
+            from += count;
+            gnttab_free_count -= count;


IIUIC we can have multiple passes over this, meaning that the gnttab_free_count 
may be decremented more than once. Is that intentional?

After the first pass decrementing gnttab_free_cnt, ret will no
longer be less than zero, so this can be hit only once.

Oh, yes, of course.




+            if (from == to)
+                continue;
+        }
+
+        while (from < to) {
+            *last = from;
+            last = __gnttab_entry(from);
+            gnttab_last_free = from;
+            from++;
+        }


I have been looking at this loop and I can't understand what it is doing ;-( 
Can you enlighten me?

It is recreating the free list in order to have it properly sorted.
This is needed to make sure that the free tail has the maximum
possible size (you can take the tail off the list without having
to worry about breaking the linked list because of references into
the tail).


So let's say we have the (one-dimensional) table of length 13

idx    ..    2    3  ...  10  11  12

grant       12   11        2  -1   3


and gnttab_free_head is 10. I.e. the free list is 2, 12, 3, 11.

What will this look like after the 2 iterations of the outer loop?

(I am really having a mental block on this).



-boris




 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.