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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 16 May 2022 07:59:45 +0200
From:   Juergen Gross <jgross@...e.com>
To:     Boris Ostrovsky <boris.ostrovsky@...cle.com>,
        Oleksandr Tyshchenko <olekstysh@...il.com>,
        xen-devel@...ts.xenproject.org, linux-kernel@...r.kernel.org,
        linux-arm-kernel@...ts.infradead.org
Cc:     Stefano Stabellini <sstabellini@...nel.org>,
        Julien Grall <julien@....org>,
        Oleksandr Tyshchenko <oleksandr_tyshchenko@...m.com>,
        "Michael S. Tsirkin" <mst@...hat.com>,
        Christoph Hellwig <hch@...radead.org>
Subject: Re: [PATCH V2 2/7] xen/grants: support allocating consecutive grants

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.


Juergen

Download attachment "OpenPGP_0xB0DE9DD628BF132F.asc" of type "application/pgp-keys" (3099 bytes)

Download attachment "OpenPGP_signature" of type "application/pgp-signature" (496 bytes)