scatterlist.h revision 345939
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 345939 2019-04-05 11:32:57Z 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 67335413Shselasky#define SCATTERLIST_MAX_SEGMENT (-1U & ~(PAGE_SIZE - 1)) 68335413Shselasky 69289682Shselasky#define SG_MAX_SINGLE_ALLOC (PAGE_SIZE / sizeof(struct scatterlist)) 70273135Shselasky 71328653Shselasky#define SG_MAGIC 0x87654321UL 72345938Shselasky#define SG_CHAIN SG_PAGE_LINK_CHAIN 73345938Shselasky#define SG_END SG_PAGE_LINK_LAST 74328653Shselasky 75328653Shselasky#define sg_is_chain(sg) ((sg)->page_link & SG_PAGE_LINK_CHAIN) 76328653Shselasky#define sg_is_last(sg) ((sg)->page_link & SG_PAGE_LINK_LAST) 77328653Shselasky#define sg_chain_ptr(sg) \ 78328653Shselasky ((struct scatterlist *) ((sg)->page_link & ~SG_PAGE_LINK_MASK)) 79328653Shselasky 80219820Sjeff#define sg_dma_address(sg) (sg)->address 81219820Sjeff#define sg_dma_len(sg) (sg)->length 82219820Sjeff 83328653Shselasky#define for_each_sg_page(sgl, iter, nents, pgoffset) \ 84328653Shselasky for (_sg_iter_init(sgl, iter, nents, pgoffset); \ 85328653Shselasky (iter)->sg; _sg_iter_next(iter)) 86219820Sjeff 87328653Shselasky#define for_each_sg(sglist, sg, sgmax, iter) \ 88328653Shselasky for (iter = 0, sg = (sglist); iter < (sgmax); iter++, sg = sg_next(sg)) 89328653Shselasky 90328653Shselaskytypedef struct scatterlist *(sg_alloc_fn) (unsigned int, gfp_t); 91328653Shselaskytypedef void (sg_free_fn) (struct scatterlist *, unsigned int); 92328653Shselasky 93219820Sjeffstatic inline void 94328653Shselaskysg_assign_page(struct scatterlist *sg, struct page *page) 95328653Shselasky{ 96328653Shselasky unsigned long page_link = sg->page_link & SG_PAGE_LINK_MASK; 97328653Shselasky 98328653Shselasky sg->page_link = page_link | (unsigned long)page; 99328653Shselasky} 100328653Shselasky 101328653Shselaskystatic inline void 102219820Sjeffsg_set_page(struct scatterlist *sg, struct page *page, unsigned int len, 103219820Sjeff unsigned int offset) 104219820Sjeff{ 105328653Shselasky sg_assign_page(sg, page); 106219820Sjeff sg->offset = offset; 107328653Shselasky sg->length = len; 108219820Sjeff} 109219820Sjeff 110328653Shselaskystatic inline struct page * 111328653Shselaskysg_page(struct scatterlist *sg) 112328653Shselasky{ 113328653Shselasky return ((struct page *)((sg)->page_link & ~SG_PAGE_LINK_MASK)); 114328653Shselasky} 115328653Shselasky 116219820Sjeffstatic inline void 117219820Sjeffsg_set_buf(struct scatterlist *sg, const void *buf, unsigned int buflen) 118219820Sjeff{ 119219820Sjeff sg_set_page(sg, virt_to_page(buf), buflen, 120289567Shselasky ((uintptr_t)buf) & (PAGE_SIZE - 1)); 121219820Sjeff} 122219820Sjeff 123219820Sjeffstatic inline struct scatterlist * 124219820Sjeffsg_next(struct scatterlist *sg) 125219820Sjeff{ 126328653Shselasky if (sg_is_last(sg)) 127219820Sjeff return (NULL); 128219820Sjeff sg++; 129328653Shselasky if (sg_is_chain(sg)) 130328653Shselasky sg = sg_chain_ptr(sg); 131219820Sjeff return (sg); 132219820Sjeff} 133219820Sjeff 134219820Sjeffstatic inline vm_paddr_t 135219820Sjeffsg_phys(struct scatterlist *sg) 136219820Sjeff{ 137328653Shselasky return (VM_PAGE_TO_PHYS(sg_page(sg)) + sg->offset); 138219820Sjeff} 139219820Sjeff 140345939Shselaskystatic inline void * 141345939Shselaskysg_virt(struct scatterlist *sg) 142345939Shselasky{ 143345939Shselasky 144345939Shselasky return ((void *)((unsigned long)page_address(sg_page(sg)) + sg->offset)); 145345939Shselasky} 146345939Shselasky 147273135Shselaskystatic inline void 148273135Shselaskysg_chain(struct scatterlist *prv, unsigned int prv_nents, 149289682Shselasky struct scatterlist *sgl) 150273135Shselasky{ 151273135Shselasky struct scatterlist *sg = &prv[prv_nents - 1]; 152273135Shselasky 153273135Shselasky sg->offset = 0; 154273135Shselasky sg->length = 0; 155328653Shselasky sg->page_link = ((unsigned long)sgl | 156328653Shselasky SG_PAGE_LINK_CHAIN) & ~SG_PAGE_LINK_LAST; 157273135Shselasky} 158273135Shselasky 159328653Shselaskystatic inline void 160289682Shselaskysg_mark_end(struct scatterlist *sg) 161273135Shselasky{ 162328653Shselasky sg->page_link |= SG_PAGE_LINK_LAST; 163328653Shselasky sg->page_link &= ~SG_PAGE_LINK_CHAIN; 164273135Shselasky} 165273135Shselasky 166273135Shselaskystatic inline void 167328653Shselaskysg_init_table(struct scatterlist *sg, unsigned int nents) 168273135Shselasky{ 169328653Shselasky bzero(sg, sizeof(*sg) * nents); 170328653Shselasky sg_mark_end(&sg[nents - 1]); 171328653Shselasky} 172328653Shselasky 173328653Shselaskystatic struct scatterlist * 174328653Shselaskysg_kmalloc(unsigned int nents, gfp_t gfp_mask) 175328653Shselasky{ 176328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 177328653Shselasky return ((void *)__get_free_page(gfp_mask)); 178328653Shselasky } else 179328653Shselasky return (kmalloc(nents * sizeof(struct scatterlist), gfp_mask)); 180328653Shselasky} 181328653Shselasky 182328653Shselaskystatic inline void 183328653Shselaskysg_kfree(struct scatterlist *sg, unsigned int nents) 184328653Shselasky{ 185328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 186328653Shselasky free_page((unsigned long)sg); 187328653Shselasky } else 188328653Shselasky kfree(sg); 189328653Shselasky} 190328653Shselasky 191328653Shselaskystatic inline void 192328653Shselasky__sg_free_table(struct sg_table *table, unsigned int max_ents, 193328653Shselasky bool skip_first_chunk, sg_free_fn * free_fn) 194328653Shselasky{ 195273135Shselasky struct scatterlist *sgl, *next; 196273135Shselasky 197273135Shselasky if (unlikely(!table->sgl)) 198273135Shselasky return; 199273135Shselasky 200273135Shselasky sgl = table->sgl; 201273135Shselasky while (table->orig_nents) { 202273135Shselasky unsigned int alloc_size = table->orig_nents; 203273135Shselasky unsigned int sg_size; 204273135Shselasky 205273135Shselasky if (alloc_size > max_ents) { 206328653Shselasky next = sg_chain_ptr(&sgl[max_ents - 1]); 207273135Shselasky alloc_size = max_ents; 208273135Shselasky sg_size = alloc_size - 1; 209273135Shselasky } else { 210273135Shselasky sg_size = alloc_size; 211273135Shselasky next = NULL; 212273135Shselasky } 213273135Shselasky 214273135Shselasky table->orig_nents -= sg_size; 215328653Shselasky if (skip_first_chunk) 216328653Shselasky skip_first_chunk = 0; 217328653Shselasky else 218328653Shselasky free_fn(sgl, alloc_size); 219273135Shselasky sgl = next; 220273135Shselasky } 221273135Shselasky 222273135Shselasky table->sgl = NULL; 223273135Shselasky} 224273135Shselasky 225273135Shselaskystatic inline void 226273135Shselaskysg_free_table(struct sg_table *table) 227273135Shselasky{ 228328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 229273135Shselasky} 230273135Shselasky 231273135Shselaskystatic inline int 232273135Shselasky__sg_alloc_table(struct sg_table *table, unsigned int nents, 233328653Shselasky unsigned int max_ents, struct scatterlist *first_chunk, 234328653Shselasky gfp_t gfp_mask, sg_alloc_fn *alloc_fn) 235273135Shselasky{ 236273135Shselasky struct scatterlist *sg, *prv; 237273135Shselasky unsigned int left; 238273135Shselasky 239273135Shselasky memset(table, 0, sizeof(*table)); 240273135Shselasky 241273135Shselasky if (nents == 0) 242328653Shselasky return (-EINVAL); 243273135Shselasky left = nents; 244273135Shselasky prv = NULL; 245273135Shselasky do { 246289682Shselasky unsigned int sg_size; 247289682Shselasky unsigned int alloc_size = left; 248273135Shselasky 249273135Shselasky if (alloc_size > max_ents) { 250273135Shselasky alloc_size = max_ents; 251273135Shselasky sg_size = alloc_size - 1; 252273135Shselasky } else 253273135Shselasky sg_size = alloc_size; 254273135Shselasky 255273135Shselasky left -= sg_size; 256273135Shselasky 257328653Shselasky if (first_chunk) { 258328653Shselasky sg = first_chunk; 259328653Shselasky first_chunk = NULL; 260328653Shselasky } else { 261328653Shselasky sg = alloc_fn(alloc_size, gfp_mask); 262328653Shselasky } 263273135Shselasky if (unlikely(!sg)) { 264273135Shselasky if (prv) 265273135Shselasky table->nents = ++table->orig_nents; 266273135Shselasky 267328653Shselasky return (-ENOMEM); 268273135Shselasky } 269273135Shselasky sg_init_table(sg, alloc_size); 270273135Shselasky table->nents = table->orig_nents += sg_size; 271273135Shselasky 272273135Shselasky if (prv) 273273135Shselasky sg_chain(prv, max_ents, sg); 274273135Shselasky else 275273135Shselasky table->sgl = sg; 276273135Shselasky 277273135Shselasky if (!left) 278273135Shselasky sg_mark_end(&sg[sg_size - 1]); 279273135Shselasky 280273135Shselasky prv = sg; 281273135Shselasky } while (left); 282273135Shselasky 283328653Shselasky return (0); 284273135Shselasky} 285273135Shselasky 286273135Shselaskystatic inline int 287273135Shselaskysg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask) 288273135Shselasky{ 289273135Shselasky int ret; 290273135Shselasky 291273135Shselasky ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC, 292328653Shselasky NULL, gfp_mask, sg_kmalloc); 293273135Shselasky if (unlikely(ret)) 294328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 295273135Shselasky 296328653Shselasky return (ret); 297273135Shselasky} 298273135Shselasky 299328653Shselaskystatic inline int 300335413Shselasky__sg_alloc_table_from_pages(struct sg_table *sgt, 301328653Shselasky struct page **pages, unsigned int count, 302328653Shselasky unsigned long off, unsigned long size, 303335413Shselasky unsigned int max_segment, gfp_t gfp_mask) 304328653Shselasky{ 305335413Shselasky unsigned int i, segs, cur, len; 306328653Shselasky int rc; 307328653Shselasky struct scatterlist *s; 308328653Shselasky 309335413Shselasky if (__predict_false(!max_segment || offset_in_page(max_segment))) 310335413Shselasky return (-EINVAL); 311335413Shselasky 312335413Shselasky len = 0; 313328653Shselasky for (segs = i = 1; i < count; ++i) { 314335413Shselasky len += PAGE_SIZE; 315335413Shselasky if (len >= max_segment || 316335413Shselasky page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) { 317328653Shselasky ++segs; 318335413Shselasky len = 0; 319335413Shselasky } 320328653Shselasky } 321328653Shselasky if (__predict_false((rc = sg_alloc_table(sgt, segs, gfp_mask)))) 322328653Shselasky return (rc); 323328653Shselasky 324328653Shselasky cur = 0; 325328653Shselasky for_each_sg(sgt->sgl, s, sgt->orig_nents, i) { 326328653Shselasky unsigned long seg_size; 327328653Shselasky unsigned int j; 328328653Shselasky 329335413Shselasky len = 0; 330335413Shselasky for (j = cur + 1; j < count; ++j) { 331335413Shselasky len += PAGE_SIZE; 332335413Shselasky if (len >= max_segment || page_to_pfn(pages[j]) != 333328653Shselasky page_to_pfn(pages[j - 1]) + 1) 334328653Shselasky break; 335335413Shselasky } 336328653Shselasky 337328653Shselasky seg_size = ((j - cur) << PAGE_SHIFT) - off; 338328653Shselasky sg_set_page(s, pages[cur], min(size, seg_size), off); 339328653Shselasky size -= seg_size; 340328653Shselasky off = 0; 341328653Shselasky cur = j; 342328653Shselasky } 343328653Shselasky return (0); 344328653Shselasky} 345328653Shselasky 346335413Shselaskystatic inline int 347335413Shselaskysg_alloc_table_from_pages(struct sg_table *sgt, 348335413Shselasky struct page **pages, unsigned int count, 349335413Shselasky unsigned long off, unsigned long size, 350335413Shselasky gfp_t gfp_mask) 351335413Shselasky{ 352328653Shselasky 353335413Shselasky return (__sg_alloc_table_from_pages(sgt, pages, count, off, size, 354335413Shselasky SCATTERLIST_MAX_SEGMENT, gfp_mask)); 355335413Shselasky} 356335413Shselasky 357328653Shselaskystatic inline int 358328653Shselaskysg_nents(struct scatterlist *sg) 359328653Shselasky{ 360328653Shselasky int nents; 361328653Shselasky 362328653Shselasky for (nents = 0; sg; sg = sg_next(sg)) 363328653Shselasky nents++; 364328653Shselasky return (nents); 365328653Shselasky} 366328653Shselasky 367289567Shselaskystatic inline void 368328653Shselasky__sg_page_iter_start(struct sg_page_iter *piter, 369328653Shselasky struct scatterlist *sglist, unsigned int nents, 370328653Shselasky unsigned long pgoffset) 371328653Shselasky{ 372328653Shselasky piter->internal.pg_advance = 0; 373328653Shselasky piter->internal.nents = nents; 374328653Shselasky 375328653Shselasky piter->sg = sglist; 376328653Shselasky piter->sg_pgoffset = pgoffset; 377328653Shselasky} 378328653Shselasky 379328653Shselaskystatic inline void 380289567Shselasky_sg_iter_next(struct sg_page_iter *iter) 381289567Shselasky{ 382289567Shselasky struct scatterlist *sg; 383289567Shselasky unsigned int pgcount; 384289567Shselasky 385289567Shselasky sg = iter->sg; 386289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 387289567Shselasky 388289567Shselasky ++iter->sg_pgoffset; 389289567Shselasky while (iter->sg_pgoffset >= pgcount) { 390289567Shselasky iter->sg_pgoffset -= pgcount; 391289567Shselasky sg = sg_next(sg); 392289567Shselasky --iter->maxents; 393289567Shselasky if (sg == NULL || iter->maxents == 0) 394289567Shselasky break; 395289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 396289567Shselasky } 397289567Shselasky iter->sg = sg; 398289567Shselasky} 399289567Shselasky 400328653Shselaskystatic inline int 401328653Shselaskysg_page_count(struct scatterlist *sg) 402328653Shselasky{ 403328653Shselasky return (PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT); 404328653Shselasky} 405328653Shselasky 406328653Shselaskystatic inline bool 407328653Shselasky__sg_page_iter_next(struct sg_page_iter *piter) 408328653Shselasky{ 409328653Shselasky if (piter->internal.nents == 0) 410328653Shselasky return (0); 411328653Shselasky if (piter->sg == NULL) 412328653Shselasky return (0); 413328653Shselasky 414328653Shselasky piter->sg_pgoffset += piter->internal.pg_advance; 415328653Shselasky piter->internal.pg_advance = 1; 416328653Shselasky 417328653Shselasky while (piter->sg_pgoffset >= sg_page_count(piter->sg)) { 418328653Shselasky piter->sg_pgoffset -= sg_page_count(piter->sg); 419328653Shselasky piter->sg = sg_next(piter->sg); 420328653Shselasky if (--piter->internal.nents == 0) 421328653Shselasky return (0); 422328653Shselasky if (piter->sg == NULL) 423328653Shselasky return (0); 424328653Shselasky } 425328653Shselasky return (1); 426328653Shselasky} 427328653Shselasky 428289567Shselaskystatic inline void 429289567Shselasky_sg_iter_init(struct scatterlist *sgl, struct sg_page_iter *iter, 430289682Shselasky unsigned int nents, unsigned long pgoffset) 431289567Shselasky{ 432289567Shselasky if (nents) { 433289567Shselasky iter->sg = sgl; 434289567Shselasky iter->sg_pgoffset = pgoffset - 1; 435289567Shselasky iter->maxents = nents; 436289567Shselasky _sg_iter_next(iter); 437289567Shselasky } else { 438289567Shselasky iter->sg = NULL; 439289567Shselasky iter->sg_pgoffset = 0; 440289567Shselasky iter->maxents = 0; 441289567Shselasky } 442289567Shselasky} 443289567Shselasky 444289567Shselaskystatic inline dma_addr_t 445289567Shselaskysg_page_iter_dma_address(struct sg_page_iter *spi) 446289567Shselasky{ 447328653Shselasky return (spi->sg->address + (spi->sg_pgoffset << PAGE_SHIFT)); 448289567Shselasky} 449289567Shselasky 450328653Shselaskystatic inline struct page * 451328653Shselaskysg_page_iter_page(struct sg_page_iter *piter) 452328653Shselasky{ 453328653Shselasky return (nth_page(sg_page(piter->sg), piter->sg_pgoffset)); 454328653Shselasky} 455289567Shselasky 456219820Sjeff 457289682Shselasky#endif /* _LINUX_SCATTERLIST_H_ */ 458