Subject: Re: [PATCH v7 05/10] iommu/dma-reserved-iommu: reserved binding
 rb-tree and helpers
To: Robin Murphy <robin.murphy@arm.com>, eric.auger@st.com,
        alex.williamson@redhat.com, will.deacon@arm.com, joro@8bytes.org,
        tglx@linutronix.de, jason@lakedaemon.net, marc.zyngier@arm.com,
        christoffer.dall@linaro.org, linux-arm-kernel@lists.infradead.org
References: <1461084994-2355-1-git-send-email-eric.auger@linaro.org>
 <1461084994-2355-6-git-send-email-eric.auger@linaro.org>
 <5717805A.3070602@arm.com>
Cc: patches@linaro.org, linux-kernel@vger.kernel.org,
        Bharat.Bhushan@freescale.com, pranav.sawargaonkar@gmail.com,
        p.fedin@samsung.com, iommu@lists.linux-foundation.org,
        Jean-Philippe.Brucker@arm.com, julien.grall@arm.com
From: Eric Auger <eric.auger@linaro.org>
Message-ID: <5717ABF2.1030204@linaro.org>
Date: Wed, 20 Apr 2016 18:18:58 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
 Thunderbird/38.6.0
MIME-Version: 1.0
In-Reply-To: <5717805A.3070602@arm.com>
Content-Type: text/plain; charset=windows-1252
Content-Transfer-Encoding: 7bit
Sender: linux-kernel-owner@vger.kernel.org
Content-Length: 3961
Lines: 124

Robin,
On 04/20/2016 03:12 PM, Robin Murphy wrote:
> On 19/04/16 17:56, Eric Auger wrote:
>> we will need to track which host physical addresses are mapped to
>> reserved IOVA. In that prospect we introduce a new RB tree indexed
>> by physical address. This RB tree only is used for reserved IOVA
>> bindings.
>>
>> It is expected this RB tree will contain very few bindings.
> 
> Sounds like a good reason in favour of using a list, and thus having
> rather less code here ;)

OK will move to a simple list.
> 
>>  Those
>> generally correspond to single page mapping one MSI frame (GICv2m
>> frame or ITS GITS_TRANSLATER frame).
>>
>> Signed-off-by: Eric Auger <eric.auger@linaro.org>
>>
>> ---
>> v5 -> v6:
>> - add comment about @d->reserved_lock to be held
>>
>> v3 -> v4:
>> - that code was formerly in "iommu/arm-smmu: add a reserved binding RB
>> tree"
>> ---
>>   drivers/iommu/dma-reserved-iommu.c | 63
>> ++++++++++++++++++++++++++++++++++++++
>>   1 file changed, 63 insertions(+)
>>
>> diff --git a/drivers/iommu/dma-reserved-iommu.c
>> b/drivers/iommu/dma-reserved-iommu.c
>> index 2562af0..f6fa18e 100644
>> --- a/drivers/iommu/dma-reserved-iommu.c
>> +++ b/drivers/iommu/dma-reserved-iommu.c
>> @@ -23,6 +23,69 @@ struct reserved_iova_domain {
>>       int prot; /* iommu protection attributes to be obeyed */
>>   };
>>
>> +struct iommu_reserved_binding {
>> +    struct kref        kref;
>> +    struct rb_node        node;
>> +    struct iommu_domain    *domain;
> 
> Hang on, the tree these are in is already embedded in a domain. Ergo we
> can't look them up without first knowing the domain they belong to, so
> what purpose does this guy serve?
this is used on the kref_put. The release function takes a kref; then we
get the container to retrieve the binding and storing the domain here
enables to unlink the node.

Best Regards

Eric
> 
> Robin.
> 
>> +    phys_addr_t        addr;
>> +    dma_addr_t        iova;
>> +    size_t            size;
>> +};
>> +
>> +/* Reserved binding RB-tree manipulation */
>> +
>> +/* @d->reserved_lock must be held */
>> +static struct iommu_reserved_binding *find_reserved_binding(
>> +                    struct iommu_domain *d,
>> +                    phys_addr_t start, size_t size)
>> +{
>> +    struct rb_node *node = d->reserved_binding_list.rb_node;
>> +
>> +    while (node) {
>> +        struct iommu_reserved_binding *binding =
>> +            rb_entry(node, struct iommu_reserved_binding, node);
>> +
>> +        if (start + size <= binding->addr)
>> +            node = node->rb_left;
>> +        else if (start >= binding->addr + binding->size)
>> +            node = node->rb_right;
>> +        else
>> +            return binding;
>> +    }
>> +
>> +    return NULL;
>> +}
>> +
>> +/* @d->reserved_lock must be held */
>> +static void link_reserved_binding(struct iommu_domain *d,
>> +                  struct iommu_reserved_binding *new)
>> +{
>> +    struct rb_node **link = &d->reserved_binding_list.rb_node;
>> +    struct rb_node *parent = NULL;
>> +    struct iommu_reserved_binding *binding;
>> +
>> +    while (*link) {
>> +        parent = *link;
>> +        binding = rb_entry(parent, struct iommu_reserved_binding,
>> +                   node);
>> +
>> +        if (new->addr + new->size <= binding->addr)
>> +            link = &(*link)->rb_left;
>> +        else
>> +            link = &(*link)->rb_right;
>> +    }
>> +
>> +    rb_link_node(&new->node, parent, link);
>> +    rb_insert_color(&new->node, &d->reserved_binding_list);
>> +}
>> +
>> +/* @d->reserved_lock must be held */
>> +static void unlink_reserved_binding(struct iommu_domain *d,
>> +                    struct iommu_reserved_binding *old)
>> +{
>> +    rb_erase(&old->node, &d->reserved_binding_list);
>> +}
>> +
>>   int iommu_alloc_reserved_iova_domain(struct iommu_domain *domain,
>>                        dma_addr_t iova, size_t size, int prot,
>>                        unsigned long order)
>>
>