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 368828 2020-12-30 01:11:14Z 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 67361204Shselaskystruct sg_dma_page_iter { 68361204Shselasky struct sg_page_iter base; 69361204Shselasky}; 70361204Shselasky 71335413Shselasky#define SCATTERLIST_MAX_SEGMENT (-1U & ~(PAGE_SIZE - 1)) 72335413Shselasky 73289682Shselasky#define SG_MAX_SINGLE_ALLOC (PAGE_SIZE / sizeof(struct scatterlist)) 74273135Shselasky 75328653Shselasky#define SG_MAGIC 0x87654321UL 76345938Shselasky#define SG_CHAIN SG_PAGE_LINK_CHAIN 77345938Shselasky#define SG_END SG_PAGE_LINK_LAST 78328653Shselasky 79328653Shselasky#define sg_is_chain(sg) ((sg)->page_link & SG_PAGE_LINK_CHAIN) 80328653Shselasky#define sg_is_last(sg) ((sg)->page_link & SG_PAGE_LINK_LAST) 81328653Shselasky#define sg_chain_ptr(sg) \ 82328653Shselasky ((struct scatterlist *) ((sg)->page_link & ~SG_PAGE_LINK_MASK)) 83328653Shselasky 84219820Sjeff#define sg_dma_address(sg) (sg)->address 85219820Sjeff#define sg_dma_len(sg) (sg)->length 86219820Sjeff 87328653Shselasky#define for_each_sg_page(sgl, iter, nents, pgoffset) \ 88328653Shselasky for (_sg_iter_init(sgl, iter, nents, pgoffset); \ 89328653Shselasky (iter)->sg; _sg_iter_next(iter)) 90361204Shselasky#define for_each_sg_dma_page(sgl, iter, nents, pgoffset) \ 91361204Shselasky for_each_sg_page(sgl, &(iter)->base, nents, pgoffset) 92219820Sjeff 93328653Shselasky#define for_each_sg(sglist, sg, sgmax, iter) \ 94328653Shselasky for (iter = 0, sg = (sglist); iter < (sgmax); iter++, sg = sg_next(sg)) 95328653Shselasky 96328653Shselaskytypedef struct scatterlist *(sg_alloc_fn) (unsigned int, gfp_t); 97328653Shselaskytypedef void (sg_free_fn) (struct scatterlist *, unsigned int); 98328653Shselasky 99219820Sjeffstatic inline void 100328653Shselaskysg_assign_page(struct scatterlist *sg, struct page *page) 101328653Shselasky{ 102328653Shselasky unsigned long page_link = sg->page_link & SG_PAGE_LINK_MASK; 103328653Shselasky 104328653Shselasky sg->page_link = page_link | (unsigned long)page; 105328653Shselasky} 106328653Shselasky 107328653Shselaskystatic inline void 108219820Sjeffsg_set_page(struct scatterlist *sg, struct page *page, unsigned int len, 109219820Sjeff unsigned int offset) 110219820Sjeff{ 111328653Shselasky sg_assign_page(sg, page); 112219820Sjeff sg->offset = offset; 113328653Shselasky sg->length = len; 114219820Sjeff} 115219820Sjeff 116328653Shselaskystatic inline struct page * 117328653Shselaskysg_page(struct scatterlist *sg) 118328653Shselasky{ 119328653Shselasky return ((struct page *)((sg)->page_link & ~SG_PAGE_LINK_MASK)); 120328653Shselasky} 121328653Shselasky 122219820Sjeffstatic inline void 123219820Sjeffsg_set_buf(struct scatterlist *sg, const void *buf, unsigned int buflen) 124219820Sjeff{ 125219820Sjeff sg_set_page(sg, virt_to_page(buf), buflen, 126289567Shselasky ((uintptr_t)buf) & (PAGE_SIZE - 1)); 127219820Sjeff} 128219820Sjeff 129219820Sjeffstatic inline struct scatterlist * 130219820Sjeffsg_next(struct scatterlist *sg) 131219820Sjeff{ 132328653Shselasky if (sg_is_last(sg)) 133219820Sjeff return (NULL); 134219820Sjeff sg++; 135328653Shselasky if (sg_is_chain(sg)) 136328653Shselasky sg = sg_chain_ptr(sg); 137219820Sjeff return (sg); 138219820Sjeff} 139219820Sjeff 140219820Sjeffstatic inline vm_paddr_t 141219820Sjeffsg_phys(struct scatterlist *sg) 142219820Sjeff{ 143328653Shselasky return (VM_PAGE_TO_PHYS(sg_page(sg)) + sg->offset); 144219820Sjeff} 145219820Sjeff 146345939Shselaskystatic inline void * 147345939Shselaskysg_virt(struct scatterlist *sg) 148345939Shselasky{ 149345939Shselasky 150345939Shselasky return ((void *)((unsigned long)page_address(sg_page(sg)) + sg->offset)); 151345939Shselasky} 152345939Shselasky 153273135Shselaskystatic inline void 154273135Shselaskysg_chain(struct scatterlist *prv, unsigned int prv_nents, 155289682Shselasky struct scatterlist *sgl) 156273135Shselasky{ 157273135Shselasky struct scatterlist *sg = &prv[prv_nents - 1]; 158273135Shselasky 159273135Shselasky sg->offset = 0; 160273135Shselasky sg->length = 0; 161328653Shselasky sg->page_link = ((unsigned long)sgl | 162328653Shselasky SG_PAGE_LINK_CHAIN) & ~SG_PAGE_LINK_LAST; 163273135Shselasky} 164273135Shselasky 165328653Shselaskystatic inline void 166289682Shselaskysg_mark_end(struct scatterlist *sg) 167273135Shselasky{ 168328653Shselasky sg->page_link |= SG_PAGE_LINK_LAST; 169328653Shselasky sg->page_link &= ~SG_PAGE_LINK_CHAIN; 170273135Shselasky} 171273135Shselasky 172273135Shselaskystatic inline void 173328653Shselaskysg_init_table(struct scatterlist *sg, unsigned int nents) 174273135Shselasky{ 175328653Shselasky bzero(sg, sizeof(*sg) * nents); 176328653Shselasky sg_mark_end(&sg[nents - 1]); 177328653Shselasky} 178328653Shselasky 179328653Shselaskystatic struct scatterlist * 180328653Shselaskysg_kmalloc(unsigned int nents, gfp_t gfp_mask) 181328653Shselasky{ 182328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 183328653Shselasky return ((void *)__get_free_page(gfp_mask)); 184328653Shselasky } else 185328653Shselasky return (kmalloc(nents * sizeof(struct scatterlist), gfp_mask)); 186328653Shselasky} 187328653Shselasky 188328653Shselaskystatic inline void 189328653Shselaskysg_kfree(struct scatterlist *sg, unsigned int nents) 190328653Shselasky{ 191328653Shselasky if (nents == SG_MAX_SINGLE_ALLOC) { 192328653Shselasky free_page((unsigned long)sg); 193328653Shselasky } else 194328653Shselasky kfree(sg); 195328653Shselasky} 196328653Shselasky 197328653Shselaskystatic inline void 198328653Shselasky__sg_free_table(struct sg_table *table, unsigned int max_ents, 199328653Shselasky bool skip_first_chunk, sg_free_fn * free_fn) 200328653Shselasky{ 201273135Shselasky struct scatterlist *sgl, *next; 202273135Shselasky 203273135Shselasky if (unlikely(!table->sgl)) 204273135Shselasky return; 205273135Shselasky 206273135Shselasky sgl = table->sgl; 207273135Shselasky while (table->orig_nents) { 208273135Shselasky unsigned int alloc_size = table->orig_nents; 209273135Shselasky unsigned int sg_size; 210273135Shselasky 211273135Shselasky if (alloc_size > max_ents) { 212328653Shselasky next = sg_chain_ptr(&sgl[max_ents - 1]); 213273135Shselasky alloc_size = max_ents; 214273135Shselasky sg_size = alloc_size - 1; 215273135Shselasky } else { 216273135Shselasky sg_size = alloc_size; 217273135Shselasky next = NULL; 218273135Shselasky } 219273135Shselasky 220273135Shselasky table->orig_nents -= sg_size; 221328653Shselasky if (skip_first_chunk) 222328653Shselasky skip_first_chunk = 0; 223328653Shselasky else 224328653Shselasky free_fn(sgl, alloc_size); 225273135Shselasky sgl = next; 226273135Shselasky } 227273135Shselasky 228273135Shselasky table->sgl = NULL; 229273135Shselasky} 230273135Shselasky 231273135Shselaskystatic inline void 232273135Shselaskysg_free_table(struct sg_table *table) 233273135Shselasky{ 234328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 235273135Shselasky} 236273135Shselasky 237273135Shselaskystatic inline int 238273135Shselasky__sg_alloc_table(struct sg_table *table, unsigned int nents, 239328653Shselasky unsigned int max_ents, struct scatterlist *first_chunk, 240328653Shselasky gfp_t gfp_mask, sg_alloc_fn *alloc_fn) 241273135Shselasky{ 242273135Shselasky struct scatterlist *sg, *prv; 243273135Shselasky unsigned int left; 244273135Shselasky 245273135Shselasky memset(table, 0, sizeof(*table)); 246273135Shselasky 247273135Shselasky if (nents == 0) 248328653Shselasky return (-EINVAL); 249273135Shselasky left = nents; 250273135Shselasky prv = NULL; 251273135Shselasky do { 252289682Shselasky unsigned int sg_size; 253289682Shselasky unsigned int alloc_size = left; 254273135Shselasky 255273135Shselasky if (alloc_size > max_ents) { 256273135Shselasky alloc_size = max_ents; 257273135Shselasky sg_size = alloc_size - 1; 258273135Shselasky } else 259273135Shselasky sg_size = alloc_size; 260273135Shselasky 261273135Shselasky left -= sg_size; 262273135Shselasky 263328653Shselasky if (first_chunk) { 264328653Shselasky sg = first_chunk; 265328653Shselasky first_chunk = NULL; 266328653Shselasky } else { 267328653Shselasky sg = alloc_fn(alloc_size, gfp_mask); 268328653Shselasky } 269273135Shselasky if (unlikely(!sg)) { 270273135Shselasky if (prv) 271273135Shselasky table->nents = ++table->orig_nents; 272273135Shselasky 273328653Shselasky return (-ENOMEM); 274273135Shselasky } 275273135Shselasky sg_init_table(sg, alloc_size); 276273135Shselasky table->nents = table->orig_nents += sg_size; 277273135Shselasky 278273135Shselasky if (prv) 279273135Shselasky sg_chain(prv, max_ents, sg); 280273135Shselasky else 281273135Shselasky table->sgl = sg; 282273135Shselasky 283273135Shselasky if (!left) 284273135Shselasky sg_mark_end(&sg[sg_size - 1]); 285273135Shselasky 286273135Shselasky prv = sg; 287273135Shselasky } while (left); 288273135Shselasky 289328653Shselasky return (0); 290273135Shselasky} 291273135Shselasky 292273135Shselaskystatic inline int 293273135Shselaskysg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask) 294273135Shselasky{ 295273135Shselasky int ret; 296273135Shselasky 297273135Shselasky ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC, 298328653Shselasky NULL, gfp_mask, sg_kmalloc); 299273135Shselasky if (unlikely(ret)) 300328653Shselasky __sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree); 301273135Shselasky 302328653Shselasky return (ret); 303273135Shselasky} 304273135Shselasky 305328653Shselaskystatic inline int 306335413Shselasky__sg_alloc_table_from_pages(struct sg_table *sgt, 307328653Shselasky struct page **pages, unsigned int count, 308328653Shselasky unsigned long off, unsigned long size, 309335413Shselasky unsigned int max_segment, gfp_t gfp_mask) 310328653Shselasky{ 311335413Shselasky unsigned int i, segs, cur, len; 312328653Shselasky int rc; 313328653Shselasky struct scatterlist *s; 314328653Shselasky 315335413Shselasky if (__predict_false(!max_segment || offset_in_page(max_segment))) 316335413Shselasky return (-EINVAL); 317335413Shselasky 318335413Shselasky len = 0; 319328653Shselasky for (segs = i = 1; i < count; ++i) { 320335413Shselasky len += PAGE_SIZE; 321335413Shselasky if (len >= max_segment || 322335413Shselasky page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) { 323328653Shselasky ++segs; 324335413Shselasky len = 0; 325335413Shselasky } 326328653Shselasky } 327328653Shselasky if (__predict_false((rc = sg_alloc_table(sgt, segs, gfp_mask)))) 328328653Shselasky return (rc); 329328653Shselasky 330328653Shselasky cur = 0; 331328653Shselasky for_each_sg(sgt->sgl, s, sgt->orig_nents, i) { 332328653Shselasky unsigned long seg_size; 333328653Shselasky unsigned int j; 334328653Shselasky 335335413Shselasky len = 0; 336335413Shselasky for (j = cur + 1; j < count; ++j) { 337335413Shselasky len += PAGE_SIZE; 338335413Shselasky if (len >= max_segment || page_to_pfn(pages[j]) != 339328653Shselasky page_to_pfn(pages[j - 1]) + 1) 340328653Shselasky break; 341335413Shselasky } 342328653Shselasky 343328653Shselasky seg_size = ((j - cur) << PAGE_SHIFT) - off; 344368828Shselasky sg_set_page(s, pages[cur], MIN(size, seg_size), off); 345328653Shselasky size -= seg_size; 346328653Shselasky off = 0; 347328653Shselasky cur = j; 348328653Shselasky } 349328653Shselasky return (0); 350328653Shselasky} 351328653Shselasky 352335413Shselaskystatic inline int 353335413Shselaskysg_alloc_table_from_pages(struct sg_table *sgt, 354335413Shselasky struct page **pages, unsigned int count, 355335413Shselasky unsigned long off, unsigned long size, 356335413Shselasky gfp_t gfp_mask) 357335413Shselasky{ 358328653Shselasky 359335413Shselasky return (__sg_alloc_table_from_pages(sgt, pages, count, off, size, 360335413Shselasky SCATTERLIST_MAX_SEGMENT, gfp_mask)); 361335413Shselasky} 362335413Shselasky 363328653Shselaskystatic inline int 364328653Shselaskysg_nents(struct scatterlist *sg) 365328653Shselasky{ 366328653Shselasky int nents; 367328653Shselasky 368328653Shselasky for (nents = 0; sg; sg = sg_next(sg)) 369328653Shselasky nents++; 370328653Shselasky return (nents); 371328653Shselasky} 372328653Shselasky 373289567Shselaskystatic inline void 374328653Shselasky__sg_page_iter_start(struct sg_page_iter *piter, 375328653Shselasky struct scatterlist *sglist, unsigned int nents, 376328653Shselasky unsigned long pgoffset) 377328653Shselasky{ 378328653Shselasky piter->internal.pg_advance = 0; 379328653Shselasky piter->internal.nents = nents; 380328653Shselasky 381328653Shselasky piter->sg = sglist; 382328653Shselasky piter->sg_pgoffset = pgoffset; 383328653Shselasky} 384328653Shselasky 385328653Shselaskystatic inline void 386289567Shselasky_sg_iter_next(struct sg_page_iter *iter) 387289567Shselasky{ 388289567Shselasky struct scatterlist *sg; 389289567Shselasky unsigned int pgcount; 390289567Shselasky 391289567Shselasky sg = iter->sg; 392289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 393289567Shselasky 394289567Shselasky ++iter->sg_pgoffset; 395289567Shselasky while (iter->sg_pgoffset >= pgcount) { 396289567Shselasky iter->sg_pgoffset -= pgcount; 397289567Shselasky sg = sg_next(sg); 398289567Shselasky --iter->maxents; 399289567Shselasky if (sg == NULL || iter->maxents == 0) 400289567Shselasky break; 401289567Shselasky pgcount = (sg->offset + sg->length + PAGE_SIZE - 1) >> PAGE_SHIFT; 402289567Shselasky } 403289567Shselasky iter->sg = sg; 404289567Shselasky} 405289567Shselasky 406328653Shselaskystatic inline int 407328653Shselaskysg_page_count(struct scatterlist *sg) 408328653Shselasky{ 409328653Shselasky return (PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT); 410328653Shselasky} 411361204Shselasky#define sg_dma_page_count(sg) \ 412361204Shselasky sg_page_count(sg) 413328653Shselasky 414328653Shselaskystatic inline bool 415328653Shselasky__sg_page_iter_next(struct sg_page_iter *piter) 416328653Shselasky{ 417361206Shselasky unsigned int pgcount; 418361206Shselasky 419328653Shselasky if (piter->internal.nents == 0) 420328653Shselasky return (0); 421328653Shselasky if (piter->sg == NULL) 422328653Shselasky return (0); 423328653Shselasky 424328653Shselasky piter->sg_pgoffset += piter->internal.pg_advance; 425328653Shselasky piter->internal.pg_advance = 1; 426328653Shselasky 427361206Shselasky while (1) { 428361206Shselasky pgcount = sg_page_count(piter->sg); 429361206Shselasky if (likely(piter->sg_pgoffset < pgcount)) 430361206Shselasky break; 431361206Shselasky piter->sg_pgoffset -= pgcount; 432328653Shselasky piter->sg = sg_next(piter->sg); 433328653Shselasky if (--piter->internal.nents == 0) 434328653Shselasky return (0); 435328653Shselasky if (piter->sg == NULL) 436328653Shselasky return (0); 437328653Shselasky } 438328653Shselasky return (1); 439328653Shselasky} 440361204Shselasky#define __sg_page_iter_dma_next(itr) \ 441361204Shselasky __sg_page_iter_next(&(itr)->base) 442328653Shselasky 443289567Shselaskystatic inline void 444289567Shselasky_sg_iter_init(struct scatterlist *sgl, struct sg_page_iter *iter, 445289682Shselasky unsigned int nents, unsigned long pgoffset) 446289567Shselasky{ 447289567Shselasky if (nents) { 448289567Shselasky iter->sg = sgl; 449289567Shselasky iter->sg_pgoffset = pgoffset - 1; 450289567Shselasky iter->maxents = nents; 451289567Shselasky _sg_iter_next(iter); 452289567Shselasky } else { 453289567Shselasky iter->sg = NULL; 454289567Shselasky iter->sg_pgoffset = 0; 455289567Shselasky iter->maxents = 0; 456289567Shselasky } 457289567Shselasky} 458289567Shselasky 459361204Shselasky/* 460361204Shselasky * sg_page_iter_dma_address() is implemented as a macro because it 461361204Shselasky * needs to accept two different and identical structure types. This 462361204Shselasky * allows both old and new code to co-exist. The compile time assert 463361204Shselasky * adds some safety, that the structure sizes match. 464361204Shselasky */ 465361204Shselasky#define sg_page_iter_dma_address(spi) ({ \ 466361204Shselasky struct sg_page_iter *__spi = (void *)(spi); \ 467361204Shselasky dma_addr_t __dma_address; \ 468361204Shselasky CTASSERT(sizeof(*(spi)) == sizeof(*__spi)); \ 469361204Shselasky __dma_address = __spi->sg->address + \ 470361204Shselasky (__spi->sg_pgoffset << PAGE_SHIFT); \ 471361204Shselasky __dma_address; \ 472361204Shselasky}) 473289567Shselasky 474328653Shselaskystatic inline struct page * 475328653Shselaskysg_page_iter_page(struct sg_page_iter *piter) 476328653Shselasky{ 477328653Shselasky return (nth_page(sg_page(piter->sg), piter->sg_pgoffset)); 478328653Shselasky} 479289567Shselasky 480219820Sjeff 481289682Shselasky#endif /* _LINUX_SCATTERLIST_H_ */ 482