sys/compat/linuxkpi/common/include/linux/scatterlist.h

   1 /*-
   2  * Copyright (c) 2010 Isilon Systems, Inc.
   3  * Copyright (c) 2010 iX Systems, Inc.
   4  * Copyright (c) 2010 Panasas, Inc.
   5  * Copyright (c) 2013-2017 Mellanox Technologies, Ltd.
   6  * Copyright (c) 2015 Matthew Dillon <dillon@backplane.com>
   7  * All rights reserved.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice unmodified, this list of conditions, and the following
  14  *    disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  20  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  21  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  22  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  23  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  24  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  28  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * $FreeBSD$
  31  */
  32 #ifndef _LINUX_SCATTERLIST_H_
  33 #define _LINUX_SCATTERLIST_H_
  34
  35 #include <linux/page.h>
  36 #include <linux/slab.h>
  37 #include <linux/mm.h>
  38
  39 struct scatterlist {
  40         unsigned long page_link;
  41 #define SG_PAGE_LINK_CHAIN      0x1UL
  42 #define SG_PAGE_LINK_LAST       0x2UL
  43 #define SG_PAGE_LINK_MASK       0x3UL
  44         unsigned int offset;
  45         unsigned int length;
  46         dma_addr_t address;
  47 };
  48
  49 CTASSERT((sizeof(struct scatterlist) & SG_PAGE_LINK_MASK) == 0);
  50
  51 struct sg_table {
  52         struct scatterlist *sgl;
  53         unsigned int nents;
  54         unsigned int orig_nents;
  55 };
  56
  57 struct sg_page_iter {
  58         struct scatterlist *sg;
  59         unsigned int sg_pgoffset;
  60         unsigned int maxents;
  61         struct {
  62                 unsigned int nents;
  63                 int     pg_advance;
  64         } internal;
  65 };
  66
  67 #define SCATTERLIST_MAX_SEGMENT (-1U & ~(PAGE_SIZE - 1))
  68
  69 #define SG_MAX_SINGLE_ALLOC     (PAGE_SIZE / sizeof(struct scatterlist))
  70
  71 #define SG_MAGIC                0x87654321UL
  72
  73 #define sg_is_chain(sg)         ((sg)->page_link & SG_PAGE_LINK_CHAIN)
  74 #define sg_is_last(sg)          ((sg)->page_link & SG_PAGE_LINK_LAST)
  75 #define sg_chain_ptr(sg)        \
  76         ((struct scatterlist *) ((sg)->page_link & ~SG_PAGE_LINK_MASK))
  77
  78 #define sg_dma_address(sg)      (sg)->address
  79 #define sg_dma_len(sg)          (sg)->length
  80
  81 #define for_each_sg_page(sgl, iter, nents, pgoffset)                    \
  82         for (_sg_iter_init(sgl, iter, nents, pgoffset);                 \
  83              (iter)->sg; _sg_iter_next(iter))
  84
  85 #define for_each_sg(sglist, sg, sgmax, iter)                            \
  86         for (iter = 0, sg = (sglist); iter < (sgmax); iter++, sg = sg_next(sg))
  87
  88 typedef struct scatterlist *(sg_alloc_fn) (unsigned int, gfp_t);
  89 typedef void (sg_free_fn) (struct scatterlist *, unsigned int);
  90
  91 static inline void
  92 sg_assign_page(struct scatterlist *sg, struct page *page)
  93 {
  94         unsigned long page_link = sg->page_link & SG_PAGE_LINK_MASK;
  95
  96         sg->page_link = page_link | (unsigned long)page;
  97 }
  98
  99 static inline void
 100 sg_set_page(struct scatterlist *sg, struct page *page, unsigned int len,
 101     unsigned int offset)
 102 {
 103         sg_assign_page(sg, page);
 104         sg->offset = offset;
 105         sg->length = len;
 106 }
 107
 108 static inline struct page *
 109 sg_page(struct scatterlist *sg)
 110 {
 111         return ((struct page *)((sg)->page_link & ~SG_PAGE_LINK_MASK));
 112 }
 113
 114 static inline void
 115 sg_set_buf(struct scatterlist *sg, const void *buf, unsigned int buflen)
 116 {
 117         sg_set_page(sg, virt_to_page(buf), buflen,
 118             ((uintptr_t)buf) & (PAGE_SIZE - 1));
 119 }
 120
 121 static inline struct scatterlist *
 122 sg_next(struct scatterlist *sg)
 123 {
 124         if (sg_is_last(sg))
 125                 return (NULL);
 126         sg++;
 127         if (sg_is_chain(sg))
 128                 sg = sg_chain_ptr(sg);
 129         return (sg);
 130 }
 131
 132 static inline vm_paddr_t
 133 sg_phys(struct scatterlist *sg)
 134 {
 135         return (VM_PAGE_TO_PHYS(sg_page(sg)) + sg->offset);
 136 }
 137
 138 static inline void
 139 sg_chain(struct scatterlist *prv, unsigned int prv_nents,
 140     struct scatterlist *sgl)
 141 {
 142         struct scatterlist *sg = &prv[prv_nents - 1];
 143
 144         sg->offset = 0;
 145         sg->length = 0;
 146         sg->page_link = ((unsigned long)sgl |
 147             SG_PAGE_LINK_CHAIN) & ~SG_PAGE_LINK_LAST;
 148 }
 149
 150 static inline void
 151 sg_mark_end(struct scatterlist *sg)
 152 {
 153         sg->page_link |= SG_PAGE_LINK_LAST;
 154         sg->page_link &= ~SG_PAGE_LINK_CHAIN;
 155 }
 156
 157 static inline void
 158 sg_init_table(struct scatterlist *sg, unsigned int nents)
 159 {
 160         bzero(sg, sizeof(*sg) * nents);
 161         sg_mark_end(&sg[nents - 1]);
 162 }
 163
 164 static struct scatterlist *
 165 sg_kmalloc(unsigned int nents, gfp_t gfp_mask)
 166 {
 167         if (nents == SG_MAX_SINGLE_ALLOC) {
 168                 return ((void *)__get_free_page(gfp_mask));
 169         } else
 170                 return (kmalloc(nents * sizeof(struct scatterlist), gfp_mask));
 171 }
 172
 173 static inline void
 174 sg_kfree(struct scatterlist *sg, unsigned int nents)
 175 {
 176         if (nents == SG_MAX_SINGLE_ALLOC) {
 177                 free_page((unsigned long)sg);
 178         } else
 179                 kfree(sg);
 180 }
 181
 182 static inline void
 183 __sg_free_table(struct sg_table *table, unsigned int max_ents,
 184     bool skip_first_chunk, sg_free_fn * free_fn)
 185 {
 186         struct scatterlist *sgl, *next;
 187
 188         if (unlikely(!table->sgl))
 189                 return;
 190
 191         sgl = table->sgl;
 192         while (table->orig_nents) {
 193                 unsigned int alloc_size = table->orig_nents;
 194                 unsigned int sg_size;
 195
 196                 if (alloc_size > max_ents) {
 197                         next = sg_chain_ptr(&sgl[max_ents - 1]);
 198                         alloc_size = max_ents;
 199                         sg_size = alloc_size - 1;
 200                 } else {
 201                         sg_size = alloc_size;
 202                         next = NULL;
 203                 }
 204
 205                 table->orig_nents -= sg_size;
 206                 if (skip_first_chunk)
 207                         skip_first_chunk = 0;
 208                 else
 209                         free_fn(sgl, alloc_size);
 210                 sgl = next;
 211         }
 212
 213         table->sgl = NULL;
 214 }
 215
 216 static inline void
 217 sg_free_table(struct sg_table *table)
 218 {
 219         __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree);
 220 }
 221
 222 static inline int
 223 __sg_alloc_table(struct sg_table *table, unsigned int nents,
 224     unsigned int max_ents, struct scatterlist *first_chunk,
 225     gfp_t gfp_mask, sg_alloc_fn *alloc_fn)
 226 {
 227         struct scatterlist *sg, *prv;
 228         unsigned int left;
 229
 230         memset(table, 0, sizeof(*table));
 231
 232         if (nents == 0)
 233                 return (-EINVAL);
 234         left = nents;
 235         prv = NULL;
 236         do {
 237                 unsigned int sg_size;
 238                 unsigned int alloc_size = left;
 239
 240                 if (alloc_size > max_ents) {
 241                         alloc_size = max_ents;
 242                         sg_size = alloc_size - 1;
 243                 } else
 244                         sg_size = alloc_size;
 245
 246                 left -= sg_size;
 247
 248                 if (first_chunk) {
 249                         sg = first_chunk;
 250                         first_chunk = NULL;
 251                 } else {
 252                         sg = alloc_fn(alloc_size, gfp_mask);
 253                 }
 254                 if (unlikely(!sg)) {
 255                         if (prv)
 256                                 table->nents = ++table->orig_nents;
 257
 258                         return (-ENOMEM);
 259                 }
 260                 sg_init_table(sg, alloc_size);
 261                 table->nents = table->orig_nents += sg_size;
 262
 263                 if (prv)
 264                         sg_chain(prv, max_ents, sg);
 265                 else
 266                         table->sgl = sg;
 267
 268                 if (!left)
 269                         sg_mark_end(&sg[sg_size - 1]);
 270
 271                 prv = sg;
 272         } while (left);
 273
 274         return (0);
 275 }
 276
 277 static inline int
 278 sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
 279 {
 280         int ret;
 281
 282         ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC,
 283             NULL, gfp_mask, sg_kmalloc);
 284         if (unlikely(ret))
 285                 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree);
 286
 287         return (ret);
 288 }
 289
 290 static inline int
 291 __sg_alloc_table_from_pages(struct sg_table *sgt,
 292     struct page **pages, unsigned int count,
 293     unsigned long off, unsigned long size,
 294     unsigned int max_segment, gfp_t gfp_mask)
 295 {
 296         unsigned int i, segs, cur, len;
 297         int rc;
 298         struct scatterlist *s;
 299
 300         if (__predict_false(!max_segment || offset_in_page(max_segment)))
 301                 return (-EINVAL);
 302
 303         len = 0;
 304         for (segs = i = 1; i < count; ++i) {
 305                 len += PAGE_SIZE;
 306                 if (len >= max_segment ||
 307                     page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) {
 308                         ++segs;
 309                         len = 0;
 310                 }
 311         }
 312         if (__predict_false((rc = sg_alloc_table(sgt, segs, gfp_mask))))
 313                 return (rc);
 314
 315         cur = 0;
 316         for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
 317                 unsigned long seg_size;
 318                 unsigned int j;
 319
 320                 len = 0;
 321                 for (j = cur + 1; j < count; ++j) {
 322                         len += PAGE_SIZE;
 323                         if (len >= max_segment || page_to_pfn(pages[j]) !=
 324                             page_to_pfn(pages[j - 1]) + 1)
 325                                 break;
 326                 }
 327
 328                 seg_size = ((j - cur) << PAGE_SHIFT) - off;
 329                 sg_set_page(s, pages[cur], min(size, seg_size), off);
 330                 size -= seg_size;
 331                 off = 0;
 332                 cur = j;
 333         }
 334         return (0);
 335 }
 336
 337 static inline int
 338 sg_alloc_table_from_pages(struct sg_table *sgt,
 339     struct page **pages, unsigned int count,
 340     unsigned long off, unsigned long size,
 341     gfp_t gfp_mask)
 342 {
 343
 344         return (__sg_alloc_table_from_pages(sgt, pages, count, off, size,
 345             SCATTERLIST_MAX_SEGMENT, gfp_mask));
 346 }
 347
 348 static inline int
 349 sg_nents(struct scatterlist *sg)
 350 {
 351         int nents;
 352
 353         for (nents = 0; sg; sg = sg_next(sg))
 354                 nents++;
 355         return (nents);
 356 }
 357
 358 static inline void
 359 __sg_page_iter_start(struct sg_page_iter *piter,
 360     struct scatterlist *sglist, unsigned int nents,
 361     unsigned long pgoffset)
 362 {
 363         piter->internal.pg_advance = 0;
 364         piter->internal.nents = nents;
 365
 366         piter->sg = sglist;
 367         piter->sg_pgoffset = pgoffset;
 368 }
 369
 370 static inline void
 371 _sg_iter_next(struct sg_page_iter *iter)
 372 {
 373         struct scatterlist *sg;
 374         unsigned int pgcount;
 375
 376         sg = iter->sg;
 377         pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT;
 378
 379         ++iter->sg_pgoffset;
 380         while (iter->sg_pgoffset >= pgcount) {
 381                 iter->sg_pgoffset -= pgcount;
 382                 sg = sg_next(sg);
 383                 --iter->maxents;
 384                 if (sg == NULL || iter->maxents == 0)
 385                         break;
 386                 pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT;
 387         }
 388         iter->sg = sg;
 389 }
 390
 391 static inline int
 392 sg_page_count(struct scatterlist *sg)
 393 {
 394         return (PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT);
 395 }
 396
 397 static inline bool
 398 __sg_page_iter_next(struct sg_page_iter *piter)
 399 {
 400         if (piter->internal.nents == 0)
 401                 return (0);
 402         if (piter->sg == NULL)
 403                 return (0);
 404
 405         piter->sg_pgoffset += piter->internal.pg_advance;
 406         piter->internal.pg_advance = 1;
 407
 408         while (piter->sg_pgoffset >= sg_page_count(piter->sg)) {
 409                 piter->sg_pgoffset -= sg_page_count(piter->sg);
 410                 piter->sg = sg_next(piter->sg);
 411                 if (--piter->internal.nents == 0)
 412                         return (0);
 413                 if (piter->sg == NULL)
 414                         return (0);
 415         }
 416         return (1);
 417 }
 418
 419 static inline void
 420 _sg_iter_init(struct scatterlist *sgl, struct sg_page_iter *iter,
 421     unsigned int nents, unsigned long pgoffset)
 422 {
 423         if (nents) {
 424                 iter->sg = sgl;
 425                 iter->sg_pgoffset = pgoffset - 1;
 426                 iter->maxents = nents;
 427                 _sg_iter_next(iter);
 428         } else {
 429                 iter->sg = NULL;
 430                 iter->sg_pgoffset = 0;
 431                 iter->maxents = 0;
 432         }
 433 }
 434
 435 static inline dma_addr_t
 436 sg_page_iter_dma_address(struct sg_page_iter *spi)
 437 {
 438         return (spi->sg->address + (spi->sg_pgoffset << PAGE_SHIFT));
 439 }
 440
 441 static inline struct page *
 442 sg_page_iter_page(struct sg_page_iter *piter)
 443 {
 444         return (nth_page(sg_page(piter->sg), piter->sg_pgoffset));
 445 }
 446
 447
 448 #endif                                  /* _LINUX_SCATTERLIST_H_ */