Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Message-ID: <80286144-cca4-ef07-3aca-2c2374881738@oracle.com>
Date:   Mon, 16 May 2022 12:00:05 -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>
 <91f95228-215c-b817-8bb6-8e24c0caf925@oracle.com>
 <e04fd32d-b379-d515-2080-781e555303f1@suse.com>
From:   Boris Ostrovsky <boris.ostrovsky@oracle.com>
In-Reply-To: <e04fd32d-b379-d515-2080-781e555303f1@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?UFhadkJpdEZBY0JnVXNNZUt2bjF6a2dubjNMTVNoSFovdWxrYmhSV0dEc1Mr?=
 =?utf-8?B?TTVrWWJ4Z2s1d0FaQjNNNVM3eURpb2RCbE56S2hQeUNpelozNk5kNnM4TFVR?=
 =?utf-8?B?VUN1TjlKakFHYU9ncDJrZ1JTWk5lb2pOU2w5bEMrVGtPTjcvM3ZQZXJmd29V?=
 =?utf-8?B?Y0JyNklPTUdZS1JJZi9jK2p3bEFjQ2s5ekpSL1FmMnZTM2tKUklmcmpCTkJy?=
 =?utf-8?B?SVJsREFXcXBjcHZ5WnhoVnpXcCtWTzVUS1J1Rnl5Vnc3Tmc4dDdWaXVFbHpV?=
 =?utf-8?B?WERaQ095YmdTRjZXTGYxTmptTWlzRGNiRi84Y0t3QU5vODJQMWI4RU94K1Ru?=
 =?utf-8?B?M1hGdmkzMWc2S3JMSTVqTEZ0T0tBVStKOVg3M1p0QWwyQ1RZSzhvTHBSTi9B?=
 =?utf-8?B?ZXpmT3BDcmRsRUw4WjFuZ09kMXN1OFlGZGdXbXpDZ2FtKzZsb2E1VmZEcTg4?=
 =?utf-8?B?dWxNTnNxVVh0N3BxUitlc0E4bkJSN01YQXp1Um14Z20xMy91TURMdytOYVAx?=
 =?utf-8?B?SVZ5NDBqQm5KUlRtMjlZQ0d5NGhlT1RYdDlYUWNHOFJ6T1hUMC9GNWZyY29k?=
 =?utf-8?B?Ym50Z3dObGM5YWFtbitzcG1xdWdvczMzUjI3YUpEZU8xbEIxcWZIRm1DOFRH?=
 =?utf-8?B?bmZkMTRSejFFVkhOTXVBNXJpUjlrQUE0bmNia0t5QzFIODFlNVV6ckoxbWlL?=
 =?utf-8?B?bEZ5WC9BTG41ZjlLVHZoT3RHU1dDTzg0ZHZSRk15NWpMYUF4cStJRDQ0VFhN?=
 =?utf-8?B?RkVxNWlNRkIwcTBvbUloY3BkbUh2c0t3YTN4OHV3bGh4RmQ0QWpJczMzWkZJ?=
 =?utf-8?B?ZTU3Y00ydzhJc3FTNmx5dXhsSDlYQkxzaXpvTS9Ta2MvL2U3aW02N2UxdVZm?=
 =?utf-8?B?dVM3ZTFpeUpZZHRzTTdaTnpNdkNUb1lsdHBCdm1GUDFWN0JDa0xjcWlsNUtZ?=
 =?utf-8?B?ancvOGhzMm50bmswYUJ1MmQ3dkt6T3pDQkRXcnlBVDNMSUtEM3oxU3dvc3pV?=
 =?utf-8?B?eVBpbkJTbmVHM0ZWVGRleHlIZjBmdHJ5MjVDY3AxTFZqNlc3MW5BL1ozTWg2?=
 =?utf-8?B?VGFmanRqMjNFR2NLNkVOTFpVUm9hVkNZaEdIQkZ0Q2pReTZzcTR3MTVZVUda?=
 =?utf-8?B?RjdnMG1HaTlqV2dUcWJKd2Ruam1pTXBXenQ5aHdCK3djUmRndEVsc0tLSkg1?=
 =?utf-8?B?ZENLc1o0S1lsdWpyanRFT3ErOCtSa2s2Um9tcFdLY0p3NTVIdTdtQWdnZnhh?=
 =?utf-8?B?enFyNnpOWmZrd25GbSt3M0Zkd2ZZY1pTL2VWYkZ1aTE0Z29nOWlpbUR1ejFr?=
 =?utf-8?B?MnNqZm4rZmZQV2FQczBPd0RsL25mWWRIOE5EandDT3hoRGRSS1d2d2RFQ2hv?=
 =?utf-8?B?VFYwTnBOczhwYjNxdlF2QnJpSnE3NTQ0aHpYeng5bzFrZXBWODQzandpeisw?=
 =?utf-8?B?emhJV1V1Qmt2SHcxeElCWWVORnoxdlJFVzd1N1l6VlgvNDBoUzZZOTczTGlK?=
 =?utf-8?B?Y21hN0N2bnhCSkgrclB1Q09TM0tQYXhpczBDcDZtZGk2Y1QxUk9na3J0NUxD?=
 =?utf-8?B?NlUzOG1HY3lURzNaQkNIbHZGbTlCUGxNQklCdG5hVVVReWc4c0JNSFd3M1lM?=
 =?utf-8?B?aldGTDZ3ZmN6aE5MK0ozWlNEWCtFRkY5QkRxQUpOZGg2Z0pFd2ljL2hlZkk0?=
 =?utf-8?B?ekhMa05tTkNtdFJpLzZpUy9zaUx0U1F3ak5YNXQ3Z2NBcUpLTkkrNjk2S0ps?=
 =?utf-8?B?b1FhcG9EQlFNczlJZ1BSbTJhYkJYSHQxRmk0RHhjdVE1S1Q5NXlqUWRjNmVX?=
 =?utf-8?B?b0Y3VkJ4KzhydEJObWZQa2d0WTRxL1ROUlNVVDRIbytjcjcrajBFcFBPUkF5?=
 =?utf-8?B?MVVEb2Q4RTJncXdlVmtCZi9jcGpkbFZoMElpVTduYXBFNmZRRHNDV09qS2FT?=
 =?utf-8?B?R1dnQXcrYzZ3WmtJSTM0eDM1N3k1UHpPNGJ3di9uUUQrUEdORXMzZUxtSHp0?=
 =?utf-8?B?c1FrRml5ZlVucGNvbldrVzVON3JteFhxcjFCckVrZExLekFDTExUSC95NmZR?=
 =?utf-8?B?TDExN1BvNndRQ3VjbStjODBXYUFlYzArUzUrclI1WTYyd0F6TzlOMGMvZ3VJ?=
 =?utf-8?B?cnZlVTl0bHhxUjJaeEp2dVVNb2RnRmMyNXk4RXJsU1gwdnRjZEJLd1FucGpD?=
 =?utf-8?B?WjRhVFUrVlZwQy9sUTRLYVVlNXF4cFdKM2t1MXRIRms5Zmo1YzNodXdyMWRk?=
 =?utf-8?B?LzBhRnF6T1JFOEsxM3JCcjJKRVAvQWNzdnl1a2J5UVM1Q2k5eUJ1VUtMRzhz?=
 =?utf-8?B?SlRrK05JUWt0VjFIbnYzbW5IQ0pxUnV0c2FWTldzUG1mOWZBVUlYRmxXWG5t?=
 =?utf-8?Q?8WclvEQ+diXTdGNY=3D?=
