From patchwork Wed May 11 12:15:41 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Ajay Kumar X-Patchwork-Id: 12846975 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.lore.kernel.org (Postfix) with ESMTPS id E10A6C433EF for ; Thu, 12 May 2022 03:41:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=lists.infradead.org; s=bombadil.20210309; h=Sender: Content-Transfer-Encoding:Content-Type:MIME-Version:List-Subscribe:List-Help: List-Post:List-Archive:List-Unsubscribe:List-Id:References:In-Reply-To: Message-Id:Date:Subject:Cc:To:From:Reply-To:Content-ID:Content-Description: Resent-Date:Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID: List-Owner; bh=072M3BIey1JfHRoC2JeM2omtEwPVuMN+pQjCJaHT1nE=; b=z6jrrT5foQh+Wo y32hVlbViol38zi6TWbISaD8F0n08iP0DQK+VsD5ZFTvRAoLEHlrt5lTuOzadhTXFFO5gmhDfp6ww P7x/JLZIpi1cThss+lR4+o8LiRK5Oit57YcSzT5TTMJDvB7kCpxowOjnXOFAJU+rKyH55j8yRaZms s+CqO97qiMG1xDqf9FEV6VMdakGg6f62d7i+lGjYQZwI6ZjXq3+a+6NC83Rwb7MzIxW+mqWmRfJuQ D3IbsuRQU9mb1CbhTxiMC0AFgYqyyiK5GcjwynTXH0/gHGF8aVS/GB+W+rDJvUDCwS9j5cOhL7CEz fK1Hn7QRqk+Dg8fQr4xQ==; Received: from localhost ([::1] helo=bombadil.infradead.org) by bombadil.infradead.org with esmtp (Exim 4.94.2 #2 (Red Hat Linux)) id 1nozgB-009i4b-UE; Thu, 12 May 2022 03:39:56 +0000 Received: from mailout2.samsung.com ([203.254.224.25]) by bombadil.infradead.org with esmtps (Exim 4.94.2 #2 (Red Hat Linux)) id 1nozfl-009hvg-FS for linux-arm-kernel@lists.infradead.org; Thu, 12 May 2022 03:39:31 +0000 Received: from epcas5p1.samsung.com (unknown [182.195.41.39]) by mailout2.samsung.com (KnoxPortal) with ESMTP id 20220512033926epoutp024abcfdba2a475125cf8324b11e102482~uPnCYcwi33248032480epoutp02a for ; Thu, 12 May 2022 03:39:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 mailout2.samsung.com 20220512033926epoutp024abcfdba2a475125cf8324b11e102482~uPnCYcwi33248032480epoutp02a DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=samsung.com; s=mail20170921; t=1652326766; bh=j7H+lYgLrxIwd/UWGDzvCeRAYA20sZX74We4b9F9RWw=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=Tc3u/bIH/OxEcctZtanwOGle1z0FER8kMaWyCtPCNbPCPAgI8U75uwQWZMOuICr41 qnQnCzJmtSnVrjudWcgxuds4oqwT1eEbFfk8X/tqrskVL+OYK9ASh+ho/OfTHt5pup ThpsAyDdmeFd47YZpvbbdsa99/0Ftt3sxWpEnKj0= Received: from epsnrtp3.localdomain (unknown [182.195.42.164]) by epcas5p1.samsung.com (KnoxPortal) with ESMTP id 20220512033926epcas5p1f24cee324a020438f0c120d6eb214304~uPnCD3MpP0057600576epcas5p1C; Thu, 12 May 2022 03:39:26 +0000 (GMT) Received: from epsmges5p3new.samsung.com (unknown [182.195.38.174]) by epsnrtp3.localdomain (Postfix) with ESMTP id 4KzHZf42v4z4x9Pr; Thu, 12 May 2022 03:39:22 +0000 (GMT) Received: from epcas5p2.samsung.com ( [182.195.41.40]) by epsmges5p3new.samsung.com (Symantec Messaging Gateway) with SMTP id 6A.A6.09762.9618C726; Thu, 12 May 2022 12:39:21 +0900 (KST) Received: from epsmtrp1.samsung.com (unknown [182.195.40.13]) by epcas5p2.samsung.com (KnoxPortal) with ESMTPA id 20220511121437epcas5p29d2210065b47346840c9c6ac14b0e585~uC-jtXoHL2858628586epcas5p2y; Wed, 11 May 2022 12:14:37 +0000 (GMT) Received: from epsmgms1p1new.samsung.com (unknown [182.195.42.41]) by epsmtrp1.samsung.com (KnoxPortal) with ESMTP id 20220511121437epsmtrp1b387b23b145dd996fa4816ef8f52b71a~uC-jshRt_0052800528epsmtrp1H; Wed, 11 May 2022 12:14:37 +0000 (GMT) X-AuditID: b6c32a4b-213ff70000002622-40-627c81690c8c Received: from epsmtip2.samsung.com ( [182.195.34.31]) by epsmgms1p1new.samsung.com (Symantec Messaging Gateway) with SMTP id 79.0F.11276.CA8AB726; Wed, 11 May 2022 21:14:36 +0900 (KST) Received: from Jaguar.sa.corp.samsungelectronics.net (unknown [107.108.73.139]) by epsmtip2.samsung.com (KnoxPortal) with ESMTPA id 20220511121435epsmtip2552daaded7e433543c05e9341576f16d~uC-iNLKKW0495704957epsmtip26; Wed, 11 May 2022 12:14:35 +0000 (GMT) From: Ajay Kumar To: linux-arm-kernel@lists.infradead.org, iommu@lists.linux-foundation.org, joro@8bytes.org, will@kernel.org, robin.murphy@arm.com Cc: alim.akhtar@samsung.com, pankaj.dubey@samsung.com, ajaykumar.rs1989@gmail.com, Marek Szyprowski , Ajay Kumar Subject: [PATCH V2 3/6] iommu: iova: add support for 'first-fit' algorithm Date: Wed, 11 May 2022 17:45:41 +0530 Message-Id: <20220511121544.5998-4-ajaykumar.rs@samsung.com> X-Mailer: git-send-email 2.17.1 In-Reply-To: <20220511121544.5998-1-ajaykumar.rs@samsung.com> X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFvrJKsWRmVeSWpSXmKPExsWy7bCmhm5mY02SwcEODouvJ36zWRx4f5DF 4sG8bWwWC/ZbW3TO3sBusenxNVaLtUfuslss2vqF3eLghyesFi13TB24PJ4cnMfksWbeGkaP nbPusntsWtXJ5rF5Sb3H5BvLGT36tqxiDGCPyrbJSE1MSS1SSM1Lzk/JzEu3VfIOjneONzUz MNQ1tLQwV1LIS8xNtVVy8QnQdcvMAbpOSaEsMacUKBSQWFyspG9nU5RfWpKqkJFfXGKrlFqQ klNgUqBXnJhbXJqXrpeXWmJlaGBgZApUmJCdcX7pQ5aCD3IVJ5qXMjYwbpbsYuTkkBAwkXj+ 4gNzFyMXh5DAbkaJSYd/sUA4nxiBMr+hnG+MEkt2rmaFabnauBYqsZdRYtbr/ewQTguTRNPr K+wgVWwC2hLbpt9kAbFFBFoYJeZOswcpYhZYCTTqVgdYkbCAl0Tr8kdMIDaLgKrEmY7JYCt4 BWwk+q9/YIFYJy+xesMBZhCbU8BWYtKOv4wggyQE3rJLTJu1GarIRWL6mWnsELawxKvjW6Bs KYmX/W1QdrXEuVv72SCaOxglOh6ug0rYSxy4MgdoEAfQeZoS63fpQ4RlJaaeWgd2HLMAn0Tv 7ydMEHFeiR3zQGwOIFtNYusKP4iwjMSZg1egSjwk1q5uZ4KEygRGiV29R1gnMMrNQtiwgJFx FaNkakFxbnpqsWmBcV5qOTzekvNzNzGC06CW9w7GRw8+6B1iZOJgPMQowcGsJMK7v68iSYg3 JbGyKrUoP76oNCe1+BCjKTAAJzJLiSbnAxNxXkm8oYmlgYmZmZmJpbGZoZI476n0DYlCAumJ JanZqakFqUUwfUwcnFINTNGvfLvZGDOvqOXs6NmtdvIsmx+TwToPjysnQrQZX9xZJrnow8Nv Cn/Dmv7u+HClsK0zdkLBqTVNMTs+vZeQnGFyuOF1tmaZyPtrV6QeZ3j2OnO3p93PFGZe9MZs 9tqNF9NOf9lu82rfzW9uq2LuTVxeflnI6Ufmg0unF2e82S+a2Sue7xGZdcqyMt+m/2uag9/S Hc+f6E6cYFV+6Lx5x7ysxAmppev+rLL/qFC68PXXjF8d/HWrhV1S/m69bXm95N5JYEJeP6Um PuLpeVWTqNcnFau2XZ31dKJeZ9zdJ7PE5TvWzTiz4sETl6bQUK2ft55fWlhb8S7Z+sNCkYr3 4oYd8c6fXd8fjhBx2ug494wSS3FGoqEWc1FxIgB6OQQCDAQAAA== X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFtrALMWRmVeSWpSXmKPExsWy7bCSvO6aFdVJBmearCy+nvjNZnHg/UEW iwfztrFZLNhvbdE5ewO7xabH11gt1h65y26xaOsXdouDH56wWrTcMXXg8nhycB6Tx5p5axg9 ds66y+6xaVUnm8fmJfUek28sZ/To27KKMYA9issmJTUnsyy1SN8ugSvj/NKHLAUf5CpONC9l bGDcLNnFyMkhIWAicbVxLUsXIxeHkMBuRomVFz6wQSRkJJ7veMoCYQtLrPz3nB2iqIlJYvnS E2AJNgFtiW3Tb4J1iwh0MUpcvbqXFcRhFljLKPGqcQkjSJWwgJdE6/JHTCA2i4CqxJmOyawg Nq+AjUT/9Q9QK+QlVm84wAxicwrYSkza8ResVwioZs7no8wTGPkWMDKsYpRMLSjOTc8tNiww zEst1ytOzC0uzUvXS87P3cQIDlQtzR2M21d90DvEyMTBeIhRgoNZSYR3f19FkhBvSmJlVWpR fnxRaU5q8SFGaQ4WJXHeC10n44UE0hNLUrNTUwtSi2CyTBycUg1M27SetzzTalC8a313HX/8 KcnPvY6ttV565QtqmNtZPx6fNvFLw8zLdzqUz8gfsFtz83iLEsMv6QSDH5YHjiy+NlXUTMFb 8rHjytb8BbF9J3ec+je3tWrH7lhHlRX+d7VYpklqbzANP863xDBcxe9P36QFr+4aOG1v6N3E PDvuZtdMIeaWwNJodRUmA3HLf3MkndTkjpwJmn9B9NJbrmMtC+tvTd/EH/WmuTfE03Vb+sfS aKHao+/m7M9W/SrTePGUy/57QRuvXK38Iff6VIeR8ny9snnPo+wiy68sEHyle6jluXJa7rOi c1c3GZ0Nnf/jf+N7UUummyqp+sw+svXX5wjVM/lMXbp16+7H35WOK7EUZyQaajEXFScCAAiJ x1bDAgAA X-CMS-MailID: 20220511121437epcas5p29d2210065b47346840c9c6ac14b0e585 X-Msg-Generator: CA X-Sendblock-Type: REQ_APPROVE CMS-TYPE: 105P DLP-Filter: Pass X-CFilter-Loop: Reflected X-CMS-RootMailID: 20220511121437epcas5p29d2210065b47346840c9c6ac14b0e585 References: <20220511121544.5998-1-ajaykumar.rs@samsung.com> X-CRM114-Version: 20100106-BlameMichelson ( TRE 0.8.0 (BSD) ) MR-646709E3 X-CRM114-CacheID: sfid-20220511_203929_941286_305C9238 X-CRM114-Status: GOOD ( 20.78 ) X-BeenThere: linux-arm-kernel@lists.infradead.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: "linux-arm-kernel" Errors-To: linux-arm-kernel-bounces+linux-arm-kernel=archiver.kernel.org@lists.infradead.org From: Marek Szyprowski Add support for the 'first-fit' allocation algorithm. It will be used for the special case of implementing DMA_ATTR_LOW_ADDRESS, so this path doesn't use IOVA cache. Signed-off-by: Marek Szyprowski Signed-off-by: Ajay Kumar --- drivers/iommu/iova.c | 78 ++++++++++++++++++++++++++++++++++++++++++++ include/linux/iova.h | 2 ++ 2 files changed, 80 insertions(+) diff --git a/drivers/iommu/iova.c b/drivers/iommu/iova.c index ae0fe0a6714e..89f9338f83a3 100644 --- a/drivers/iommu/iova.c +++ b/drivers/iommu/iova.c @@ -231,6 +231,59 @@ static int __alloc_and_insert_iova_range(struct iova_domain *iovad, return -ENOMEM; } +static unsigned long +__iova_get_aligned_start(unsigned long start, unsigned long size) +{ + unsigned long mask = __roundup_pow_of_two(size) - 1; + + return (start + mask) & ~mask; +} + +static int __alloc_and_insert_iova_range_forward(struct iova_domain *iovad, + unsigned long size, unsigned long limit_pfn, + struct iova *new) +{ + struct rb_node *curr; + unsigned long flags; + unsigned long start, limit; + + spin_lock_irqsave(&iovad->iova_rbtree_lock, flags); + + curr = rb_first(&iovad->rbroot); + limit = limit_pfn; + start = __iova_get_aligned_start(iovad->start_pfn, size); + + while (curr) { + struct iova *curr_iova = rb_entry(curr, struct iova, node); + struct rb_node *next = rb_next(curr); + + start = __iova_get_aligned_start(curr_iova->pfn_hi + 1, size); + if (next) { + struct iova *next_iova = rb_entry(next, struct iova, node); + limit = next_iova->pfn_lo - 1; + } else { + limit = limit_pfn; + } + + if ((start + size) <= limit) + break; /* found a free slot */ + curr = next; + } + + if (!curr && start + size > limit) { + spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); + return -ENOMEM; + } + + new->pfn_lo = start; + new->pfn_hi = new->pfn_lo + size - 1; + iova_insert_rbtree(&iovad->rbroot, new, curr); + + spin_unlock_irqrestore(&iovad->iova_rbtree_lock, flags); + + return 0; +} + static struct kmem_cache *iova_cache; static unsigned int iova_cache_users; static DEFINE_MUTEX(iova_cache_mutex); @@ -420,6 +473,31 @@ free_iova(struct iova_domain *iovad, unsigned long pfn) } EXPORT_SYMBOL_GPL(free_iova); +/** + * alloc_iova_first_fit - allocates an iova from the beginning of address space + * @iovad: - iova domain in question + * @size: - size of page frames to allocate + * @limit_pfn: - max limit address + * Returns a pfn the allocated iova starts at or IOVA_BAD_ADDR in the case + * of a failure. + */ +unsigned long +alloc_iova_first_fit(struct iova_domain *iovad, unsigned long size, + unsigned long limit_pfn) +{ + struct iova *new_iova = alloc_iova_mem(); + + if (!new_iova) + return IOVA_BAD_ADDR; + + if (__alloc_and_insert_iova_range_forward(iovad, size, limit_pfn, new_iova)) { + free_iova_mem(new_iova); + return IOVA_BAD_ADDR; + } + return new_iova->pfn_lo; +} +EXPORT_SYMBOL_GPL(alloc_iova_first_fit); + /** * alloc_iova_fast - allocates an iova from rcache * @iovad: - iova domain in question diff --git a/include/linux/iova.h b/include/linux/iova.h index 46b5b10c532b..45ed6d41490a 100644 --- a/include/linux/iova.h +++ b/include/linux/iova.h @@ -89,6 +89,8 @@ void free_iova_fast(struct iova_domain *iovad, unsigned long pfn, unsigned long size); unsigned long alloc_iova_fast(struct iova_domain *iovad, unsigned long size, unsigned long limit_pfn, bool flush_rcache); +unsigned long alloc_iova_first_fit(struct iova_domain *iovad, unsigned long size, + unsigned long limit_pfn); struct iova *reserve_iova(struct iova_domain *iovad, unsigned long pfn_lo, unsigned long pfn_hi); void init_iova_domain(struct iova_domain *iovad, unsigned long granule,