Received-SPF: softfail (google.com: domain of transitioning linux-kernel-owner@vger.kernel.org does not designate 23.128.96.19 as permitted sender) client-ip=23.128.96.19;
Message-ID: <91f95228-215c-b817-8bb6-8e24c0caf925@oracle.com>
Date:   Fri, 13 May 2022 22:34:19 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:91.0)
 Gecko/20100101 Thunderbird/91.9.0
Subject: Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants
Content-Language: en-US
To:     Juergen Gross <jgross@suse.com>,
        Oleksandr Tyshchenko <olekstysh@gmail.com>,
        xen-devel@lists.xenproject.org, linux-kernel@vger.kernel.org,
        linux-arm-kernel@lists.infradead.org
Cc:     Stefano Stabellini <sstabellini@kernel.org>,
        Julien Grall <julien@xen.org>,
        Oleksandr Tyshchenko <oleksandr_tyshchenko@epam.com>,
        "Michael S. Tsirkin" <mst@redhat.com>,
        Christoph Hellwig <hch@infradead.org>
References: <1651947548-4055-1-git-send-email-olekstysh@gmail.com>
 <1651947548-4055-3-git-send-email-olekstysh@gmail.com>
 <597125fd-4c85-fde0-9d5b-a9cc13a81ccc@oracle.com>
 <d1d61bcf-86f9-68cd-9bd4-a13bf8149b88@suse.com>
From:   Boris Ostrovsky <boris.ostrovsky@oracle.com>
In-Reply-To: <d1d61bcf-86f9-68cd-9bd4-a13bf8149b88@suse.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?utf-8?B?UGRET0NDNHVBcDJqWm52WElxeDVzTHVnTzNTRDZ3aFpIbHY1NGFHZ3pjOGJv?=
 =?utf-8?B?KzBFVUs1elVoTkpqdllrM1dNbDdZU1R3blBRWFJLREpGbk1nZm1sblUxa2pI?=
 =?utf-8?B?Z3FkQXBwT09La2M0QTlaRHIvdUtnVmd6VnJTZ2x3MnlmZ092NGM1THU0dlZO?=
 =?utf-8?B?WEVoSUk2TTNPaW1QeGZiVzh6RmEvZ2QxSS9JVHRIUUd5Y2xhR3JkWkJzZUZC?=
 =?utf-8?B?OEN3MTZWRG52VmhwWGdZalFlamY5TkhHMnlPTzBSY1ZOb0dWVmp1YXdFYVJu?=
 =?utf-8?B?dVBackY2VmpIcE5telVpa0FycDF5b1RDZ0ZaTS9IN2c0MGw2Mm5rL0d4L1Qv?=
 =?utf-8?B?bmYvbVpTR3BzSVEyWjl0WEc3QnkxTHU5djZib1BOemRqNVNydU1Yb0dJaXNQ?=
 =?utf-8?B?UDlVOGpWSTh5Y1dpS0F2clJ3ZWtWQmZ6SXlVcGJVR0N6SDdDWVlOVWlGOXZv?=
 =?utf-8?B?WStjYmxCVkV1RkFPcjVCTm52K0I5QXBHZkwxZm90MEEyRmJ0UmcvMDBsZEta?=
 =?utf-8?B?d2phQ2E0bGVDTUE2dGNhcTlZbm50cGw1M2FGOGJ6Skhkb1llZmNTMHo4czVo?=
 =?utf-8?B?ODYzU3VNQ1dFS2RYcmltUTVqTDUxM1FzcHZLSzJoc1ZETUdIT1E0SGhrMDhj?=
 =?utf-8?B?ZXRFN1Zyc2RoNjJBTnNHdjk2cEpISm9NOXpMT2VVa1l5K1hlYmE2VlM5SndK?=
 =?utf-8?B?bWFOYnd3OCtWbFZzSUFSQ1JXN1FEdGwwVDNxSHN2TFVDTlJMZjlQSXAxWjYr?=
 =?utf-8?B?SWFTWDdnMG5haFBGdHExczA0cjg5aFBnMmVnazF5S2V2Y2xWOTMwRjZHMERV?=
 =?utf-8?B?bjZzQncxUmF3RDJuUFFoNjYzVHJtVWwxbjNZVG50TFN4Y3NFeWJSNWFHeWZi?=
 =?utf-8?B?eUQ0dU9qWVNiTjAxdWwyM2ovb0g4TWlMN1FCVnNPcFJ4TCtBTVRMblh5VjZS?=
 =?utf-8?B?U1pMS1Q5WGRrTndSTWdPUk8xcWdRRVNpRUhENERNQzN2bndEdmhYK3MyQ05h?=
 =?utf-8?B?d1hKdWN2emVJRkpRT2xhaHM1SnJXMjdpUHBNY0xodmlkc0hHazgzQzA0MmJO?=
 =?utf-8?B?dk9BTzh3NGtNSTZibnR3VERHN3diQXgwOTVJNnBteG9NRElpeTd1TjFaUTVo?=
 =?utf-8?B?bE1mOWZOWm9od1RaWUZQY2h1UTZSUE15MzVBVVRmQkpzclV5Qk1INUlVN3JZ?=
 =?utf-8?B?RmVCV1dwckNIVUkrTTRrOTJLNE1hWUlTbFNCcXBJWnBVb3FteDFzbXlpS1ZB?=
 =?utf-8?B?MDdCempoS2VrZThScHVqV1FZYjUxU2IxTWNHMkFvaFQzbDNHNCtQMTFOZllj?=
 =?utf-8?B?NVRWQ3hXTDR0KzBQOVZmNEJZR0EwVkJOdTBuTGJ6K0lEYjRWU0tYb01JU0xZ?=
 =?utf-8?B?TzZKSWdmWDhMR3BkSVhReFp4dFZSay9MYTcrb2Q2WG5OU3RaSC9aeUpLRGNQ?=
 =?utf-8?B?WXZsRzVDSXJLTVpsZjMwR1ZtckU5cHZlMERJb1VKc0I4cGREa0ZoQ1NiUkdW?=
 =?utf-8?B?TENHZFMvSUNpdjUvU2VnaXR6MFZ3L2VmUzAwZHg5VC80eGRucUE2QzhibnFt?=
 =?utf-8?B?MUV5SjV2RkZKSWZEdzQwdUdTczZFemNMRTkvLzN4ZDZZQWF2djJ3Mkk4Rzdq?=
 =?utf-8?B?VUt2ZzZRMVVEbGxESENUZXVMcERJejh5SGVsck80VlcvYVo3MC9ZVXpaY3Nq?=
 =?utf-8?B?ZmFKbWNWMkxWSnAvWmRYNDZOUEVmL0c0cndxQ0F2cXdROVU4ZmlUT3BLN1Vk?=
 =?utf-8?B?eFovL3hQU1BINTd4dXdUbW1PdFo2SCs3eVFLcE93TlY3WDFlQ1lScWo1L2VC?=
 =?utf-8?B?Y3c2dExtRFNBUHMva0RKQ1hvZ1BUM0VFTnVUaUEyeWVyVXl2WEsyeFkyck1P?=
 =?utf-8?B?aERRczVkVXFZSi8xYWZTMEd0Y3lFSzdEam5IS0ExaGVDTVhadURtOHhlRGtt?=
 =?utf-8?B?NEh1dGp4Mmo0Mk1YdVBJZFJ5cGVTaE5ZR045V0t2TWVrRHhuYVRLNGt0UVpL?=
 =?utf-8?B?T3pvL0lZb3VqNTJuUjl3WWQrS01tUWtZZ2dYQUxMT3lVcjFia0tIUHd3dWtT?=
 =?utf-8?B?Ynl4ZkxPdWVGWXIrMUJHazNIamd4Nk5rVWlGWU15cXZ5d0F4bms5R0p3Y3NO?=
 =?utf-8?B?b1RnOHJnZnVGc3E0UVBMbHV4Qy9RaFEwb3BHRmN4QU4rZXV2NGYwUWowNEoz?=
 =?utf-8?B?ZFg0K3VCV29rVDNhcitkVkV0V2hOSnovNUJIVHBkUGZCbWRlTVYwMnZjYmZr?=
 =?utf-8?B?VWV6clpyQTJaUnBDendpbE5RTllpMVBqNTBteEkreTdiR2J5OXUzVTNZK3BQ?=
 =?utf-8?B?UE80dFdYTUR1MmcrZHpsd3Y3aGZnZ29EMzYxRXZxbW1DQWk0WDI2dzFOSzFI?=
 =?utf-8?Q?kMiEBFpvaS8qa+bU=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: efe6e20d-1489-4578-90fd-08da3552407c
