1
2
3
4
5
6
7
8
9#include <linux/export.h>
10#include <linux/slab.h>
11#include <linux/scatterlist.h>
12#include <linux/highmem.h>
13#include <linux/kmemleak.h>
14
15
16
17
18
19
20
21
22
23
24
25struct scatterlist *sg_next(struct scatterlist *sg)
26{
27#ifdef CONFIG_DEBUG_SG
28 BUG_ON(sg->sg_magic != SG_MAGIC);
29#endif
30 if (sg_is_last(sg))
31 return NULL;
32
33 sg++;
34 if (unlikely(sg_is_chain(sg)))
35 sg = sg_chain_ptr(sg);
36
37 return sg;
38}
39EXPORT_SYMBOL(sg_next);
40
41
42
43
44
45
46
47
48
49
50int sg_nents(struct scatterlist *sg)
51{
52 int nents;
53 for (nents = 0; sg; sg = sg_next(sg))
54 nents++;
55 return nents;
56}
57EXPORT_SYMBOL(sg_nents);
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73int sg_nents_for_len(struct scatterlist *sg, u64 len)
74{
75 int nents;
76 u64 total;
77
78 if (!len)
79 return 0;
80
81 for (nents = 0, total = 0; sg; sg = sg_next(sg)) {
82 nents++;
83 total += sg->length;
84 if (total >= len)
85 return nents;
86 }
87
88 return -EINVAL;
89}
90EXPORT_SYMBOL(sg_nents_for_len);
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106struct scatterlist *sg_last(struct scatterlist *sgl, unsigned int nents)
107{
108 struct scatterlist *sg, *ret = NULL;
109 unsigned int i;
110
111 for_each_sg(sgl, sg, nents, i)
112 ret = sg;
113
114#ifdef CONFIG_DEBUG_SG
115 BUG_ON(sgl[0].sg_magic != SG_MAGIC);
116 BUG_ON(!sg_is_last(ret));
117#endif
118 return ret;
119}
120EXPORT_SYMBOL(sg_last);
121
122
123
124
125
126
127
128
129
130
131
132void sg_init_table(struct scatterlist *sgl, unsigned int nents)
133{
134 memset(sgl, 0, sizeof(*sgl) * nents);
135 sg_init_marker(sgl, nents);
136}
137EXPORT_SYMBOL(sg_init_table);
138
139
140
141
142
143
144
145
146void sg_init_one(struct scatterlist *sg, const void *buf, unsigned int buflen)
147{
148 sg_init_table(sg, 1);
149 sg_set_buf(sg, buf, buflen);
150}
151EXPORT_SYMBOL(sg_init_one);
152
153
154
155
156
157static struct scatterlist *sg_kmalloc(unsigned int nents, gfp_t gfp_mask)
158{
159 if (nents == SG_MAX_SINGLE_ALLOC) {
160
161
162
163
164
165
166
167
168
169 void *ptr = (void *) __get_free_page(gfp_mask);
170 kmemleak_alloc(ptr, PAGE_SIZE, 1, gfp_mask);
171 return ptr;
172 } else
173 return kmalloc(nents * sizeof(struct scatterlist), gfp_mask);
174}
175
176static void sg_kfree(struct scatterlist *sg, unsigned int nents)
177{
178 if (nents == SG_MAX_SINGLE_ALLOC) {
179 kmemleak_free(sg);
180 free_page((unsigned long) sg);
181 } else
182 kfree(sg);
183}
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198void __sg_free_table(struct sg_table *table, unsigned int max_ents,
199 bool skip_first_chunk, sg_free_fn *free_fn)
200{
201 struct scatterlist *sgl, *next;
202
203 if (unlikely(!table->sgl))
204 return;
205
206 sgl = table->sgl;
207 while (table->orig_nents) {
208 unsigned int alloc_size = table->orig_nents;
209 unsigned int sg_size;
210
211
212
213
214
215
216
217 if (alloc_size > max_ents) {
218 next = sg_chain_ptr(&sgl[max_ents - 1]);
219 alloc_size = max_ents;
220 sg_size = alloc_size - 1;
221 } else {
222 sg_size = alloc_size;
223 next = NULL;
224 }
225
226 table->orig_nents -= sg_size;
227 if (skip_first_chunk)
228 skip_first_chunk = false;
229 else
230 free_fn(sgl, alloc_size);
231 sgl = next;
232 }
233
234 table->sgl = NULL;
235}
236EXPORT_SYMBOL(__sg_free_table);
237
238
239
240
241
242
243void sg_free_table(struct sg_table *table)
244{
245 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, false, sg_kfree);
246}
247EXPORT_SYMBOL(sg_free_table);
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268int __sg_alloc_table(struct sg_table *table, unsigned int nents,
269 unsigned int max_ents, struct scatterlist *first_chunk,
270 gfp_t gfp_mask, sg_alloc_fn *alloc_fn)
271{
272 struct scatterlist *sg, *prv;
273 unsigned int left;
274
275 memset(table, 0, sizeof(*table));
276
277 if (nents == 0)
278 return -EINVAL;
279#ifndef CONFIG_ARCH_HAS_SG_CHAIN
280 if (WARN_ON_ONCE(nents > max_ents))
281 return -EINVAL;
282#endif
283
284 left = nents;
285 prv = NULL;
286 do {
287 unsigned int sg_size, alloc_size = left;
288
289 if (alloc_size > max_ents) {
290 alloc_size = max_ents;
291 sg_size = alloc_size - 1;
292 } else
293 sg_size = alloc_size;
294
295 left -= sg_size;
296
297 if (first_chunk) {
298 sg = first_chunk;
299 first_chunk = NULL;
300 } else {
301 sg = alloc_fn(alloc_size, gfp_mask);
302 }
303 if (unlikely(!sg)) {
304
305
306
307
308
309
310 if (prv)
311 table->nents = ++table->orig_nents;
312
313 return -ENOMEM;
314 }
315
316 sg_init_table(sg, alloc_size);
317 table->nents = table->orig_nents += sg_size;
318
319
320
321
322
323 if (prv)
324 sg_chain(prv, max_ents, sg);
325 else
326 table->sgl = sg;
327
328
329
330
331 if (!left)
332 sg_mark_end(&sg[sg_size - 1]);
333
334 prv = sg;
335 } while (left);
336
337 return 0;
338}
339EXPORT_SYMBOL(__sg_alloc_table);
340
341
342
343
344
345
346
347
348
349
350
351
352int sg_alloc_table(struct sg_table *table, unsigned int nents, gfp_t gfp_mask)
353{
354 int ret;
355
356 ret = __sg_alloc_table(table, nents, SG_MAX_SINGLE_ALLOC,
357 NULL, gfp_mask, sg_kmalloc);
358 if (unlikely(ret))
359 __sg_free_table(table, SG_MAX_SINGLE_ALLOC, false, sg_kfree);
360
361 return ret;
362}
363EXPORT_SYMBOL(sg_alloc_table);
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386int __sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
387 unsigned int n_pages, unsigned int offset,
388 unsigned long size, unsigned int max_segment,
389 gfp_t gfp_mask)
390{
391 unsigned int chunks, cur_page, seg_len, i;
392 int ret;
393 struct scatterlist *s;
394
395 if (WARN_ON(!max_segment || offset_in_page(max_segment)))
396 return -EINVAL;
397
398
399 chunks = 1;
400 seg_len = 0;
401 for (i = 1; i < n_pages; i++) {
402 seg_len += PAGE_SIZE;
403 if (seg_len >= max_segment ||
404 page_to_pfn(pages[i]) != page_to_pfn(pages[i - 1]) + 1) {
405 chunks++;
406 seg_len = 0;
407 }
408 }
409
410 ret = sg_alloc_table(sgt, chunks, gfp_mask);
411 if (unlikely(ret))
412 return ret;
413
414
415 cur_page = 0;
416 for_each_sg(sgt->sgl, s, sgt->orig_nents, i) {
417 unsigned int j, chunk_size;
418
419
420 seg_len = 0;
421 for (j = cur_page + 1; j < n_pages; j++) {
422 seg_len += PAGE_SIZE;
423 if (seg_len >= max_segment ||
424 page_to_pfn(pages[j]) !=
425 page_to_pfn(pages[j - 1]) + 1)
426 break;
427 }
428
429 chunk_size = ((j - cur_page) << PAGE_SHIFT) - offset;
430 sg_set_page(s, pages[cur_page],
431 min_t(unsigned long, size, chunk_size), offset);
432 size -= chunk_size;
433 offset = 0;
434 cur_page = j;
435 }
436
437 return 0;
438}
439EXPORT_SYMBOL(__sg_alloc_table_from_pages);
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461int sg_alloc_table_from_pages(struct sg_table *sgt, struct page **pages,
462 unsigned int n_pages, unsigned int offset,
463 unsigned long size, gfp_t gfp_mask)
464{
465 return __sg_alloc_table_from_pages(sgt, pages, n_pages, offset, size,
466 SCATTERLIST_MAX_SEGMENT, gfp_mask);
467}
468EXPORT_SYMBOL(sg_alloc_table_from_pages);
469
470#ifdef CONFIG_SGL_ALLOC
471
472
473
474
475
476
477
478
479
480
481
482
483struct scatterlist *sgl_alloc_order(unsigned long long length,
484 unsigned int order, bool chainable,
485 gfp_t gfp, unsigned int *nent_p)
486{
487 struct scatterlist *sgl, *sg;
488 struct page *page;
489 unsigned int nent, nalloc;
490 u32 elem_len;
491
492 nent = round_up(length, PAGE_SIZE << order) >> (PAGE_SHIFT + order);
493
494 if (length > (nent << (PAGE_SHIFT + order)))
495 return NULL;
496 nalloc = nent;
497 if (chainable) {
498
499 if (nalloc + 1 < nalloc)
500 return NULL;
501 nalloc++;
502 }
503 sgl = kmalloc_array(nalloc, sizeof(struct scatterlist),
504 (gfp & ~GFP_DMA) | __GFP_ZERO);
505 if (!sgl)
506 return NULL;
507
508 sg_init_table(sgl, nalloc);
509 sg = sgl;
510 while (length) {
511 elem_len = min_t(u64, length, PAGE_SIZE << order);
512 page = alloc_pages(gfp, order);
513 if (!page) {
514 sgl_free(sgl);
515 return NULL;
516 }
517
518 sg_set_page(sg, page, elem_len, 0);
519 length -= elem_len;
520 sg = sg_next(sg);
521 }
522 WARN_ONCE(length, "length = %lld\n", length);
523 if (nent_p)
524 *nent_p = nent;
525 return sgl;
526}
527EXPORT_SYMBOL(sgl_alloc_order);
528
529
530
531
532
533
534
535
536
537struct scatterlist *sgl_alloc(unsigned long long length, gfp_t gfp,
538 unsigned int *nent_p)
539{
540 return sgl_alloc_order(length, 0, false, gfp, nent_p);
541}
542EXPORT_SYMBOL(sgl_alloc);
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557void sgl_free_n_order(struct scatterlist *sgl, int nents, int order)
558{
559 struct scatterlist *sg;
560 struct page *page;
561 int i;
562
563 for_each_sg(sgl, sg, nents, i) {
564 if (!sg)
565 break;
566 page = sg_page(sg);
567 if (page)
568 __free_pages(page, order);
569 }
570 kfree(sgl);
571}
572EXPORT_SYMBOL(sgl_free_n_order);
573
574
575
576
577
578
579void sgl_free_order(struct scatterlist *sgl, int order)
580{
581 sgl_free_n_order(sgl, INT_MAX, order);
582}
583EXPORT_SYMBOL(sgl_free_order);
584
585
586
587
588
589void sgl_free(struct scatterlist *sgl)
590{
591 sgl_free_order(sgl, 0);
592}
593EXPORT_SYMBOL(sgl_free);
594
595#endif
596
597void __sg_page_iter_start(struct sg_page_iter *piter,
598 struct scatterlist *sglist, unsigned int nents,
599 unsigned long pgoffset)
600{
601 piter->__pg_advance = 0;
602 piter->__nents = nents;
603
604 piter->sg = sglist;
605 piter->sg_pgoffset = pgoffset;
606}
607EXPORT_SYMBOL(__sg_page_iter_start);
608
609static int sg_page_count(struct scatterlist *sg)
610{
611 return PAGE_ALIGN(sg->offset + sg->length) >> PAGE_SHIFT;
612}
613
614bool __sg_page_iter_next(struct sg_page_iter *piter)
615{
616 if (!piter->__nents || !piter->sg)
617 return false;
618
619 piter->sg_pgoffset += piter->__pg_advance;
620 piter->__pg_advance = 1;
621
622 while (piter->sg_pgoffset >= sg_page_count(piter->sg)) {
623 piter->sg_pgoffset -= sg_page_count(piter->sg);
624 piter->sg = sg_next(piter->sg);
625 if (!--piter->__nents || !piter->sg)
626 return false;
627 }
628
629 return true;
630}
631EXPORT_SYMBOL(__sg_page_iter_next);
632
633
634
635
636
637
638
639
640
641
642
643
644
645void sg_miter_start(struct sg_mapping_iter *miter, struct scatterlist *sgl,
646 unsigned int nents, unsigned int flags)
647{
648 memset(miter, 0, sizeof(struct sg_mapping_iter));
649
650 __sg_page_iter_start(&miter->piter, sgl, nents, 0);
651 WARN_ON(!(flags & (SG_MITER_TO_SG | SG_MITER_FROM_SG)));
652 miter->__flags = flags;
653}
654EXPORT_SYMBOL(sg_miter_start);
655
656static bool sg_miter_get_next_page(struct sg_mapping_iter *miter)
657{
658 if (!miter->__remaining) {
659 struct scatterlist *sg;
660 unsigned long pgoffset;
661
662 if (!__sg_page_iter_next(&miter->piter))
663 return false;
664
665 sg = miter->piter.sg;
666 pgoffset = miter->piter.sg_pgoffset;
667
668 miter->__offset = pgoffset ? 0 : sg->offset;
669 miter->__remaining = sg->offset + sg->length -
670 (pgoffset << PAGE_SHIFT) - miter->__offset;
671 miter->__remaining = min_t(unsigned long, miter->__remaining,
672 PAGE_SIZE - miter->__offset);
673 }
674
675 return true;
676}
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696bool sg_miter_skip(struct sg_mapping_iter *miter, off_t offset)
697{
698 sg_miter_stop(miter);
699
700 while (offset) {
701 off_t consumed;
702
703 if (!sg_miter_get_next_page(miter))
704 return false;
705
706 consumed = min_t(off_t, offset, miter->__remaining);
707 miter->__offset += consumed;
708 miter->__remaining -= consumed;
709 offset -= consumed;
710 }
711
712 return true;
713}
714EXPORT_SYMBOL(sg_miter_skip);
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733bool sg_miter_next(struct sg_mapping_iter *miter)
734{
735 sg_miter_stop(miter);
736
737
738
739
740
741 if (!sg_miter_get_next_page(miter))
742 return false;
743
744 miter->page = sg_page_iter_page(&miter->piter);
745 miter->consumed = miter->length = miter->__remaining;
746
747 if (miter->__flags & SG_MITER_ATOMIC)
748 miter->addr = kmap_atomic(miter->page) + miter->__offset;
749 else
750 miter->addr = kmap(miter->page) + miter->__offset;
751
752 return true;
753}
754EXPORT_SYMBOL(sg_miter_next);
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770void sg_miter_stop(struct sg_mapping_iter *miter)
771{
772 WARN_ON(miter->consumed > miter->length);
773
774
775 if (miter->addr) {
776 miter->__offset += miter->consumed;
777 miter->__remaining -= miter->consumed;
778
779 if ((miter->__flags & SG_MITER_TO_SG) &&
780 !PageSlab(miter->page))
781 flush_kernel_dcache_page(miter->page);
782
783 if (miter->__flags & SG_MITER_ATOMIC) {
784 WARN_ON_ONCE(preemptible());
785 kunmap_atomic(miter->addr);
786 } else
787 kunmap(miter->page);
788
789 miter->page = NULL;
790 miter->addr = NULL;
791 miter->length = 0;
792 miter->consumed = 0;
793 }
794}
795EXPORT_SYMBOL(sg_miter_stop);
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810size_t sg_copy_buffer(struct scatterlist *sgl, unsigned int nents, void *buf,
811 size_t buflen, off_t skip, bool to_buffer)
812{
813 unsigned int offset = 0;
814 struct sg_mapping_iter miter;
815 unsigned int sg_flags = SG_MITER_ATOMIC;
816
817 if (to_buffer)
818 sg_flags |= SG_MITER_FROM_SG;
819 else
820 sg_flags |= SG_MITER_TO_SG;
821
822 sg_miter_start(&miter, sgl, nents, sg_flags);
823
824 if (!sg_miter_skip(&miter, skip))
825 return false;
826
827 while ((offset < buflen) && sg_miter_next(&miter)) {
828 unsigned int len;
829
830 len = min(miter.length, buflen - offset);
831
832 if (to_buffer)
833 memcpy(buf + offset, miter.addr, len);
834 else
835 memcpy(miter.addr, buf + offset, len);
836
837 offset += len;
838 }
839
840 sg_miter_stop(&miter);
841
842 return offset;
843}
844EXPORT_SYMBOL(sg_copy_buffer);
845
846
847
848
849
850
851
852
853
854
855
856size_t sg_copy_from_buffer(struct scatterlist *sgl, unsigned int nents,
857 const void *buf, size_t buflen)
858{
859 return sg_copy_buffer(sgl, nents, (void *)buf, buflen, 0, false);
860}
861EXPORT_SYMBOL(sg_copy_from_buffer);
862
863
864
865
866
867
868
869
870
871
872
873size_t sg_copy_to_buffer(struct scatterlist *sgl, unsigned int nents,
874 void *buf, size_t buflen)
875{
876 return sg_copy_buffer(sgl, nents, buf, buflen, 0, true);
877}
878EXPORT_SYMBOL(sg_copy_to_buffer);
879
880
881
882
883
884
885
886
887
888
889
890
891size_t sg_pcopy_from_buffer(struct scatterlist *sgl, unsigned int nents,
892 const void *buf, size_t buflen, off_t skip)
893{
894 return sg_copy_buffer(sgl, nents, (void *)buf, buflen, skip, false);
895}
896EXPORT_SYMBOL(sg_pcopy_from_buffer);
897
898
899
900
901
902
903
904
905
906
907
908
909size_t sg_pcopy_to_buffer(struct scatterlist *sgl, unsigned int nents,
910 void *buf, size_t buflen, off_t skip)
911{
912 return sg_copy_buffer(sgl, nents, buf, buflen, skip, true);
913}
914EXPORT_SYMBOL(sg_pcopy_to_buffer);
915
916
917
918
919
920
921
922
923
924
925size_t sg_zero_buffer(struct scatterlist *sgl, unsigned int nents,
926 size_t buflen, off_t skip)
927{
928 unsigned int offset = 0;
929 struct sg_mapping_iter miter;
930 unsigned int sg_flags = SG_MITER_ATOMIC | SG_MITER_TO_SG;
931
932 sg_miter_start(&miter, sgl, nents, sg_flags);
933
934 if (!sg_miter_skip(&miter, skip))
935 return false;
936
937 while (offset < buflen && sg_miter_next(&miter)) {
938 unsigned int len;
939
940 len = min(miter.length, buflen - offset);
941 memset(miter.addr, 0, len);
942
943 offset += len;
944 }
945
946 sg_miter_stop(&miter);
947 return offset;
948}
949EXPORT_SYMBOL(sg_zero_buffer);
950