X-OriginatorOrg: oracle.com
X-MS-Exchange-CrossTenant-Network-Message-Id: ce285bab-33b9-445c-29f6-08da37552758
X-MS-Exchange-CrossTenant-AuthSource: BLAPR10MB5009.namprd10.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 16 May 2022 16:00:09.9902
 (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: FmoHxtbIvZsHsufZhRIcehYjAnhh14jgM+LxPJqnGqh2rfYvKOaKhp5mqABijLixWttSzvLNnMI1Akir23/yy25LmmKEBaW03RaN14oJdY0=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: SN6PR10MB2464
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:6.0.486,18.0.858
 definitions=2022-05-16_14:2022-05-16,2022-05-16 signatures=0
X-Proofpoint-Spam-Details: rule=notspam policy=default score=0 mlxscore=0 malwarescore=0
 suspectscore=0 mlxlogscore=999 adultscore=0 phishscore=0 spamscore=0
 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1
 engine=8.12.0-2202240000 definitions=main-2205160091
X-Proofpoint-GUID: yQg_XaNzmgEyh--YBNbdb2uxZkJd1LLY
X-Proofpoint-ORIG-GUID: yQg_XaNzmgEyh--YBNbdb2uxZkJd1LLY
X-Spam-Status: No, score=-3.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,
        DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,NICE_REPLY_A,RCVD_IN_DNSWL_LOW,
        SPF_HELO_NONE,SPF_NONE,T_SCC_BODY_TEXT_LINE autolearn=ham
        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/16/22 1:59 AM, Juergen Gross wrote:
> On 14.05.22 04:34, Boris Ostrovsky wrote:
>>
>>
>> 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.
> 
> You meant 10, 2, 12, 3, 11, I guess?
> 
>>
>> What will this look like after the 2 iterations of the outer loop?
> 
> idx    ..    2    3  ...  10  11  12
> 
> grant        3   10       11  12  -1
> 
> with gnttab_free_head being 2, i.e the free list is now 2, 3, 10, 11, 12.


OK, thanks, that helped. I couldn't link the free chunks in my head


With the error handling in gnttab_init() fixed

Reviewed-by: Boris Ostrovsky <boris.ostrovsky@oracle.com>


-boris