Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Sultan Alsawaf <sultan@kerneltoast.com>
Cc:     Sultan Alsawaf <sultan@kerneltoast.com>,
        Jason Gunthorpe <jgg@ziepe.ca>,
        "Martin K. Petersen" <martin.petersen@oracle.com>,
        Thomas Hellstrom <thellstrom@vmware.com>,
        Palmer Dabbelt <palmer@sifive.com>,
        Sakari Ailus <sakari.ailus@linux.intel.com>,
        Ming Lei <ming.lei@redhat.com>,
        Gal Pressman <galpress@amazon.com>,
        linux-kernel@vger.kernel.org
Subject: [PATCH] scatterlist: Speed up for_each_sg() loop macro
Date:   Fri, 25 Oct 2019 14:33:58 -0700
Message-Id: <20191025213359.7538-1-sultan@kerneltoast.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
To:     unlisted-recipients:; (no To-header on input)
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

From: Sultan Alsawaf <sultan@kerneltoast.com>

Scatterlists are chained in predictable arrays of up to
SG_MAX_SINGLE_ALLOC sg structs in length. Using this knowledge, speed up
for_each_sg() by using constant operations to determine when to simply
increment the sg pointer by one or get the next sg array in the chain.

Rudimentary measurements with a trivial loop body show that this yields
roughly a 2x performance gain.

The following simple test module proves the correctness of the new loop
definition by testing all the different edge cases of sg chains:
#include <linux/module.h>
#include <linux/scatterlist.h>
#include <linux/slab.h>

static int __init test_for_each_sg(void)
{
	static const gfp_t gfp_flags = GFP_KERNEL | __GFP_NOFAIL;
        struct scatterlist *sg;
        struct sg_table *table;
        long old = 0, new = 0;
        unsigned int i, nents;

        table = kmalloc(sizeof(*table), gfp_flags);
        for (nents = 1; nents <= 3 * SG_MAX_SINGLE_ALLOC; nents++) {
                BUG_ON(sg_alloc_table(table, nents, gfp_flags));
                for (sg = table->sgl; sg; sg = sg_next(sg))
                        old ^= (long)sg;
                for_each_sg(table->sgl, sg, nents, i)
                        new ^= (long)sg;
                sg_free_table(table);
        }

        BUG_ON(old != new);
        kfree(table);
        return 0;
}
module_init(test_for_each_sg);

Signed-off-by: Sultan Alsawaf <sultan@kerneltoast.com>
---
 include/linux/scatterlist.h | 5 ++++-
 1 file changed, 4 insertions(+), 1 deletion(-)

diff --git a/include/linux/scatterlist.h b/include/linux/scatterlist.h
index 556ec1ea2574..73f7fd6702d7 100644
--- a/include/linux/scatterlist.h
+++ b/include/linux/scatterlist.h
@@ -146,7 +146,10 @@ static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
  * Loop over each sg element, following the pointer to a new list if necessary
  */
 #define for_each_sg(sglist, sg, nr, __i)	\
-	for (__i = 0, sg = (sglist); __i < (nr); __i++, sg = sg_next(sg))
+	for (__i = 0, sg = (sglist); __i < (nr);		\
+	     likely(++__i % (SG_MAX_SINGLE_ALLOC - 1) ||	\
+		    (__i + 1) >= (nr)) ? sg++ :			\
+		    (sg = sg_chain_ptr(sg + 1)))
 
 /**
  * sg_chain - Chain two sglists together
-- 
2.23.0