X-MS-Exchange-CrossTenant-AuthSource: BLAPR10MB5009.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 14 May 2022 02:34:21.3731
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 4e2c6054-71cb-48f1-bd6c-3a9705aca71b
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: gU7pW8pRwHFuCXIBuUG3P1X1VIGpe3DICoh+sj/CmsPvmqsR8A01nCObhV65O2U5dDCvVU+f3s1VN2u5NgjPKZhW8WDJo56cirkEp5YB4o8=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: CH0PR10MB4825
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.486,18.0.858
 definitions=2022-05-13_08:2022-05-13,2022-05-13 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 malwarescore=0 adultscore=0
 phishscore=0 mlxscore=0 spamscore=0 bulkscore=0 mlxlogscore=999
 suspectscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2202240000 definitions=main-2205140012
X-Proofpoint-GUID: GN7K3KiDBj9kiXHe3DJ6yk4_YdSpBSqj
X-Proofpoint-ORIG-GUID: GN7K3KiDBj9kiXHe3DJ6yk4_YdSpBSqj
X-Spam-Status: No, score=-4.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HEADER_FROM_DIFFERENT_DOMAINS,
	MAILING_LIST_MULTI,NICE_REPLY_A,RDNS_NONE,SPF_HELO_NONE,
	T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no
	version=3.4.6
X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on
	lindbergh.monkeyblade.net
Precedence: bulk
List-ID: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.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