scatterlist.h revision 328653
1219820Sjeff/*- 2219820Sjeff * Copyright (c) 2010 Isilon Systems, Inc. 3219820Sjeff * Copyright (c) 2010 iX Systems, Inc. 4219820Sjeff * Copyright (c) 2010 Panasas, Inc. 5328653Shselasky * Copyright (c) 2013-2017 Mellanox Technologies, Ltd. 6289567Shselasky * Copyright (c) 2015 Matthew Dillon <dillon@backplane.com> 7219820Sjeff * All rights reserved. 8219820Sjeff * 9219820Sjeff * Redistribution and use in source and binary forms, with or without 10219820Sjeff * modification, are permitted provided that the following conditions 11219820Sjeff * are met: 12219820Sjeff * 1. Redistributions of source code must retain the above copyright 13219820Sjeff * notice unmodified, this list of conditions, and the following 14219820Sjeff * disclaimer. 15219820Sjeff * 2. Redistributions in binary form must reproduce the above copyright 16219820Sjeff * notice, this list of conditions and the following disclaimer in the 17219820Sjeff * documentation and/or other materials provided with the distribution. 18219820Sjeff * 19219820Sjeff * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 20219820Sjeff * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 21219820Sjeff * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 22219820Sjeff * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 23219820Sjeff * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 24219820Sjeff * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25219820Sjeff * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26219820Sjeff * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27219820Sjeff * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 28219820Sjeff * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29289644Shselasky * 30289644Shselasky * $FreeBSD: stable/11/sys/compat/linuxkpi/common/include/linux/scatterlist.h 328653 2018-02-01 13:01:44Z hselasky $ 31219820Sjeff */ 32219820Sjeff#ifndef _LINUX_SCATTERLIST_H_ 33219820Sjeff#define _LINUX_SCATTERLIST_H_ 34219820Sjeff 35219820Sjeff#include <linux/page.h> 36273135Shselasky#include <linux/slab.h> 37328653Shselasky#include <linux/mm.h> 38219820Sjeff 39219820Sjeffstruct scatterlist { 40328653Shselasky unsigned long page_link; 41328653Shselasky#define SG_PAGE_LINK_CHAIN 0x1UL 42328653Shselasky#define SG_PAGE_LINK_LAST 0x2UL 43328653Shselasky#define SG_PAGE_LINK_MASK 0x3UL 44328653Shselasky unsigned int offset; 45328653Shselasky unsigned int length; 46289682Shselasky dma_addr_t address; 47219820Sjeff}; 48219820Sjeff 49328653ShselaskyCTASSERT((sizeof(struct scatterlist) & SG_PAGE_LINK_MASK) == 0); 50328653Shselasky 51270710Shselaskystruct sg_table { 52289682Shselasky struct scatterlist *sgl; 53289682Shselasky unsigned int nents; 54289682Shselasky unsigned int orig_nents; 55270710Shselasky}; 56270710Shselasky 57289567Shselaskystruct sg_page_iter { 58289682Shselasky struct scatterlist *sg; 59289682Shselasky unsigned int sg_pgoffset; 60289682Shselasky unsigned int maxents; 61328653Shselasky struct { 62328653Shselasky unsigned int nents; 63328653Shselasky int pg_advance; 64328653Shselasky } internal; 65289567Shselasky}; 66289567Shselasky 67289682Shselasky#define SG_MAX_SINGLE_ALLOC (PAGE_SIZE / sizeof(struct scatterlist)) 68273135Shselasky 69328653Shselasky#define SG_MAGIC 0x87654321UL 70328653Shselasky 71328653Shselasky#define sg_is_chain(sg) ((sg)->page_link & SG_PAGE_LINK_CHAIN) 72328653Shselasky#define sg_is_last(sg) ((sg)->page_link & SG_PAGE_LINK_LAST) 73328653Shselasky#define sg_chain_ptr(sg) \ 74328653Shselasky ((struct scatterlist *) ((sg)->page_link & ~SG_PAGE_LINK_MASK)) 75328653Shselasky 76219820Sjeff#define sg_dma_address(sg) (sg)->address 77219820Sjeff#define sg_dma_len(sg) (sg)->length 78219820Sjeff 79328653Shselasky#define for_each_sg_page(sgl, iter, nents, pgoffset) \ 80328653Shselasky for (_sg_iter_init(sgl, iter, nents, pgoffset); \ 81328653Shselasky (iter)->sg; _sg_iter_next(iter)) 82219820Sjeff 83328653Shselasky#define for_each_sg(sglist, sg, sgmax, iter) \ 84328653Shselasky for (iter = 0, sg = (sglist); iter < (sgmax); iter++, sg = sg_next(sg)) 85328653Shselasky 86328653Shselaskytypedef struct scatterlist *(sg_alloc_fn) (unsigned int, gfp_t); 87328653Shselaskytypedef void (sg_free_fn) (struct scatterlist *, unsigned int); 88328653Shselasky 89219820Sjeffstatic inline void 90328653Shselaskysg_assign_page(struct scatterlist *sg, struct page *page) 91328653Shselasky{ 92328653Shselasky unsigned long page_link = sg->page_link & SG_PAGE_LINK_MASK; 93328653Shselasky 94328653Shselasky sg->page_link = page_link | (unsigned long)page; 95328653Shselasky} 96328653Shselasky 97328653Shselaskystatic inline void 98219820Sjeffsg_set_page(struct scatterlist *sg, struct page *page, unsigned int len, 99219820Sjeff unsigned int offset) 100219820Sjeff{ 101328653Shselasky sg_assign_page(sg, page); 102219820Sjeff sg->offset = offset; 103328653Shselasky sg->length = len; 104219820Sjeff} 105219820Sjeff 106328653Shselaskystatic inline struct page * 107328653Shselaskysg_page(struct scatterlist *sg) 108328653Shselasky{ 109328653Shselasky return ((struct page *)((sg)->page_link & ~SG_PAGE_LINK_MASK)); 110328653Shselasky} 111328653Shselasky 112219820Sjeffstatic inline void 113219820Sjeffsg_set_buf(struct scatterlist *sg, const void *buf, unsigned int buflen) 114219820Sjeff{ 115219820Sjeff sg_set_page(sg, virt_to_page(buf), buflen, 116289567Shselasky ((uintptr_t)buf) & (PAGE_SIZE - 1)); 117219820Sjeff} 118219820Sjeff 119219820Sjeffstatic inline struct scatterlist * 120219820Sjeffsg_next(struct scatterlist *sg) 121219820Sjeff{ 122328653Shselasky if (sg_is_last(sg)) 123219820Sjeff return (NULL); 124219820Sjeff sg++; 125328653Shselasky if (sg_is_chain(sg)) 126328653Shselasky sg = sg_chain_ptr(sg); 127219820Sjeff return (sg); 128219820Sjeff} 129219820Sjeff 130219820Sjeffstatic inline vm_paddr_t 131219820Sjeffsg_phys(struct scatterlist *sg) 132219820Sjeff{ 133328653Shselasky return (VM_PAGE_TO_PHYS(sg_page(sg)) + sg->offset); 134219820Sjeff} 135219820Sjeff 136273135Shselaskystatic inline void 137273135Shselaskysg_chain(struct scatterlist *prv, unsigned int prv_nents, 138289682Shselasky struct scatterlist *sgl) 139273135Shselasky{ 140273135Shselasky struct scatterlist *sg = &prv[prv_nents - 1]; 141273135Shselasky 142273135Shselasky sg->offset = 0; 143273135Shselasky sg->length = 0; 144328653Shselasky sg->page_link = ((unsigned long)sgl | 145328653Shselasky SG_PAGE_LINK_CHAIN) & ~SG_PAGE_LINK_LAST; 146273135Shselasky} 147273135Shselasky 148328653Shselaskystatic inline void 149289682Shselaskysg_mark_end(struct scatterlist *sg) 150273135Shselasky{ 151328653Shselasky sg->page_link |= SG_PAGE_LINK_LAST; 152328653Shselasky sg->page_link &= ~SG_PAGE_LINK_CHAIN; 153273135Shselasky} 154273135Shselasky 155273135Shselaskystatic inline void 156328653Shselaskysg_init_table(struct scatterlist *sg, unsigned int nents) 157273135Shselasky{ 158328653Shselasky bzero(sg, sizeof(*sg) * nents); 159328653Shselasky sg_mark_end(&sg[nents - 1]); 160328653Shselasky} 161328653Shselasky 162328653Shselaskystatic struct scatterlist * 163328653Shselaskysg_kmalloc(unsigned int nents, gfp_t gfp_mask) 164328653Shselasky{ 165328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 166328653Shselasky return ((void *)__get_free_page(gfp_mask)); 167328653Shselasky } else 168328653Shselasky return (kmalloc(nents * sizeof(struct scatterlist), gfp_mask)); 169328653Shselasky} 170328653Shselasky 171328653Shselaskystatic inline void 172328653Shselaskysg_kfree(struct scatterlist *sg, unsigned int nents) 173328653Shselasky{ 174328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 175328653Shselasky free_page((unsigned long)sg); 176328653Shselasky } else 177328653Shselasky kfree(sg); 178328653Shselasky} 179328653Shselasky 180328653Shselaskystatic inline void 181328653Shselasky__sg_free_table(struct sg_table *table, unsigned int max_ents, 182328653Shselasky bool skip_first_chunk, sg_free_fn * free_fn) 183328653Shselasky{ 184273135Shselasky struct scatterlist *sgl, *next; 185273135Shselasky 186273135Shselasky if (unlikely(!table->sgl)) 187273135Shselasky return; 188273135Shselasky 189273135Shselasky sgl = table->sgl; 190273135Shselasky while (table->orig_nents) { 191273135Shselasky unsigned int alloc_size = table->orig_nents; 192273135Shselasky unsigned int sg_size; 193273135Shselasky 194273135Shselasky if (alloc_size > max_ents) { 195328653Shselasky next = sg_chain_ptr(&sgl[max_ents - 1]); 196273135Shselasky alloc_size = max_ents; 197273135Shselasky sg_size = alloc_size - 1; 198273135Shselasky } else { 199273135Shselasky sg_size = alloc_size; 200273135Shselasky next = NULL; 201273135Shselasky } 202273135Shselasky 203273135Shselasky table->orig_nents -= sg_size; 204328653Shselasky if (skip_first_chunk) 205328653Shselasky skip_first_chunk = 0; 206328653Shselasky else 207328653Shselasky free_fn(sgl, alloc_size); 208273135Shselasky sgl = next; 209273135Shselasky } 210273135Shselasky 211273135Shselasky table->sgl = NULL; 212273135Shselasky} 213273135Shselasky 214273135Shselaskystatic inline void 215273135Shselaskysg_free_table(struct sg_table *table) 216273135Shselasky{ 217328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 218273135Shselasky} 219273135Shselasky 220273135Shselaskystatic inline int 221273135Shselasky__sg_alloc_table(struct sg_table *table, unsigned int nents, 222328653Shselasky unsigned int max_ents, struct scatterlist *first_chunk, 223328653Shselasky gfp_t gfp_mask, sg_alloc_fn *alloc_fn) 224273135Shselasky{ 225273135Shselasky struct scatterlist *sg, *prv; 226273135Shselasky unsigned int left; 227273135Shselasky 228273135Shselasky memset(table, 0, sizeof(*table)); 229273135Shselasky 230273135Shselasky if (nents == 0) 231328653Shselasky return (-EINVAL); 232273135Shselasky left = nents; 233273135Shselasky prv = NULL; 234273135Shselasky do { 235289682Shselasky unsigned int sg_size; 236289682Shselasky unsigned int alloc_size = left; 237273135Shselasky 238273135Shselasky if (alloc_size > max_ents) { 239273135Shselasky alloc_size = max_ents; 240273135Shselasky sg_size = alloc_size - 1; 241273135Shselasky } else 242273135Shselasky sg_size = alloc_size; 243273135Shselasky 244273135Shselasky left -= sg_size; 245273135Shselasky 246328653Shselasky if (first_chunk) { 247328653Shselasky sg = first_chunk; 248328653Shselasky first_chunk = NULL; 249328653Shselasky } else { 250328653Shselasky sg = alloc_fn(alloc_size, gfp_mask); 251328653Shselasky } 252273135Shselasky if (unlikely(!sg)) { 253273135Shselasky if (prv) 254273135Shselasky table->nents = ++table->orig_nents; 255273135Shselasky 256328653Shselasky return (-ENOMEM); 257273135Shselasky } 258273135Shselasky sg_init_table(sg, alloc_size); 259273135Shselasky table->nents = table->orig_nents += sg_size; 260273135Shselasky 261273135Shselasky if (prv) 262273135Shselasky sg_chain(prv, max_ents, sg); 263273135Shselasky else 264273135Shselasky table->sgl = sg; 265273135Shselasky 266273135Shselasky if (!left) 267273135Shselasky sg_mark_end(&sg[sg_size - 1]); 268273135Shselasky 269273135Shselasky prv = sg; 270273135Shselasky } while (left); 271273135Shselasky 272328653Shselasky return (0); 273273135Shselasky} 274273135Shselasky 275273135Shselaskystatic inline int 276273135Shselaskysg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask) 277273135Shselasky{ 278273135Shselasky int ret; 279273135Shselasky 280273135Shselasky ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC, 281328653Shselasky NULL, gfp_mask, sg_kmalloc); 282273135Shselasky if (unlikely(ret)) 283328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 284273135Shselasky 285328653Shselasky return (ret); 286273135Shselasky} 287273135Shselasky 288328653Shselaskystatic inline int 289328653Shselaskysg_alloc_table_from_pages(struct sg_table *sgt, 290328653Shselasky struct page **pages, unsigned int count, 291328653Shselasky unsigned long off, unsigned long size, 292328653Shselasky gfp_t gfp_mask) 293328653Shselasky{ 294328653Shselasky unsigned int i, segs, cur; 295328653Shselasky int rc; 296328653Shselasky struct scatterlist *s; 297328653Shselasky 298328653Shselasky for (segs = i = 1; i < count; ++i) { 299328653Shselasky if (page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) 300328653Shselasky ++segs; 301328653Shselasky } 302328653Shselasky if (__predict_false((rc = sg_alloc_table(sgt, segs, gfp_mask)))) 303328653Shselasky return (rc); 304328653Shselasky 305328653Shselasky cur = 0; 306328653Shselasky for_each_sg(sgt->sgl, s, sgt->orig_nents, i) { 307328653Shselasky unsigned long seg_size; 308328653Shselasky unsigned int j; 309328653Shselasky 310328653Shselasky for (j = cur + 1; j < count; ++j) 311328653Shselasky if (page_to_pfn(pages[j]) != 312328653Shselasky page_to_pfn(pages[j - 1]) + 1) 313328653Shselasky break; 314328653Shselasky 315328653Shselasky seg_size = ((j - cur) << PAGE_SHIFT) - off; 316328653Shselasky sg_set_page(s, pages[cur], min(size, seg_size), off); 317328653Shselasky size -= seg_size; 318328653Shselasky off = 0; 319328653Shselasky cur = j; 320328653Shselasky } 321328653Shselasky return (0); 322328653Shselasky} 323328653Shselasky 324328653Shselasky 325328653Shselaskystatic inline int 326328653Shselaskysg_nents(struct scatterlist *sg) 327328653Shselasky{ 328328653Shselasky int nents; 329328653Shselasky 330328653Shselasky for (nents = 0; sg; sg = sg_next(sg)) 331328653Shselasky nents++; 332328653Shselasky return (nents); 333328653Shselasky} 334328653Shselasky 335289567Shselaskystatic inline void 336328653Shselasky__sg_page_iter_start(struct sg_page_iter *piter, 337328653Shselasky struct scatterlist *sglist, unsigned int nents, 338328653Shselasky unsigned long pgoffset) 339328653Shselasky{ 340328653Shselasky piter->internal.pg_advance = 0; 341328653Shselasky piter->internal.nents = nents; 342328653Shselasky 343328653Shselasky piter->sg = sglist; 344328653Shselasky piter->sg_pgoffset = pgoffset; 345328653Shselasky} 346328653Shselasky 347328653Shselaskystatic inline void 348289567Shselasky_sg_iter_next(struct sg_page_iter *iter) 349289567Shselasky{ 350289567Shselasky struct scatterlist *sg; 351289567Shselasky unsigned int pgcount; 352289567Shselasky 353289567Shselasky sg = iter->sg; 354289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 355289567Shselasky 356289567Shselasky ++iter->sg_pgoffset; 357289567Shselasky while (iter->sg_pgoffset >= pgcount) { 358289567Shselasky iter->sg_pgoffset -= pgcount; 359289567Shselasky sg = sg_next(sg); 360289567Shselasky --iter->maxents; 361289567Shselasky if (sg == NULL || iter->maxents == 0) 362289567Shselasky break; 363289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 364289567Shselasky } 365289567Shselasky iter->sg = sg; 366289567Shselasky} 367289567Shselasky 368328653Shselaskystatic inline int 369328653Shselaskysg_page_count(struct scatterlist *sg) 370328653Shselasky{ 371328653Shselasky return (PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT); 372328653Shselasky} 373328653Shselasky 374328653Shselaskystatic inline bool 375328653Shselasky__sg_page_iter_next(struct sg_page_iter *piter) 376328653Shselasky{ 377328653Shselasky if (piter->internal.nents == 0) 378328653Shselasky return (0); 379328653Shselasky if (piter->sg == NULL) 380328653Shselasky return (0); 381328653Shselasky 382328653Shselasky piter->sg_pgoffset += piter->internal.pg_advance; 383328653Shselasky piter->internal.pg_advance = 1; 384328653Shselasky 385328653Shselasky while (piter->sg_pgoffset >= sg_page_count(piter->sg)) { 386328653Shselasky piter->sg_pgoffset -= sg_page_count(piter->sg); 387328653Shselasky piter->sg = sg_next(piter->sg); 388328653Shselasky if (--piter->internal.nents == 0) 389328653Shselasky return (0); 390328653Shselasky if (piter->sg == NULL) 391328653Shselasky return (0); 392328653Shselasky } 393328653Shselasky return (1); 394328653Shselasky} 395328653Shselasky 396289567Shselaskystatic inline void 397289567Shselasky_sg_iter_init(struct scatterlist *sgl, struct sg_page_iter *iter, 398289682Shselasky unsigned int nents, unsigned long pgoffset) 399289567Shselasky{ 400289567Shselasky if (nents) { 401289567Shselasky iter->sg = sgl; 402289567Shselasky iter->sg_pgoffset = pgoffset - 1; 403289567Shselasky iter->maxents = nents; 404289567Shselasky _sg_iter_next(iter); 405289567Shselasky } else { 406289567Shselasky iter->sg = NULL; 407289567Shselasky iter->sg_pgoffset = 0; 408289567Shselasky iter->maxents = 0; 409289567Shselasky } 410289567Shselasky} 411289567Shselasky 412289567Shselaskystatic inline dma_addr_t 413289567Shselaskysg_page_iter_dma_address(struct sg_page_iter *spi) 414289567Shselasky{ 415328653Shselasky return (spi->sg->address + (spi->sg_pgoffset << PAGE_SHIFT)); 416289567Shselasky} 417289567Shselasky 418328653Shselaskystatic inline struct page * 419328653Shselaskysg_page_iter_page(struct sg_page_iter *piter) 420328653Shselasky{ 421328653Shselasky return (nth_page(sg_page(piter->sg), piter->sg_pgoffset)); 422328653Shselasky} 423289567Shselasky 424219820Sjeff 425289682Shselasky#endif /* _LINUX_SCATTERLIST_H_ */ 426