From patchwork Thu May 5 12:39:47 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Tim Gardner X-Patchwork-Id: 1626943 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=fail reason="signature verification failed" (2048-bit key; unprotected) header.d=canonical.com header.i=@canonical.com header.a=rsa-sha256 header.s=20210705 header.b=ESLIx5Iv; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=lists.ubuntu.com (client-ip=91.189.94.19; helo=huckleberry.canonical.com; envelope-from=kernel-team-bounces@lists.ubuntu.com; receiver=) Received: from huckleberry.canonical.com (huckleberry.canonical.com [91.189.94.19]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4KvCvs71C7z9sBF for ; Thu, 5 May 2022 22:40:09 +1000 (AEST) Received: from localhost ([127.0.0.1] helo=huckleberry.canonical.com) by huckleberry.canonical.com with esmtp (Exim 4.86_2) (envelope-from ) id 1nmam4-0007tO-Hq; Thu, 05 May 2022 12:40:04 +0000 Received: from smtp-relay-internal-1.internal ([10.131.114.114] helo=smtp-relay-internal-1.canonical.com) by huckleberry.canonical.com with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.86_2) (envelope-from ) id 1nmam1-0007sN-U1 for kernel-team@lists.ubuntu.com; Thu, 05 May 2022 12:40:01 +0000 Received: from mail-pf1-f197.google.com (mail-pf1-f197.google.com [209.85.210.197]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by smtp-relay-internal-1.canonical.com (Postfix) with ESMTPS id 8C9053F21E for ; Thu, 5 May 2022 12:40:01 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=canonical.com; s=20210705; t=1651754401; bh=rCR4AMSJ7IltwQ6EXiHRROfri6BaMTEbQiKLJ9HTGTE=; h=From:To:Cc:Subject:Date:Message-Id:In-Reply-To:References: MIME-Version; b=ESLIx5IvLC8/3gsKcfdmS6E6ouUX/kN2Kje2mO0wHhq74lW3TU7BKPKrjj3imT56b WFXasUE+sOsjiRo2ZlGreuT6iBb08yxHL3ERnZVqga+H/n7iDXuj0itxBxgWCXOjNQ +MeK1zkbk5HM4+nzU8ICb9z4x3zlar7sXpCs9YbzQwbO8S5VkJWjOTFqsWGYWSV5uM kXDcRm/T0SJM0qQvMqh9cCz8T0/v00+3aQbdSIfw/I5OmDrl6sDVl1X6swZiH/I6Uc xLBe/QgnhOXJtxpdCAqODWhM8nYx+AQfBcVfkqlxhaRmM9gfli9aNoGtZOH2GCHwR7 fGZMvY/UgUmKA== Received: by mail-pf1-f197.google.com with SMTP id d6-20020aa78e46000000b0050cfcce2fefso1032352pfr.18 for ; Thu, 05 May 2022 05:40:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:from:to:cc:subject:date:message-id:in-reply-to :references:mime-version:content-transfer-encoding; bh=rCR4AMSJ7IltwQ6EXiHRROfri6BaMTEbQiKLJ9HTGTE=; b=13F31nBInSDRRhu8DHbFTEEb4qVprrcsvHZ/B98OXzSWgofphy0ynt1iLi/D5scJGB 9Peo3yPyXiHGV7m+7vAf1gFjctd40BFLWRnlH2dbsKdpHEaEdD2ih3Vf4fPqXpvSM2kq YM8UQjoteO8iHL7g6r7DuTJA7YPKM7NyWyL2c4K7iYN9ZPaZGtyqaa7fT+QqoiDpfFxH LuH4xpKIadDWMVP9dntaohUz6Ye6Xh8nQj+iYyy62DTzBng8/cYe17GdcRCZE2uf75ik Z/qvJE6dkfxMzufvgNNnm8caMAk460I+Pm+WYZ/f4zm4wVk0QaeRIaOG/rri7OrRnAex lsag== X-Gm-Message-State: AOAM5306rVEE0igHZq70m7pIFzJQW6e7oU5JY/CKf8LXrEbQRvxeiOp3 DzK3oWXbqokL3gu3ylRybk1fren/2UjnAtt1owo10QFcicD8oEAJBDdznpe/R8m3npYL19M0YEG vdPChLKLTW+8qJIrjMW759Au+BKDR0niXCyBXNP+XHw== X-Received: by 2002:a63:6a88:0:b0:3c1:4a6c:be3 with SMTP id f130-20020a636a88000000b003c14a6c0be3mr21536242pgc.13.1651754399330; Thu, 05 May 2022 05:39:59 -0700 (PDT) X-Google-Smtp-Source: ABdhPJyGNHvKVrsqG+amuAnPHFrc8BzI9MZyCBdxS6B81YlubRUQEsnXVSkUDaxPJDqs6NhxhGDDDQ== X-Received: by 2002:a63:6a88:0:b0:3c1:4a6c:be3 with SMTP id f130-20020a636a88000000b003c14a6c0be3mr21536220pgc.13.1651754398993; Thu, 05 May 2022 05:39:58 -0700 (PDT) Received: from localhost.localdomain ([69.163.84.166]) by smtp.gmail.com with ESMTPSA id o12-20020a170902bccc00b0015ec71f72d6sm1403744pls.253.2022.05.05.05.39.58 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 05 May 2022 05:39:58 -0700 (PDT) From: Tim Gardner To: kernel-team@lists.ubuntu.com Subject: [PATCH 2/4] UBUNTU: SAUCE: swiotlb: use bitmap to track free slots Date: Thu, 5 May 2022 06:39:47 -0600 Message-Id: <20220505123949.12030-3-tim.gardner@canonical.com> X-Mailer: git-send-email 2.36.0 In-Reply-To: <20220505123949.12030-1-tim.gardner@canonical.com> References: <20220505123949.12030-1-tim.gardner@canonical.com> MIME-Version: 1.0 X-BeenThere: kernel-team@lists.ubuntu.com X-Mailman-Version: 2.1.20 Precedence: list List-Id: Kernel team discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: kernel-team-bounces@lists.ubuntu.com Sender: "kernel-team" From: Chao Gao BugLink: https://bugs.launchpad.net/bugs/1971701 Currently, each slot tracks the number of contiguous free slots starting from itself. It helps to quickly check if there are enough contiguous entries when dealing with an allocation request. But maintaining this information can leads to some overhead. Specifically, if a slot is allocated/freed, preceding slots may need to be updated as the number of contiguous free slots can change. This process may access memory scattering over multiple cachelines. To reduce the overhead of maintaining the number of contiguous free entries, use a global bitmap to track free slots; each bit represents if a slot is available. The number of contiguous free slots can be calculated by counting the number of consecutive 1s in the bitmap. Tests show that the average cost of freeing slots drops by 120 cycles while the average cost of allocation increases by 20 cycles. Overall, 100 cycles are saved from a pair of allocation and freeing. Signed-off-by: Chao Gao (cherry picked from commit d1320673ea2565f5d64e9ef57f8ec3221b3a3b92 https://github.com/intel/tdx.git) Signed-off-by: Tim Gardner --- include/linux/swiotlb.h | 6 ++-- kernel/dma/swiotlb.c | 62 +++++++++++++++++++---------------------- 2 files changed, 32 insertions(+), 36 deletions(-) diff --git a/include/linux/swiotlb.h b/include/linux/swiotlb.h index a93856650b4d..47758796d2c0 100644 --- a/include/linux/swiotlb.h +++ b/include/linux/swiotlb.h @@ -80,8 +80,6 @@ extern enum swiotlb_force swiotlb_force; * @end. For default swiotlb, this is command line adjustable via * setup_io_tlb_npages. * @used: The number of used IO TLB block. - * @list: The free list describing the number of free entries available - * from each index. * @index: The index to start searching in the next round. * @orig_addr: The original address corresponding to a mapped entry. * @alloc_size: Size of the allocated buffer. @@ -91,6 +89,8 @@ extern enum swiotlb_force swiotlb_force; * @late_alloc: %true if allocated using the page allocator * @force_bounce: %true if swiotlb bouncing is forced * @for_alloc: %true if the pool is used for memory allocation + * @bitmap: The bitmap used to track free entries. 1 in bit X means the slot + * indexed by X is free. */ struct io_tlb_mem { phys_addr_t start; @@ -107,8 +107,8 @@ struct io_tlb_mem { struct io_tlb_slot { phys_addr_t orig_addr; size_t alloc_size; - unsigned int list; } *slots; + unsigned long *bitmap; }; extern struct io_tlb_mem io_tlb_default_mem; diff --git a/kernel/dma/swiotlb.c b/kernel/dma/swiotlb.c index 1bf993d1f97d..55cd20f068fd 100644 --- a/kernel/dma/swiotlb.c +++ b/kernel/dma/swiotlb.c @@ -235,7 +235,7 @@ static void swiotlb_init_io_tlb_mem(struct io_tlb_mem *mem, phys_addr_t start, spin_lock_init(&mem->lock); for (i = 0; i < mem->nslabs; i++) { - mem->slots[i].list = IO_TLB_SEGSIZE - io_tlb_offset(i); + __set_bit(i, mem->bitmap); mem->slots[i].orig_addr = INVALID_PHYS_ADDR; mem->slots[i].alloc_size = 0; } @@ -270,6 +270,11 @@ int __init swiotlb_init_with_tbl(char *tlb, unsigned long nslabs, int verbose) panic("%s: Failed to allocate %zu bytes align=0x%lx\n", __func__, alloc_size, PAGE_SIZE); + mem->bitmap = memblock_alloc(DIV_ROUND_UP(nslabs, BITS_PER_BYTE), SMP_CACHE_BYTES); + if (!mem->bitmap) + panic("%s: Failed to allocate %lu bytes align=0x%x\n", + __func__, DIV_ROUND_UP(nslabs, BITS_PER_BYTE), SMP_CACHE_BYTES); + swiotlb_init_io_tlb_mem(mem, __pa(tlb), nslabs, false); if (verbose) @@ -373,10 +378,14 @@ swiotlb_late_init_with_tbl(char *tlb, unsigned long nslabs) if (WARN_ON_ONCE(mem->nslabs)) return -ENOMEM; + mem->bitmap = kzalloc(DIV_ROUND_UP(nslabs, BITS_PER_BYTE), GFP_KERNEL); mem->slots = (void *)__get_free_pages(GFP_KERNEL | __GFP_ZERO, get_order(array_size(sizeof(*mem->slots), nslabs))); - if (!mem->slots) + if (!mem->slots || !mem->bitmap) { + kfree(mem->bitmap); + kfree(mem->slots); return -ENOMEM; + } set_memory_decrypted((unsigned long)tlb, bytes >> PAGE_SHIFT); swiotlb_init_io_tlb_mem(mem, virt_to_phys(tlb), nslabs, true); @@ -529,7 +538,7 @@ static int swiotlb_find_slots(struct device *dev, phys_addr_t orig_addr, unsigned int iotlb_align_mask = dma_get_min_align_mask(dev) & ~(IO_TLB_SIZE - 1); unsigned int nslots = nr_slots(alloc_size), stride; - unsigned int index, wrap, count = 0, i; + unsigned int index, wrap, i; unsigned int offset = swiotlb_align_offset(dev, orig_addr); unsigned long flags; @@ -557,6 +566,12 @@ static int swiotlb_find_slots(struct device *dev, phys_addr_t orig_addr, continue; } + /* Start from the next segment if no enough free entries */ + if (io_tlb_offset(index) + nslots > IO_TLB_SEGSIZE) { + index = wrap_index(mem, round_up(index, IO_TLB_SEGSIZE)); + continue; + } + /* * If we find a slot that indicates we have 'nslots' number of * contiguous buffers, we allocate the buffers from that slot @@ -565,7 +580,8 @@ static int swiotlb_find_slots(struct device *dev, phys_addr_t orig_addr, if (!iommu_is_span_boundary(index, nslots, nr_slots(tbl_dma_addr), max_slots)) { - if (mem->slots[index].list >= nslots) + if (find_next_zero_bit(mem->bitmap, index + nslots, index) == + index + nslots) goto found; } index = wrap_index(mem, index + stride); @@ -577,14 +593,10 @@ static int swiotlb_find_slots(struct device *dev, phys_addr_t orig_addr, found: for (i = index; i < index + nslots; i++) { - mem->slots[i].list = 0; + __clear_bit(i, mem->bitmap); mem->slots[i].alloc_size = alloc_size - (offset + ((i - index) << IO_TLB_SHIFT)); } - for (i = index - 1; - io_tlb_offset(i) != IO_TLB_SEGSIZE - 1 && - mem->slots[i].list; i--) - mem->slots[i].list = ++count; /* * Update the indices to avoid searching in the next round. @@ -656,38 +668,19 @@ static void swiotlb_release_slots(struct device *dev, phys_addr_t tlb_addr) unsigned int offset = swiotlb_align_offset(dev, tlb_addr); int index = (tlb_addr - offset - mem->start) >> IO_TLB_SHIFT; int nslots = nr_slots(mem->slots[index].alloc_size + offset); - int count, i; + int i; - /* - * Return the buffer to the free list by setting the corresponding - * entries to indicate the number of contiguous entries available. - * While returning the entries to the free list, we merge the entries - * with slots below and above the pool being returned. - */ spin_lock_irqsave(&mem->lock, flags); - if (index + nslots < ALIGN(index + 1, IO_TLB_SEGSIZE)) - count = mem->slots[index + nslots].list; - else - count = 0; - /* - * Step 1: return the slots to the free list, merging the slots with - * superceeding slots + * Return the slots to swiotlb, updating bitmap to indicate + * corresponding entries are free. */ for (i = index + nslots - 1; i >= index; i--) { - mem->slots[i].list = ++count; + __set_bit(i, mem->bitmap); mem->slots[i].orig_addr = INVALID_PHYS_ADDR; mem->slots[i].alloc_size = 0; } - /* - * Step 2: merge the returned slots with the preceding slots, if - * available (non zero) - */ - for (i = index - 1; - io_tlb_offset(i) != IO_TLB_SEGSIZE - 1 && mem->slots[i].list; - i--) - mem->slots[i].list = ++count; mem->used -= nslots; spin_unlock_irqrestore(&mem->lock, flags); } @@ -864,9 +857,12 @@ static int rmem_swiotlb_device_init(struct reserved_mem *rmem, if (!mem) return -ENOMEM; + mem->bitmap = kzalloc(DIV_ROUND_UP(nslabs, BITS_PER_BYTE), GFP_KERNEL); mem->slots = kzalloc(array_size(sizeof(*mem->slots), nslabs), GFP_KERNEL); - if (!mem->slots) { + if (!mem->slots || !mem->bitmap) { + kfree(mem->slots); + kfree(mem->bitmap); kfree(mem); return -ENOMEM; }