1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3  * Copyright (C) 2007 Jens Axboe <jens.axboe@oracle.com>
4  *
5  * Scatterlist handling helpers.
6  */
7 #include <linux/export.h>
8 #include <linux/slab.h>
9 #include <linux/scatterlist.h>
10 #include <linux/highmem.h>
11 #include <linux/kmemleak.h>
12 
13 /**
14  * sg_next - return the next scatterlist entry in a list
15  * @sg:		The current sg entry
16  *
17  * Description:
18  *   Usually the next entry will be @sg@ + 1, but if this sg element is part
19  *   of a chained scatterlist, it could jump to the start of a new
20  *   scatterlist array.
21  *
22  **/
sg_next(struct scatterlist * sg)23 struct scatterlist *sg_next(struct scatterlist *sg)
24 {
25 	if (sg_is_last(sg))
26 		return NULL;
27 
28 	sg++;
29 	if (unlikely(sg_is_chain(sg)))
30 		sg = sg_chain_ptr(sg);
31 
32 	return sg;
33 }
34 EXPORT_SYMBOL(sg_next);
35 
36 /**
37  * sg_nents - return total count of entries in scatterlist
38  * @sg:		The scatterlist
39  *
40  * Description:
41  * Allows to know how many entries are in sg, taking into account
42  * chaining as well
43  *
44  **/
sg_nents(struct scatterlist * sg)45 int sg_nents(struct scatterlist *sg)
46 {
47 	int nents;
48 	for (nents = 0; sg; sg = sg_next(sg))
49 		nents++;
50 	return nents;
51 }
52 EXPORT_SYMBOL(sg_nents);
53 
54 /**
55  * sg_nents_for_len - return total count of entries in scatterlist
56  *                    needed to satisfy the supplied length
57  * @sg:		The scatterlist
58  * @len:	The total required length
59  *
60  * Description:
61  * Determines the number of entries in sg that are required to meet
62  * the supplied length, taking into account chaining as well
63  *
64  * Returns:
65  *   the number of sg entries needed, negative error on failure
66  *
67  **/
sg_nents_for_len(struct scatterlist * sg,u64 len)68 int sg_nents_for_len(struct scatterlist *sg, u64 len)
69 {
70 	int nents;
71 	u64 total;
72 
73 	if (!len)
74 		return 0;
75 
76 	for (nents = 0, total = 0; sg; sg = sg_next(sg)) {
77 		nents++;
78 		total += sg->length;
79 		if (total >= len)
80 			return nents;
81 	}
82 
83 	return -EINVAL;
84 }
85 EXPORT_SYMBOL(sg_nents_for_len);
86 
87 /**
88  * sg_last - return the last scatterlist entry in a list
89  * @sgl:	First entry in the scatterlist
90  * @nents:	Number of entries in the scatterlist
91  *
92  * Description:
93  *   Should only be used casually, it (currently) scans the entire list
94  *   to get the last entry.
95  *
96  *   Note that the @sgl@ pointer passed in need not be the first one,
97  *   the important bit is that @nents@ denotes the number of entries that
98  *   exist from @sgl@.
99  *
100  **/
sg_last(struct scatterlist * sgl,unsigned int nents)101 struct scatterlist *sg_last(struct scatterlist *sgl, unsigned int nents)
102 {
103 	struct scatterlist *sg, *ret = NULL;
104 	unsigned int i;
105 
106 	for_each_sg(sgl, sg, nents, i)
107 		ret = sg;
108 
109 	BUG_ON(!sg_is_last(ret));
110 	return ret;
111 }
112 EXPORT_SYMBOL(sg_last);
113 
114 /**
115  * sg_init_table - Initialize SG table
116  * @sgl:	   The SG table
117  * @nents:	   Number of entries in table
118  *
119  * Notes:
120  *   If this is part of a chained sg table, sg_mark_end() should be
121  *   used only on the last table part.
122  *
123  **/
sg_init_table(struct scatterlist * sgl,unsigned int nents)124 void sg_init_table(struct scatterlist *sgl, unsigned int nents)
125 {
126 	memset(sgl, 0, sizeof(*sgl) * nents);
127 	sg_init_marker(sgl, nents);
128 }
129 EXPORT_SYMBOL(sg_init_table);
130 
131 /**
132  * sg_init_one - Initialize a single entry sg list
133  * @sg:		 SG entry
134  * @buf:	 Virtual address for IO
135  * @buflen:	 IO length
136  *
137  **/
sg_init_one(struct scatterlist * sg,const void * buf,unsigned int buflen)138 void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
139 {
140 	sg_init_table(sg, 1);
141 	sg_set_buf(sg, buf, buflen);
142 }
143 EXPORT_SYMBOL(sg_init_one);
144 
145 /*
146  * The default behaviour of sg_alloc_table() is to use these kmalloc/kfree
147  * helpers.
148  */
sg_kmalloc(unsigned int nents,gfp_t gfp_mask)149 static struct scatterlist *sg_kmalloc(unsigned int nents, gfp_t gfp_mask)
150 {
151 	if (nents == SG_MAX_SINGLE_ALLOC) {
152 		/*
153 		 * Kmemleak doesn't track page allocations as they are not
154 		 * commonly used (in a raw form) for kernel data structures.
155 		 * As we chain together a list of pages and then a normal
156 		 * kmalloc (tracked by kmemleak), in order to for that last
157 		 * allocation not to become decoupled (and thus a
158 		 * false-positive) we need to inform kmemleak of all the
159 		 * intermediate allocations.
160 		 */
161 		void *ptr = (void *) __get_free_page(gfp_mask);
162 		kmemleak_alloc(ptr, PAGE_SIZE, 1, gfp_mask);
163 		return ptr;
164 	} else
165 		return kmalloc_array(nents, sizeof(struct scatterlist),
166 				     gfp_mask);
167 }
168 
sg_kfree(struct scatterlist * sg,unsigned int nents)169 static void sg_kfree(struct scatterlist *sg, unsigned int nents)
170 {
171 	if (nents == SG_MAX_SINGLE_ALLOC) {
172 		kmemleak_free(sg);
173 		free_page((unsigned long) sg);
174 	} else
175 		kfree(sg);
176 }
177 
178 /**
179  * __sg_free_table - Free a previously mapped sg table
180  * @table:	The sg table header to use
181  * @max_ents:	The maximum number of entries per single scatterlist
182  * @nents_first_chunk: Number of entries int the (preallocated) first
183  * 	scatterlist chunk, 0 means no such preallocated first chunk
184  * @free_fn:	Free function
185  * @num_ents:	Number of entries in the table
186  *
187  *  Description:
188  *    Free an sg table previously allocated and setup with
189  *    __sg_alloc_table().  The @max_ents value must be identical to
190  *    that previously used with __sg_alloc_table().
191  *
192  **/
__sg_free_table(struct sg_table * table,unsigned int max_ents,unsigned int nents_first_chunk,sg_free_fn * free_fn,unsigned int num_ents)193 void __sg_free_table(struct sg_table *table, unsigned int max_ents,
194 		     unsigned int nents_first_chunk, sg_free_fn *free_fn,
195 		     unsigned int num_ents)
196 {
197 	struct scatterlist *sgl, *next;
198 	unsigned curr_max_ents = nents_first_chunk ?: max_ents;
199 
200 	if (unlikely(!table->sgl))
201 		return;
202 
203 	sgl = table->sgl;
204 	while (num_ents) {
205 		unsigned int alloc_size = num_ents;
206 		unsigned int sg_size;
207 
208 		/*
209 		 * If we have more than max_ents segments left,
210 		 * then assign 'next' to the sg table after the current one.
211 		 * sg_size is then one less than alloc size, since the last
212 		 * element is the chain pointer.
213 		 */
214 		if (alloc_size > curr_max_ents) {
215 			next = sg_chain_ptr(&sgl[curr_max_ents - 1]);
216 			alloc_size = curr_max_ents;
217 			sg_size = alloc_size - 1;
218 		} else {
219 			sg_size = alloc_size;
220 			next = NULL;
221 		}
222 
223 		num_ents -= sg_size;
224 		if (nents_first_chunk)
225 			nents_first_chunk = 0;
226 		else
227 			free_fn(sgl, alloc_size);
228 		sgl = next;
229 		curr_max_ents = max_ents;
230 	}
231 
232 	table->sgl = NULL;
233 }
234 EXPORT_SYMBOL(__sg_free_table);
235 
236 /**
237  * sg_free_append_table - Free a previously allocated append sg table.
238  * @table:	 The mapped sg append table header
239  *
240  **/
sg_free_append_table(struct sg_append_table * table)241 void sg_free_append_table(struct sg_append_table *table)
242 {
243 	__sg_free_table(&table->sgt, SG_MAX_SINGLE_ALLOC, 0, sg_kfree,
244 			table->total_nents);
245 }
246 EXPORT_SYMBOL(sg_free_append_table);
247 
248 
249 /**
250  * sg_free_table - Free a previously allocated sg table
251  * @table:	The mapped sg table header
252  *
253  **/
sg_free_table(struct sg_table * table)254 void sg_free_table(struct sg_table *table)
255 {
256 	__sg_free_table(table, SG_MAX_SINGLE_ALLOC, 0, sg_kfree,
257 			table->orig_nents);
258 }
259 EXPORT_SYMBOL(sg_free_table);
260 
261 /**
262  * __sg_alloc_table - Allocate and initialize an sg table with given allocator
263  * @table:	The sg table header to use
264  * @nents:	Number of entries in sg list
265  * @max_ents:	The maximum number of entries the allocator returns per call
266  * @nents_first_chunk: Number of entries int the (preallocated) first
267  * 	scatterlist chunk, 0 means no such preallocated chunk provided by user
268  * @gfp_mask:	GFP allocation mask
269  * @alloc_fn:	Allocator to use
270  *
271  * Description:
272  *   This function returns a @table @nents long. The allocator is
273  *   defined to return scatterlist chunks of maximum size @max_ents.
274  *   Thus if @nents is bigger than @max_ents, the scatterlists will be
275  *   chained in units of @max_ents.
276  *
277  * Notes:
278  *   If this function returns non-0 (eg failure), the caller must call
279  *   __sg_free_table() to cleanup any leftover allocations.
280  *
281  **/
__sg_alloc_table(struct sg_table * table,unsigned int nents,unsigned int max_ents,struct scatterlist * first_chunk,unsigned int nents_first_chunk,gfp_t gfp_mask,sg_alloc_fn * alloc_fn)282 int __sg_alloc_table(struct sg_table *table, unsigned int nents,
283 		     unsigned int max_ents, struct scatterlist *first_chunk,
284 		     unsigned int nents_first_chunk, gfp_t gfp_mask,
285 		     sg_alloc_fn *alloc_fn)
286 {
287 	struct scatterlist *sg, *prv;
288 	unsigned int left;
289 	unsigned curr_max_ents = nents_first_chunk ?: max_ents;
290 	unsigned prv_max_ents;
291 
292 	memset(table, 0, sizeof(*table));
293 
294 	if (nents == 0)
295 		return -EINVAL;
296 #ifdef CONFIG_ARCH_NO_SG_CHAIN
297 	if (WARN_ON_ONCE(nents > max_ents))
298 		return -EINVAL;
299 #endif
300 
301 	left = nents;
302 	prv = NULL;
303 	do {
304 		unsigned int sg_size, alloc_size = left;
305 
306 		if (alloc_size > curr_max_ents) {
307 			alloc_size = curr_max_ents;
308 			sg_size = alloc_size - 1;
309 		} else
310 			sg_size = alloc_size;
311 
312 		left -= sg_size;
313 
314 		if (first_chunk) {
315 			sg = first_chunk;
316 			first_chunk = NULL;
317 		} else {
318 			sg = alloc_fn(alloc_size, gfp_mask);
319 		}
320 		if (unlikely(!sg)) {
321 			/*
322 			 * Adjust entry count to reflect that the last
323 			 * entry of the previous table won't be used for
324 			 * linkage.  Without this, sg_kfree() may get
325 			 * confused.
326 			 */
327 			if (prv)
328 				table->nents = ++table->orig_nents;
329 
330 			return -ENOMEM;
331 		}
332 
333 		sg_init_table(sg, alloc_size);
334 		table->nents = table->orig_nents += sg_size;
335 
336 		/*
337 		 * If this is the first mapping, assign the sg table header.
338 		 * If this is not the first mapping, chain previous part.
339 		 */
340 		if (prv)
341 			sg_chain(prv, prv_max_ents, sg);
342 		else
343 			table->sgl = sg;
344 
345 		/*
346 		 * If no more entries after this one, mark the end
347 		 */
348 		if (!left)
349 			sg_mark_end(&sg[sg_size - 1]);
350 
351 		prv = sg;
352 		prv_max_ents = curr_max_ents;
353 		curr_max_ents = max_ents;
354 	} while (left);
355 
356 	return 0;
357 }
358 EXPORT_SYMBOL(__sg_alloc_table);
359 
360 /**
361  * sg_alloc_table - Allocate and initialize an sg table
362  * @table:	The sg table header to use
363  * @nents:	Number of entries in sg list
364  * @gfp_mask:	GFP allocation mask
365  *
366  *  Description:
367  *    Allocate and initialize an sg table. If @nents@ is larger than
368  *    SG_MAX_SINGLE_ALLOC a chained sg table will be setup.
369  *
370  **/
sg_alloc_table(struct sg_table * table,unsigned int nents,gfp_t gfp_mask)371 int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
372 {
373 	int ret;
374 
375 	ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC,
376 			       NULL, 0, gfp_mask, sg_kmalloc);
377 	if (unlikely(ret))
378 		sg_free_table(table);
379 	return ret;
380 }
381 EXPORT_SYMBOL(sg_alloc_table);
382 
get_next_sg(struct sg_append_table * table,struct scatterlist * cur,unsigned long needed_sges,gfp_t gfp_mask)383 static struct scatterlist *get_next_sg(struct sg_append_table *table,
384 				       struct scatterlist *cur,
385 				       unsigned long needed_sges,
386 				       gfp_t gfp_mask)
387 {
388 	struct scatterlist *new_sg, *next_sg;
389 	unsigned int alloc_size;
390 
391 	if (cur) {
392 		next_sg = sg_next(cur);
393 		/* Check if last entry should be keeped for chainning */
394 		if (!sg_is_last(next_sg) || needed_sges == 1)
395 			return next_sg;
396 	}
397 
398 	alloc_size = min_t(unsigned long, needed_sges, SG_MAX_SINGLE_ALLOC);
399 	new_sg = sg_kmalloc(alloc_size, gfp_mask);
400 	if (!new_sg)
401 		return ERR_PTR(-ENOMEM);
402 	sg_init_table(new_sg, alloc_size);
403 	if (cur) {
404 		table->total_nents += alloc_size - 1;
405 		__sg_chain(next_sg, new_sg);
406 	} else {
407 		table->sgt.sgl = new_sg;
408 		table->total_nents = alloc_size;
409 	}
410 	return new_sg;
411 }
412 
pages_are_mergeable(struct page * a,struct page * b)413 static bool pages_are_mergeable(struct page *a, struct page *b)
414 {
415 	if (page_to_pfn(a) != page_to_pfn(b) + 1)
416 		return false;
417 	if (!zone_device_pages_have_same_pgmap(a, b))
418 		return false;
419 	return true;
420 }
421 
422 /**
423  * sg_alloc_append_table_from_pages - Allocate and initialize an append sg
424  *                                    table from an array of pages
425  * @sgt_append:  The sg append table to use
426  * @pages:       Pointer to an array of page pointers
427  * @n_pages:     Number of pages in the pages array
428  * @offset:      Offset from start of the first page to the start of a buffer
429  * @size:        Number of valid bytes in the buffer (after offset)
430  * @max_segment: Maximum size of a scatterlist element in bytes
431  * @left_pages:  Left pages caller have to set after this call
432  * @gfp_mask:	 GFP allocation mask
433  *
434  * Description:
435  *    In the first call it allocate and initialize an sg table from a list of
436  *    pages, else reuse the scatterlist from sgt_append. Contiguous ranges of
437  *    the pages are squashed into a single scatterlist entry up to the maximum
438  *    size specified in @max_segment.  A user may provide an offset at a start
439  *    and a size of valid data in a buffer specified by the page array. The
440  *    returned sg table is released by sg_free_append_table
441  *
442  * Returns:
443  *   0 on success, negative error on failure
444  *
445  * Notes:
446  *   If this function returns non-0 (eg failure), the caller must call
447  *   sg_free_append_table() to cleanup any leftover allocations.
448  *
449  *   In the fist call, sgt_append must by initialized.
450  */
sg_alloc_append_table_from_pages(struct sg_append_table * sgt_append,struct page ** pages,unsigned int n_pages,unsigned int offset,unsigned long size,unsigned int max_segment,unsigned int left_pages,gfp_t gfp_mask)451 int sg_alloc_append_table_from_pages(struct sg_append_table *sgt_append,
452 		struct page **pages, unsigned int n_pages, unsigned int offset,
453 		unsigned long size, unsigned int max_segment,
454 		unsigned int left_pages, gfp_t gfp_mask)
455 {
456 	unsigned int chunks, cur_page, seg_len, i, prv_len = 0;
457 	unsigned int added_nents = 0;
458 	struct scatterlist *s = sgt_append->prv;
459 	struct page *last_pg;
460 
461 	/*
462 	 * The algorithm below requires max_segment to be aligned to PAGE_SIZE
463 	 * otherwise it can overshoot.
464 	 */
465 	max_segment = ALIGN_DOWN(max_segment, PAGE_SIZE);
466 	if (WARN_ON(max_segment < PAGE_SIZE))
467 		return -EINVAL;
468 
469 	if (IS_ENABLED(CONFIG_ARCH_NO_SG_CHAIN) && sgt_append->prv)
470 		return -EOPNOTSUPP;
471 
472 	if (sgt_append->prv) {
473 		unsigned long next_pfn = (page_to_phys(sg_page(sgt_append->prv)) +
474 			sgt_append->prv->offset + sgt_append->prv->length) / PAGE_SIZE;
475 
476 		if (WARN_ON(offset))
477 			return -EINVAL;
478 
479 		/* Merge contiguous pages into the last SG */
480 		prv_len = sgt_append->prv->length;
481 		if (page_to_pfn(pages[0]) == next_pfn) {
482 			last_pg = pfn_to_page(next_pfn - 1);
483 			while (n_pages && pages_are_mergeable(pages[0], last_pg)) {
484 				if (sgt_append->prv->length + PAGE_SIZE > max_segment)
485 					break;
486 				sgt_append->prv->length += PAGE_SIZE;
487 				last_pg = pages[0];
488 				pages++;
489 				n_pages--;
490 			}
491 			if (!n_pages)
492 				goto out;
493 		}
494 	}
495 
496 	/* compute number of contiguous chunks */
497 	chunks = 1;
498 	seg_len = 0;
499 	for (i = 1; i < n_pages; i++) {
500 		seg_len += PAGE_SIZE;
501 		if (seg_len >= max_segment ||
502 		    !pages_are_mergeable(pages[i], pages[i - 1])) {
503 			chunks++;
504 			seg_len = 0;
505 		}
506 	}
507 
508 	/* merging chunks and putting them into the scatterlist */
509 	cur_page = 0;
510 	for (i = 0; i < chunks; i++) {
511 		unsigned int j, chunk_size;
512 
513 		/* look for the end of the current chunk */
514 		seg_len = 0;
515 		for (j = cur_page + 1; j < n_pages; j++) {
516 			seg_len += PAGE_SIZE;
517 			if (seg_len >= max_segment ||
518 			    !pages_are_mergeable(pages[j], pages[j - 1]))
519 				break;
520 		}
521 
522 		/* Pass how many chunks might be left */
523 		s = get_next_sg(sgt_append, s, chunks - i + left_pages,
524 				gfp_mask);
525 		if (IS_ERR(s)) {
526 			/*
527 			 * Adjust entry length to be as before function was
528 			 * called.
529 			 */
530 			if (sgt_append->prv)
531 				sgt_append->prv->length = prv_len;
532 			return PTR_ERR(s);
533 		}
534 		chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
535 		sg_set_page(s, pages[cur_page],
536 			    min_t(unsigned long, size, chunk_size), offset);
537 		added_nents++;
538 		size -= chunk_size;
539 		offset = 0;
540 		cur_page = j;
541 	}
542 	sgt_append->sgt.nents += added_nents;
543 	sgt_append->sgt.orig_nents = sgt_append->sgt.nents;
544 	sgt_append->prv = s;
545 out:
546 	if (!left_pages)
547 		sg_mark_end(s);
548 	return 0;
549 }
550 EXPORT_SYMBOL(sg_alloc_append_table_from_pages);
551 
552 /**
553  * sg_alloc_table_from_pages_segment - Allocate and initialize an sg table from
554  *                                     an array of pages and given maximum
555  *                                     segment.
556  * @sgt:	 The sg table header to use
557  * @pages:	 Pointer to an array of page pointers
558  * @n_pages:	 Number of pages in the pages array
559  * @offset:      Offset from start of the first page to the start of a buffer
560  * @size:        Number of valid bytes in the buffer (after offset)
561  * @max_segment: Maximum size of a scatterlist element in bytes
562  * @gfp_mask:	 GFP allocation mask
563  *
564  *  Description:
565  *    Allocate and initialize an sg table from a list of pages. Contiguous
566  *    ranges of the pages are squashed into a single scatterlist node up to the
567  *    maximum size specified in @max_segment. A user may provide an offset at a
568  *    start and a size of valid data in a buffer specified by the page array.
569  *
570  *    The returned sg table is released by sg_free_table.
571  *
572  *  Returns:
573  *   0 on success, negative error on failure
574  */
sg_alloc_table_from_pages_segment(struct sg_table * sgt,struct page ** pages,unsigned int n_pages,unsigned int offset,unsigned long size,unsigned int max_segment,gfp_t gfp_mask)575 int sg_alloc_table_from_pages_segment(struct sg_table *sgt, struct page **pages,
576 				unsigned int n_pages, unsigned int offset,
577 				unsigned long size, unsigned int max_segment,
578 				gfp_t gfp_mask)
579 {
580 	struct sg_append_table append = {};
581 	int err;
582 
583 	err = sg_alloc_append_table_from_pages(&append, pages, n_pages, offset,
584 					       size, max_segment, 0, gfp_mask);
585 	if (err) {
586 		sg_free_append_table(&append);
587 		return err;
588 	}
589 	memcpy(sgt, &append.sgt, sizeof(*sgt));
590 	WARN_ON(append.total_nents != sgt->orig_nents);
591 	return 0;
592 }
593 EXPORT_SYMBOL(sg_alloc_table_from_pages_segment);
594 
595 #ifdef CONFIG_SGL_ALLOC
596 
597 /**
598  * sgl_alloc_order - allocate a scatterlist and its pages
599  * @length: Length in bytes of the scatterlist. Must be at least one
600  * @order: Second argument for alloc_pages()
601  * @chainable: Whether or not to allocate an extra element in the scatterlist
602  *	for scatterlist chaining purposes
603  * @gfp: Memory allocation flags
604  * @nent_p: [out] Number of entries in the scatterlist that have pages
605  *
606  * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
607  */
sgl_alloc_order(unsigned long long length,unsigned int order,bool chainable,gfp_t gfp,unsigned int * nent_p)608 struct scatterlist *sgl_alloc_order(unsigned long long length,
609 				    unsigned int order, bool chainable,
610 				    gfp_t gfp, unsigned int *nent_p)
611 {
612 	struct scatterlist *sgl, *sg;
613 	struct page *page;
614 	unsigned int nent, nalloc;
615 	u32 elem_len;
616 
617 	nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
618 	/* Check for integer overflow */
619 	if (length > (nent << (PAGE_SHIFT + order)))
620 		return NULL;
621 	nalloc = nent;
622 	if (chainable) {
623 		/* Check for integer overflow */
624 		if (nalloc + 1 < nalloc)
625 			return NULL;
626 		nalloc++;
627 	}
628 	sgl = kmalloc_array(nalloc, sizeof(struct scatterlist),
629 			    gfp & ~GFP_DMA);
630 	if (!sgl)
631 		return NULL;
632 
633 	sg_init_table(sgl, nalloc);
634 	sg = sgl;
635 	while (length) {
636 		elem_len = min_t(u64, length, PAGE_SIZE << order);
637 		page = alloc_pages(gfp, order);
638 		if (!page) {
639 			sgl_free_order(sgl, order);
640 			return NULL;
641 		}
642 
643 		sg_set_page(sg, page, elem_len, 0);
644 		length -= elem_len;
645 		sg = sg_next(sg);
646 	}
647 	WARN_ONCE(length, "length = %lld\n", length);
648 	if (nent_p)
649 		*nent_p = nent;
650 	return sgl;
651 }
652 EXPORT_SYMBOL(sgl_alloc_order);
653 
654 /**
655  * sgl_alloc - allocate a scatterlist and its pages
656  * @length: Length in bytes of the scatterlist
657  * @gfp: Memory allocation flags
658  * @nent_p: [out] Number of entries in the scatterlist
659  *
660  * Returns: A pointer to an initialized scatterlist or %NULL upon failure.
661  */
sgl_alloc(unsigned long long length,gfp_t gfp,unsigned int * nent_p)662 struct scatterlist *sgl_alloc(unsigned long long length, gfp_t gfp,
663 			      unsigned int *nent_p)
664 {
665 	return sgl_alloc_order(length, 0, false, gfp, nent_p);
666 }
667 EXPORT_SYMBOL(sgl_alloc);
668 
669 /**
670  * sgl_free_n_order - free a scatterlist and its pages
671  * @sgl: Scatterlist with one or more elements
672  * @nents: Maximum number of elements to free
673  * @order: Second argument for __free_pages()
674  *
675  * Notes:
676  * - If several scatterlists have been chained and each chain element is
677  *   freed separately then it's essential to set nents correctly to avoid that a
678  *   page would get freed twice.
679  * - All pages in a chained scatterlist can be freed at once by setting @nents
680  *   to a high number.
681  */
sgl_free_n_order(struct scatterlist * sgl,int nents,int order)682 void sgl_free_n_order(struct scatterlist *sgl, int nents, int order)
683 {
684 	struct scatterlist *sg;
685 	struct page *page;
686 	int i;
687 
688 	for_each_sg(sgl, sg, nents, i) {
689 		if (!sg)
690 			break;
691 		page = sg_page(sg);
692 		if (page)
693 			__free_pages(page, order);
694 	}
695 	kfree(sgl);
696 }
697 EXPORT_SYMBOL(sgl_free_n_order);
698 
699 /**
700  * sgl_free_order - free a scatterlist and its pages
701  * @sgl: Scatterlist with one or more elements
702  * @order: Second argument for __free_pages()
703  */
sgl_free_order(struct scatterlist * sgl,int order)704 void sgl_free_order(struct scatterlist *sgl, int order)
705 {
706 	sgl_free_n_order(sgl, INT_MAX, order);
707 }
708 EXPORT_SYMBOL(sgl_free_order);
709 
710 /**
711  * sgl_free - free a scatterlist and its pages
712  * @sgl: Scatterlist with one or more elements
713  */
sgl_free(struct scatterlist * sgl)714 void sgl_free(struct scatterlist *sgl)
715 {
716 	sgl_free_order(sgl, 0);
717 }
718 EXPORT_SYMBOL(sgl_free);
719 
720 #endif /* CONFIG_SGL_ALLOC */
721 
__sg_page_iter_start(struct sg_page_iter * piter,struct scatterlist * sglist,unsigned int nents,unsigned long pgoffset)722 void __sg_page_iter_start(struct sg_page_iter *piter,
723 			  struct scatterlist *sglist, unsigned int nents,
724 			  unsigned long pgoffset)
725 {
726 	piter->__pg_advance = 0;
727 	piter->__nents = nents;
728 
729 	piter->sg = sglist;
730 	piter->sg_pgoffset = pgoffset;
731 }
732 EXPORT_SYMBOL(__sg_page_iter_start);
733 
sg_page_count(struct scatterlist * sg)734 static int sg_page_count(struct scatterlist *sg)
735 {
736 	return PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT;
737 }
738 
__sg_page_iter_next(struct sg_page_iter * piter)739 bool __sg_page_iter_next(struct sg_page_iter *piter)
740 {
741 	if (!piter->__nents || !piter->sg)
742 		return false;
743 
744 	piter->sg_pgoffset += piter->__pg_advance;
745 	piter->__pg_advance = 1;
746 
747 	while (piter->sg_pgoffset >= sg_page_count(piter->sg)) {
748 		piter->sg_pgoffset -= sg_page_count(piter->sg);
749 		piter->sg = sg_next(piter->sg);
750 		if (!--piter->__nents || !piter->sg)
751 			return false;
752 	}
753 
754 	return true;
755 }
756 EXPORT_SYMBOL(__sg_page_iter_next);
757 
sg_dma_page_count(struct scatterlist * sg)758 static int sg_dma_page_count(struct scatterlist *sg)
759 {
760 	return PAGE_ALIGN(sg->offset + sg_dma_len(sg)) >> PAGE_SHIFT;
761 }
762 
__sg_page_iter_dma_next(struct sg_dma_page_iter * dma_iter)763 bool __sg_page_iter_dma_next(struct sg_dma_page_iter *dma_iter)
764 {
765 	struct sg_page_iter *piter = &dma_iter->base;
766 
767 	if (!piter->__nents || !piter->sg)
768 		return false;
769 
770 	piter->sg_pgoffset += piter->__pg_advance;
771 	piter->__pg_advance = 1;
772 
773 	while (piter->sg_pgoffset >= sg_dma_page_count(piter->sg)) {
774 		piter->sg_pgoffset -= sg_dma_page_count(piter->sg);
775 		piter->sg = sg_next(piter->sg);
776 		if (!--piter->__nents || !piter->sg)
777 			return false;
778 	}
779 
780 	return true;
781 }
782 EXPORT_SYMBOL(__sg_page_iter_dma_next);
783 
784 /**
785  * sg_miter_start - start mapping iteration over a sg list
786  * @miter: sg mapping iter to be started
787  * @sgl: sg list to iterate over
788  * @nents: number of sg entries
789  *
790  * Description:
791  *   Starts mapping iterator @miter.
792  *
793  * Context:
794  *   Don't care.
795  */
sg_miter_start(struct sg_mapping_iter * miter,struct scatterlist * sgl,unsigned int nents,unsigned int flags)796 void sg_miter_start(struct sg_mapping_iter *miter, struct scatterlist *sgl,
797 		    unsigned int nents, unsigned int flags)
798 {
799 	memset(miter, 0, sizeof(struct sg_mapping_iter));
800 
801 	__sg_page_iter_start(&miter->piter, sgl, nents, 0);
802 	WARN_ON(!(flags & (SG_MITER_TO_SG | SG_MITER_FROM_SG)));
803 	miter->__flags = flags;
804 }
805 EXPORT_SYMBOL(sg_miter_start);
806 
sg_miter_get_next_page(struct sg_mapping_iter * miter)807 static bool sg_miter_get_next_page(struct sg_mapping_iter *miter)
808 {
809 	if (!miter->__remaining) {
810 		struct scatterlist *sg;
811 
812 		if (!__sg_page_iter_next(&miter->piter))
813 			return false;
814 
815 		sg = miter->piter.sg;
816 
817 		miter->__offset = miter->piter.sg_pgoffset ? 0 : sg->offset;
818 		miter->piter.sg_pgoffset += miter->__offset >> PAGE_SHIFT;
819 		miter->__offset &= PAGE_SIZE - 1;
820 		miter->__remaining = sg->offset + sg->length -
821 				     (miter->piter.sg_pgoffset << PAGE_SHIFT) -
822 				     miter->__offset;
823 		miter->__remaining = min_t(unsigned long, miter->__remaining,
824 					   PAGE_SIZE - miter->__offset);
825 	}
826 
827 	return true;
828 }
829 
830 /**
831  * sg_miter_skip - reposition mapping iterator
832  * @miter: sg mapping iter to be skipped
833  * @offset: number of bytes to plus the current location
834  *
835  * Description:
836  *   Sets the offset of @miter to its current location plus @offset bytes.
837  *   If mapping iterator @miter has been proceeded by sg_miter_next(), this
838  *   stops @miter.
839  *
840  * Context:
841  *   Don't care.
842  *
843  * Returns:
844  *   true if @miter contains the valid mapping.  false if end of sg
845  *   list is reached.
846  */
sg_miter_skip(struct sg_mapping_iter * miter,off_t offset)847 bool sg_miter_skip(struct sg_mapping_iter *miter, off_t offset)
848 {
849 	sg_miter_stop(miter);
850 
851 	while (offset) {
852 		off_t consumed;
853 
854 		if (!sg_miter_get_next_page(miter))
855 			return false;
856 
857 		consumed = min_t(off_t, offset, miter->__remaining);
858 		miter->__offset += consumed;
859 		miter->__remaining -= consumed;
860 		offset -= consumed;
861 	}
862 
863 	return true;
864 }
865 EXPORT_SYMBOL(sg_miter_skip);
866 
867 /**
868  * sg_miter_next - proceed mapping iterator to the next mapping
869  * @miter: sg mapping iter to proceed
870  *
871  * Description:
872  *   Proceeds @miter to the next mapping.  @miter should have been started
873  *   using sg_miter_start().  On successful return, @miter->page,
874  *   @miter->addr and @miter->length point to the current mapping.
875  *
876  * Context:
877  *   May sleep if !SG_MITER_ATOMIC.
878  *
879  * Returns:
880  *   true if @miter contains the next mapping.  false if end of sg
881  *   list is reached.
882  */
sg_miter_next(struct sg_mapping_iter * miter)883 bool sg_miter_next(struct sg_mapping_iter *miter)
884 {
885 	sg_miter_stop(miter);
886 
887 	/*
888 	 * Get to the next page if necessary.
889 	 * __remaining, __offset is adjusted by sg_miter_stop
890 	 */
891 	if (!sg_miter_get_next_page(miter))
892 		return false;
893 
894 	miter->page = sg_page_iter_page(&miter->piter);
895 	miter->consumed = miter->length = miter->__remaining;
896 
897 	if (miter->__flags & SG_MITER_ATOMIC)
898 		miter->addr = kmap_atomic(miter->page) + miter->__offset;
899 	else
900 		miter->addr = kmap(miter->page) + miter->__offset;
901 
902 	return true;
903 }
904 EXPORT_SYMBOL(sg_miter_next);
905 
906 /**
907  * sg_miter_stop - stop mapping iteration
908  * @miter: sg mapping iter to be stopped
909  *
910  * Description:
911  *   Stops mapping iterator @miter.  @miter should have been started
912  *   using sg_miter_start().  A stopped iteration can be resumed by
913  *   calling sg_miter_next() on it.  This is useful when resources (kmap)
914  *   need to be released during iteration.
915  *
916  * Context:
917  *   Don't care otherwise.
918  */
sg_miter_stop(struct sg_mapping_iter * miter)919 void sg_miter_stop(struct sg_mapping_iter *miter)
920 {
921 	WARN_ON(miter->consumed > miter->length);
922 
923 	/* drop resources from the last iteration */
924 	if (miter->addr) {
925 		miter->__offset += miter->consumed;
926 		miter->__remaining -= miter->consumed;
927 
928 		if (miter->__flags & SG_MITER_TO_SG)
929 			flush_dcache_page(miter->page);
930 
931 		if (miter->__flags & SG_MITER_ATOMIC) {
932 			WARN_ON_ONCE(!pagefault_disabled());
933 			kunmap_atomic(miter->addr);
934 		} else
935 			kunmap(miter->page);
936 
937 		miter->page = NULL;
938 		miter->addr = NULL;
939 		miter->length = 0;
940 		miter->consumed = 0;
941 	}
942 }
943 EXPORT_SYMBOL(sg_miter_stop);
944 
945 /**
946  * sg_copy_buffer - Copy data between a linear buffer and an SG list
947  * @sgl:		 The SG list
948  * @nents:		 Number of SG entries
949  * @buf:		 Where to copy from
950  * @buflen:		 The number of bytes to copy
951  * @skip:		 Number of bytes to skip before copying
952  * @to_buffer:		 transfer direction (true == from an sg list to a
953  *			 buffer, false == from a buffer to an sg list)
954  *
955  * Returns the number of copied bytes.
956  *
957  **/
sg_copy_buffer(struct scatterlist * sgl,unsigned int nents,void * buf,size_t buflen,off_t skip,bool to_buffer)958 size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
959 		      size_t buflen, off_t skip, bool to_buffer)
960 {
961 	unsigned int offset = 0;
962 	struct sg_mapping_iter miter;
963 	unsigned int sg_flags = SG_MITER_ATOMIC;
964 
965 	if (to_buffer)
966 		sg_flags |= SG_MITER_FROM_SG;
967 	else
968 		sg_flags |= SG_MITER_TO_SG;
969 
970 	sg_miter_start(&miter, sgl, nents, sg_flags);
971 
972 	if (!sg_miter_skip(&miter, skip))
973 		return 0;
974 
975 	while ((offset < buflen) && sg_miter_next(&miter)) {
976 		unsigned int len;
977 
978 		len = min(miter.length, buflen - offset);
979 
980 		if (to_buffer)
981 			memcpy(buf + offset, miter.addr, len);
982 		else
983 			memcpy(miter.addr, buf + offset, len);
984 
985 		offset += len;
986 	}
987 
988 	sg_miter_stop(&miter);
989 
990 	return offset;
991 }
992 EXPORT_SYMBOL(sg_copy_buffer);
993 
994 /**
995  * sg_copy_from_buffer - Copy from a linear buffer to an SG list
996  * @sgl:		 The SG list
997  * @nents:		 Number of SG entries
998  * @buf:		 Where to copy from
999  * @buflen:		 The number of bytes to copy
1000  *
1001  * Returns the number of copied bytes.
1002  *
1003  **/
sg_copy_from_buffer(struct scatterlist * sgl,unsigned int nents,const void * buf,size_t buflen)1004 size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
1005 			   const void *buf, size_t buflen)
1006 {
1007 	return sg_copy_buffer(sgl, nents, (void *)buf, buflen, 0, false);
1008 }
1009 EXPORT_SYMBOL(sg_copy_from_buffer);
1010 
1011 /**
1012  * sg_copy_to_buffer - Copy from an SG list to a linear buffer
1013  * @sgl:		 The SG list
1014  * @nents:		 Number of SG entries
1015  * @buf:		 Where to copy to
1016  * @buflen:		 The number of bytes to copy
1017  *
1018  * Returns the number of copied bytes.
1019  *
1020  **/
sg_copy_to_buffer(struct scatterlist * sgl,unsigned int nents,void * buf,size_t buflen)1021 size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
1022 			 void *buf, size_t buflen)
1023 {
1024 	return sg_copy_buffer(sgl, nents, buf, buflen, 0, true);
1025 }
1026 EXPORT_SYMBOL(sg_copy_to_buffer);
1027 
1028 /**
1029  * sg_pcopy_from_buffer - Copy from a linear buffer to an SG list
1030  * @sgl:		 The SG list
1031  * @nents:		 Number of SG entries
1032  * @buf:		 Where to copy from
1033  * @buflen:		 The number of bytes to copy
1034  * @skip:		 Number of bytes to skip before copying
1035  *
1036  * Returns the number of copied bytes.
1037  *
1038  **/
sg_pcopy_from_buffer(struct scatterlist * sgl,unsigned int nents,const void * buf,size_t buflen,off_t skip)1039 size_t sg_pcopy_from_buffer(struct scatterlist *sgl, unsigned int nents,
1040 			    const void *buf, size_t buflen, off_t skip)
1041 {
1042 	return sg_copy_buffer(sgl, nents, (void *)buf, buflen, skip, false);
1043 }
1044 EXPORT_SYMBOL(sg_pcopy_from_buffer);
1045 
1046 /**
1047  * sg_pcopy_to_buffer - Copy from an SG list to a linear buffer
1048  * @sgl:		 The SG list
1049  * @nents:		 Number of SG entries
1050  * @buf:		 Where to copy to
1051  * @buflen:		 The number of bytes to copy
1052  * @skip:		 Number of bytes to skip before copying
1053  *
1054  * Returns the number of copied bytes.
1055  *
1056  **/
sg_pcopy_to_buffer(struct scatterlist * sgl,unsigned int nents,void * buf,size_t buflen,off_t skip)1057 size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
1058 			  void *buf, size_t buflen, off_t skip)
1059 {
1060 	return sg_copy_buffer(sgl, nents, buf, buflen, skip, true);
1061 }
1062 EXPORT_SYMBOL(sg_pcopy_to_buffer);
1063 
1064 /**
1065  * sg_zero_buffer - Zero-out a part of a SG list
1066  * @sgl:		 The SG list
1067  * @nents:		 Number of SG entries
1068  * @buflen:		 The number of bytes to zero out
1069  * @skip:		 Number of bytes to skip before zeroing
1070  *
1071  * Returns the number of bytes zeroed.
1072  **/
sg_zero_buffer(struct scatterlist * sgl,unsigned int nents,size_t buflen,off_t skip)1073 size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
1074 		       size_t buflen, off_t skip)
1075 {
1076 	unsigned int offset = 0;
1077 	struct sg_mapping_iter miter;
1078 	unsigned int sg_flags = SG_MITER_ATOMIC | SG_MITER_TO_SG;
1079 
1080 	sg_miter_start(&miter, sgl, nents, sg_flags);
1081 
1082 	if (!sg_miter_skip(&miter, skip))
1083 		return false;
1084 
1085 	while (offset < buflen && sg_miter_next(&miter)) {
1086 		unsigned int len;
1087 
1088 		len = min(miter.length, buflen - offset);
1089 		memset(miter.addr, 0, len);
1090 
1091 		offset += len;
1092 	}
1093 
1094 	sg_miter_stop(&miter);
1095 	return offset;
1096 }
1097 EXPORT_SYMBOL(sg_zero_buffer);
1098