1/* SPDX-License-Identifier: GPL-2.0 */
2#ifndef _LINUX_SCATTERLIST_H
3#define _LINUX_SCATTERLIST_H
4
5#include <linux/string.h>
6#include <linux/types.h>
7#include <linux/bug.h>
8#include <linux/mm.h>
9#include <asm/io.h>
10
11struct scatterlist {
12 unsigned long page_link;
13 unsigned int offset;
14 unsigned int length;
15 dma_addr_t dma_address;
16#ifdef CONFIG_NEED_SG_DMA_LENGTH
17 unsigned int dma_length;
18#endif
19#ifdef CONFIG_PCI_P2PDMA
20 unsigned int dma_flags;
21#endif
22};
23
24/*
25 * These macros should be used after a dma_map_sg call has been done
26 * to get bus addresses of each of the SG entries and their lengths.
27 * You should only work with the number of sg entries dma_map_sg
28 * returns, or alternatively stop on the first sg_dma_len(sg) which
29 * is 0.
30 */
31#define sg_dma_address(sg) ((sg)->dma_address)
32
33#ifdef CONFIG_NEED_SG_DMA_LENGTH
34#define sg_dma_len(sg) ((sg)->dma_length)
35#else
36#define sg_dma_len(sg) ((sg)->length)
37#endif
38
39struct sg_table {
40 struct scatterlist *sgl; /* the list */
41 unsigned int nents; /* number of mapped entries */
42 unsigned int orig_nents; /* original size of list */
43};
44
45struct sg_append_table {
46 struct sg_table sgt; /* The scatter list table */
47 struct scatterlist *prv; /* last populated sge in the table */
48 unsigned int total_nents; /* Total entries in the table */
49};
50
51/*
52 * Notes on SG table design.
53 *
54 * We use the unsigned long page_link field in the scatterlist struct to place
55 * the page pointer AND encode information about the sg table as well. The two
56 * lower bits are reserved for this information.
57 *
58 * If bit 0 is set, then the page_link contains a pointer to the next sg
59 * table list. Otherwise the next entry is at sg + 1.
60 *
61 * If bit 1 is set, then this sg entry is the last element in a list.
62 *
63 * See sg_next().
64 *
65 */
66
67#define SG_CHAIN 0x01UL
68#define SG_END 0x02UL
69
70/*
71 * We overload the LSB of the page pointer to indicate whether it's
72 * a valid sg entry, or whether it points to the start of a new scatterlist.
73 * Those low bits are there for everyone! (thanks mason :-)
74 */
75#define SG_PAGE_LINK_MASK (SG_CHAIN | SG_END)
76
77static inline unsigned int __sg_flags(struct scatterlist *sg)
78{
79 return sg->page_link & SG_PAGE_LINK_MASK;
80}
81
82static inline struct scatterlist *sg_chain_ptr(struct scatterlist *sg)
83{
84 return (struct scatterlist *)(sg->page_link & ~SG_PAGE_LINK_MASK);
85}
86
87static inline bool sg_is_chain(struct scatterlist *sg)
88{
89 return __sg_flags(sg) & SG_CHAIN;
90}
91
92static inline bool sg_is_last(struct scatterlist *sg)
93{
94 return __sg_flags(sg) & SG_END;
95}
96
97/**
98 * sg_assign_page - Assign a given page to an SG entry
99 * @sg: SG entry
100 * @page: The page
101 *
102 * Description:
103 * Assign page to sg entry. Also see sg_set_page(), the most commonly used
104 * variant.
105 *
106 **/
107static inline void sg_assign_page(struct scatterlist *sg, struct page *page)
108{
109 unsigned long page_link = sg->page_link & (SG_CHAIN | SG_END);
110
111 /*
112 * In order for the low bit stealing approach to work, pages
113 * must be aligned at a 32-bit boundary as a minimum.
114 */
115 BUG_ON((unsigned long)page & SG_PAGE_LINK_MASK);
116#ifdef CONFIG_DEBUG_SG
117 BUG_ON(sg_is_chain(sg));
118#endif
119 sg->page_link = page_link | (unsigned long) page;
120}
121
122/**
123 * sg_set_page - Set sg entry to point at given page
124 * @sg: SG entry
125 * @page: The page
126 * @len: Length of data
127 * @offset: Offset into page
128 *
129 * Description:
130 * Use this function to set an sg entry pointing at a page, never assign
131 * the page directly. We encode sg table information in the lower bits
132 * of the page pointer. See sg_page() for looking up the page belonging
133 * to an sg entry.
134 *
135 **/
136static inline void sg_set_page(struct scatterlist *sg, struct page *page,
137 unsigned int len, unsigned int offset)
138{
139 sg_assign_page(sg, page);
140 sg->offset = offset;
141 sg->length = len;
142}
143
144static inline struct page *sg_page(struct scatterlist *sg)
145{
146#ifdef CONFIG_DEBUG_SG
147 BUG_ON(sg_is_chain(sg));
148#endif
149 return (struct page *)((sg)->page_link & ~SG_PAGE_LINK_MASK);
150}
151
152/**
153 * sg_set_buf - Set sg entry to point at given data
154 * @sg: SG entry
155 * @buf: Data
156 * @buflen: Data length
157 *
158 **/
159static inline void sg_set_buf(struct scatterlist *sg, const void *buf,
160 unsigned int buflen)
161{
162#ifdef CONFIG_DEBUG_SG
163 BUG_ON(!virt_addr_valid(buf));
164#endif
165 sg_set_page(sg, virt_to_page(buf), buflen, offset_in_page(buf));
166}
167
168/*
169 * Loop over each sg element, following the pointer to a new list if necessary
170 */
171#define for_each_sg(sglist, sg, nr, __i) \
172 for (__i = 0, sg = (sglist); __i < (nr); __i++, sg = sg_next(sg))
173
174/*
175 * Loop over each sg element in the given sg_table object.
176 */
177#define for_each_sgtable_sg(sgt, sg, i) \
178 for_each_sg((sgt)->sgl, sg, (sgt)->orig_nents, i)
179
180/*
181 * Loop over each sg element in the given *DMA mapped* sg_table object.
182 * Please use sg_dma_address(sg) and sg_dma_len(sg) to extract DMA addresses
183 * of the each element.
184 */
185#define for_each_sgtable_dma_sg(sgt, sg, i) \
186 for_each_sg((sgt)->sgl, sg, (sgt)->nents, i)
187
188static inline void __sg_chain(struct scatterlist *chain_sg,
189 struct scatterlist *sgl)
190{
191 /*
192 * offset and length are unused for chain entry. Clear them.
193 */
194 chain_sg->offset = 0;
195 chain_sg->length = 0;
196
197 /*
198 * Set lowest bit to indicate a link pointer, and make sure to clear
199 * the termination bit if it happens to be set.
200 */
201 chain_sg->page_link = ((unsigned long) sgl | SG_CHAIN) & ~SG_END;
202}
203
204/**
205 * sg_chain - Chain two sglists together
206 * @prv: First scatterlist
207 * @prv_nents: Number of entries in prv
208 * @sgl: Second scatterlist
209 *
210 * Description:
211 * Links @prv@ and @sgl@ together, to form a longer scatterlist.
212 *
213 **/
214static inline void sg_chain(struct scatterlist *prv, unsigned int prv_nents,
215 struct scatterlist *sgl)
216{
217 __sg_chain(&prv[prv_nents - 1], sgl);
218}
219
220/**
221 * sg_mark_end - Mark the end of the scatterlist
222 * @sg: SG entryScatterlist
223 *
224 * Description:
225 * Marks the passed in sg entry as the termination point for the sg
226 * table. A call to sg_next() on this entry will return NULL.
227 *
228 **/
229static inline void sg_mark_end(struct scatterlist *sg)
230{
231 /*
232 * Set termination bit, clear potential chain bit
233 */
234 sg->page_link |= SG_END;
235 sg->page_link &= ~SG_CHAIN;
236}
237
238/**
239 * sg_unmark_end - Undo setting the end of the scatterlist
240 * @sg: SG entryScatterlist
241 *
242 * Description:
243 * Removes the termination marker from the given entry of the scatterlist.
244 *
245 **/
246static inline void sg_unmark_end(struct scatterlist *sg)
247{
248 sg->page_link &= ~SG_END;
249}
250
251/*
252 * CONFGI_PCI_P2PDMA depends on CONFIG_64BIT which means there is 4 bytes
253 * in struct scatterlist (assuming also CONFIG_NEED_SG_DMA_LENGTH is set).
254 * Use this padding for DMA flags bits to indicate when a specific
255 * dma address is a bus address.
256 */
257#ifdef CONFIG_PCI_P2PDMA
258
259#define SG_DMA_BUS_ADDRESS (1 << 0)
260
261/**
262 * sg_dma_is_bus address - Return whether a given segment was marked
263 * as a bus address
264 * @sg: SG entry
265 *
266 * Description:
267 * Returns true if sg_dma_mark_bus_address() has been called on
268 * this segment.
269 **/
270static inline bool sg_is_dma_bus_address(struct scatterlist *sg)
271{
272 return sg->dma_flags & SG_DMA_BUS_ADDRESS;
273}
274
275/**
276 * sg_dma_mark_bus address - Mark the scatterlist entry as a bus address
277 * @sg: SG entry
278 *
279 * Description:
280 * Marks the passed in sg entry to indicate that the dma_address is
281 * a bus address and doesn't need to be unmapped. This should only be
282 * used by dma_map_sg() implementations to mark bus addresses
283 * so they can be properly cleaned up in dma_unmap_sg().
284 **/
285static inline void sg_dma_mark_bus_address(struct scatterlist *sg)
286{
287 sg->dma_flags |= SG_DMA_BUS_ADDRESS;
288}
289
290/**
291 * sg_unmark_bus_address - Unmark the scatterlist entry as a bus address
292 * @sg: SG entry
293 *
294 * Description:
295 * Clears the bus address mark.
296 **/
297static inline void sg_dma_unmark_bus_address(struct scatterlist *sg)
298{
299 sg->dma_flags &= ~SG_DMA_BUS_ADDRESS;
300}
301
302#else
303
304static inline bool sg_is_dma_bus_address(struct scatterlist *sg)
305{
306 return false;
307}
308static inline void sg_dma_mark_bus_address(struct scatterlist *sg)
309{
310}
311static inline void sg_dma_unmark_bus_address(struct scatterlist *sg)
312{
313}
314
315#endif
316
317/**
318 * sg_phys - Return physical address of an sg entry
319 * @sg: SG entry
320 *
321 * Description:
322 * This calls page_to_phys() on the page in this sg entry, and adds the
323 * sg offset. The caller must know that it is legal to call page_to_phys()
324 * on the sg page.
325 *
326 **/
327static inline dma_addr_t sg_phys(struct scatterlist *sg)
328{
329 return page_to_phys(sg_page(sg)) + sg->offset;
330}
331
332/**
333 * sg_virt - Return virtual address of an sg entry
334 * @sg: SG entry
335 *
336 * Description:
337 * This calls page_address() on the page in this sg entry, and adds the
338 * sg offset. The caller must know that the sg page has a valid virtual
339 * mapping.
340 *
341 **/
342static inline void *sg_virt(struct scatterlist *sg)
343{
344 return page_address(sg_page(sg)) + sg->offset;
345}
346
347/**
348 * sg_init_marker - Initialize markers in sg table
349 * @sgl: The SG table
350 * @nents: Number of entries in table
351 *
352 **/
353static inline void sg_init_marker(struct scatterlist *sgl,
354 unsigned int nents)
355{
356 sg_mark_end(&sgl[nents - 1]);
357}
358
359int sg_nents(struct scatterlist *sg);
360int sg_nents_for_len(struct scatterlist *sg, u64 len);
361struct scatterlist *sg_next(struct scatterlist *);
362struct scatterlist *sg_last(struct scatterlist *s, unsigned int);
363void sg_init_table(struct scatterlist *, unsigned int);
364void sg_init_one(struct scatterlist *, const void *, unsigned int);
365int sg_split(struct scatterlist *in, const int in_mapped_nents,
366 const off_t skip, const int nb_splits,
367 const size_t *split_sizes,
368 struct scatterlist **out, int *out_mapped_nents,
369 gfp_t gfp_mask);
370
371typedef struct scatterlist *(sg_alloc_fn)(unsigned int, gfp_t);
372typedef void (sg_free_fn)(struct scatterlist *, unsigned int);
373
374void __sg_free_table(struct sg_table *, unsigned int, unsigned int,
375 sg_free_fn *, unsigned int);
376void sg_free_table(struct sg_table *);
377void sg_free_append_table(struct sg_append_table *sgt);
378int __sg_alloc_table(struct sg_table *, unsigned int, unsigned int,
379 struct scatterlist *, unsigned int, gfp_t, sg_alloc_fn *);
380int sg_alloc_table(struct sg_table *, unsigned int, gfp_t);
381int sg_alloc_append_table_from_pages(struct sg_append_table *sgt,
382 struct page **pages, unsigned int n_pages,
383 unsigned int offset, unsigned long size,
384 unsigned int max_segment,
385 unsigned int left_pages, gfp_t gfp_mask);
386int sg_alloc_table_from_pages_segment(struct sg_table *sgt, struct page **pages,
387 unsigned int n_pages, unsigned int offset,
388 unsigned long size,
389 unsigned int max_segment, gfp_t gfp_mask);
390
391/**
392 * sg_alloc_table_from_pages - Allocate and initialize an sg table from
393 * an array of pages
394 * @sgt: The sg table header to use
395 * @pages: Pointer to an array of page pointers
396 * @n_pages: Number of pages in the pages array
397 * @offset: Offset from start of the first page to the start of a buffer
398 * @size: Number of valid bytes in the buffer (after offset)
399 * @gfp_mask: GFP allocation mask
400 *
401 * Description:
402 * Allocate and initialize an sg table from a list of pages. Contiguous
403 * ranges of the pages are squashed into a single scatterlist node. A user
404 * may provide an offset at a start and a size of valid data in a buffer
405 * specified by the page array. The returned sg table is released by
406 * sg_free_table.
407 *
408 * Returns:
409 * 0 on success, negative error on failure
410 */
411static inline int sg_alloc_table_from_pages(struct sg_table *sgt,
412 struct page **pages,
413 unsigned int n_pages,
414 unsigned int offset,
415 unsigned long size, gfp_t gfp_mask)
416{
417 return sg_alloc_table_from_pages_segment(sgt, pages, n_pages, offset,
418 size, UINT_MAX, gfp_mask);
419}
420
421#ifdef CONFIG_SGL_ALLOC
422struct scatterlist *sgl_alloc_order(unsigned long long length,
423 unsigned int order, bool chainable,
424 gfp_t gfp, unsigned int *nent_p);
425struct scatterlist *sgl_alloc(unsigned long long length, gfp_t gfp,
426 unsigned int *nent_p);
427void sgl_free_n_order(struct scatterlist *sgl, int nents, int order);
428void sgl_free_order(struct scatterlist *sgl, int order);
429void sgl_free(struct scatterlist *sgl);
430#endif /* CONFIG_SGL_ALLOC */
431
432size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
433 size_t buflen, off_t skip, bool to_buffer);
434
435size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
436 const void *buf, size_t buflen);
437size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
438 void *buf, size_t buflen);
439
440size_t sg_pcopy_from_buffer(struct scatterlist *sgl, unsigned int nents,
441 const void *buf, size_t buflen, off_t skip);
442size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
443 void *buf, size_t buflen, off_t skip);
444size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
445 size_t buflen, off_t skip);
446
447/*
448 * Maximum number of entries that will be allocated in one piece, if
449 * a list larger than this is required then chaining will be utilized.
450 */
451#define SG_MAX_SINGLE_ALLOC (PAGE_SIZE / sizeof(struct scatterlist))
452
453/*
454 * The maximum number of SG segments that we will put inside a
455 * scatterlist (unless chaining is used). Should ideally fit inside a
456 * single page, to avoid a higher order allocation. We could define this
457 * to SG_MAX_SINGLE_ALLOC to pack correctly at the highest order. The
458 * minimum value is 32
459 */
460#define SG_CHUNK_SIZE 128
461
462/*
463 * Like SG_CHUNK_SIZE, but for archs that have sg chaining. This limit
464 * is totally arbitrary, a setting of 2048 will get you at least 8mb ios.
465 */
466#ifdef CONFIG_ARCH_NO_SG_CHAIN
467#define SG_MAX_SEGMENTS SG_CHUNK_SIZE
468#else
469#define SG_MAX_SEGMENTS 2048
470#endif
471
472#ifdef CONFIG_SG_POOL
473void sg_free_table_chained(struct sg_table *table,
474 unsigned nents_first_chunk);
475int sg_alloc_table_chained(struct sg_table *table, int nents,
476 struct scatterlist *first_chunk,
477 unsigned nents_first_chunk);
478#endif
479
480/*
481 * sg page iterator
482 *
483 * Iterates over sg entries page-by-page. On each successful iteration, you
484 * can call sg_page_iter_page(@piter) to get the current page.
485 * @piter->sg will point to the sg holding this page and @piter->sg_pgoffset to
486 * the page's page offset within the sg. The iteration will stop either when a
487 * maximum number of sg entries was reached or a terminating sg
488 * (sg_last(sg) == true) was reached.
489 */
490struct sg_page_iter {
491 struct scatterlist *sg; /* sg holding the page */
492 unsigned int sg_pgoffset; /* page offset within the sg */
493
494 /* these are internal states, keep away */
495 unsigned int __nents; /* remaining sg entries */
496 int __pg_advance; /* nr pages to advance at the
497 * next step */
498};
499
500/*
501 * sg page iterator for DMA addresses
502 *
503 * This is the same as sg_page_iter however you can call
504 * sg_page_iter_dma_address(@dma_iter) to get the page's DMA
505 * address. sg_page_iter_page() cannot be called on this iterator.
506 */
507struct sg_dma_page_iter {
508 struct sg_page_iter base;
509};
510
511bool __sg_page_iter_next(struct sg_page_iter *piter);
512bool __sg_page_iter_dma_next(struct sg_dma_page_iter *dma_iter);
513void __sg_page_iter_start(struct sg_page_iter *piter,
514 struct scatterlist *sglist, unsigned int nents,
515 unsigned long pgoffset);
516/**
517 * sg_page_iter_page - get the current page held by the page iterator
518 * @piter: page iterator holding the page
519 */
520static inline struct page *sg_page_iter_page(struct sg_page_iter *piter)
521{
522 return nth_page(sg_page(piter->sg), piter->sg_pgoffset);
523}
524
525/**
526 * sg_page_iter_dma_address - get the dma address of the current page held by
527 * the page iterator.
528 * @dma_iter: page iterator holding the page
529 */
530static inline dma_addr_t
531sg_page_iter_dma_address(struct sg_dma_page_iter *dma_iter)
532{
533 return sg_dma_address(dma_iter->base.sg) +
534 (dma_iter->base.sg_pgoffset << PAGE_SHIFT);
535}
536
537/**
538 * for_each_sg_page - iterate over the pages of the given sg list
539 * @sglist: sglist to iterate over
540 * @piter: page iterator to hold current page, sg, sg_pgoffset
541 * @nents: maximum number of sg entries to iterate over
542 * @pgoffset: starting page offset (in pages)
543 *
544 * Callers may use sg_page_iter_page() to get each page pointer.
545 * In each loop it operates on PAGE_SIZE unit.
546 */
547#define for_each_sg_page(sglist, piter, nents, pgoffset) \
548 for (__sg_page_iter_start((piter), (sglist), (nents), (pgoffset)); \
549 __sg_page_iter_next(piter);)
550
551/**
552 * for_each_sg_dma_page - iterate over the pages of the given sg list
553 * @sglist: sglist to iterate over
554 * @dma_iter: DMA page iterator to hold current page
555 * @dma_nents: maximum number of sg entries to iterate over, this is the value
556 * returned from dma_map_sg
557 * @pgoffset: starting page offset (in pages)
558 *
559 * Callers may use sg_page_iter_dma_address() to get each page's DMA address.
560 * In each loop it operates on PAGE_SIZE unit.
561 */
562#define for_each_sg_dma_page(sglist, dma_iter, dma_nents, pgoffset) \
563 for (__sg_page_iter_start(&(dma_iter)->base, sglist, dma_nents, \
564 pgoffset); \
565 __sg_page_iter_dma_next(dma_iter);)
566
567/**
568 * for_each_sgtable_page - iterate over all pages in the sg_table object
569 * @sgt: sg_table object to iterate over
570 * @piter: page iterator to hold current page
571 * @pgoffset: starting page offset (in pages)
572 *
573 * Iterates over the all memory pages in the buffer described by
574 * a scatterlist stored in the given sg_table object.
575 * See also for_each_sg_page(). In each loop it operates on PAGE_SIZE unit.
576 */
577#define for_each_sgtable_page(sgt, piter, pgoffset) \
578 for_each_sg_page((sgt)->sgl, piter, (sgt)->orig_nents, pgoffset)
579
580/**
581 * for_each_sgtable_dma_page - iterate over the DMA mapped sg_table object
582 * @sgt: sg_table object to iterate over
583 * @dma_iter: DMA page iterator to hold current page
584 * @pgoffset: starting page offset (in pages)
585 *
586 * Iterates over the all DMA mapped pages in the buffer described by
587 * a scatterlist stored in the given sg_table object.
588 * See also for_each_sg_dma_page(). In each loop it operates on PAGE_SIZE
589 * unit.
590 */
591#define for_each_sgtable_dma_page(sgt, dma_iter, pgoffset) \
592 for_each_sg_dma_page((sgt)->sgl, dma_iter, (sgt)->nents, pgoffset)
593
594
595/*
596 * Mapping sg iterator
597 *
598 * Iterates over sg entries mapping page-by-page. On each successful
599 * iteration, @miter->page points to the mapped page and
600 * @miter->length bytes of data can be accessed at @miter->addr. As
601 * long as an iteration is enclosed between start and stop, the user
602 * is free to choose control structure and when to stop.
603 *
604 * @miter->consumed is set to @miter->length on each iteration. It
605 * can be adjusted if the user can't consume all the bytes in one go.
606 * Also, a stopped iteration can be resumed by calling next on it.
607 * This is useful when iteration needs to release all resources and
608 * continue later (e.g. at the next interrupt).
609 */
610
611#define SG_MITER_ATOMIC (1 << 0) /* use kmap_atomic */
612#define SG_MITER_TO_SG (1 << 1) /* flush back to phys on unmap */
613#define SG_MITER_FROM_SG (1 << 2) /* nop */
614
615struct sg_mapping_iter {
616 /* the following three fields can be accessed directly */
617 struct page *page; /* currently mapped page */
618 void *addr; /* pointer to the mapped area */
619 size_t length; /* length of the mapped area */
620 size_t consumed; /* number of consumed bytes */
621 struct sg_page_iter piter; /* page iterator */
622
623 /* these are internal states, keep away */
624 unsigned int __offset; /* offset within page */
625 unsigned int __remaining; /* remaining bytes on page */
626 unsigned int __flags;
627};
628
629void sg_miter_start(struct sg_mapping_iter *miter, struct scatterlist *sgl,
630 unsigned int nents, unsigned int flags);
631bool sg_miter_skip(struct sg_mapping_iter *miter, off_t offset);
632bool sg_miter_next(struct sg_mapping_iter *miter);
633void sg_miter_stop(struct sg_mapping_iter *miter);
634
635#endif /* _LINUX_SCATTERLIST_H */
636

source code of linux/include/linux/scatterlist.h