2 * SPDX-License-Identifier: BSD-3-Clause
4 * Copyright (c) 2008 Yahoo!, Inc.
6 * Written by: John Baldwin <jhb@FreeBSD.org>
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the author nor the names of any co-contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
33 #include <sys/cdefs.h>
34 __FBSDID("$FreeBSD$");
36 #include <sys/param.h>
37 #include <sys/kernel.h>
39 #include <sys/malloc.h>
42 #include <sys/sglist.h>
46 #include <vm/vm_page.h>
48 #include <vm/vm_map.h>
52 static MALLOC_DEFINE(M_SGLIST, "sglist", "scatter/gather lists");
55 * Convenience macros to save the state of an sglist so it can be restored
56 * if an append attempt fails. Since sglist's only grow we only need to
57 * save the current count of segments and the length of the ending segment.
58 * Earlier segments will not be changed by an append, and the only change
59 * that can occur to the ending segment is that it can be extended.
66 #define SGLIST_SAVE(sg, sgsave) do { \
67 (sgsave).sg_nseg = (sg)->sg_nseg; \
68 if ((sgsave).sg_nseg > 0) \
69 (sgsave).ss_len = (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len; \
71 (sgsave).ss_len = 0; \
74 #define SGLIST_RESTORE(sg, sgsave) do { \
75 (sg)->sg_nseg = (sgsave).sg_nseg; \
76 if ((sgsave).sg_nseg > 0) \
77 (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len = (sgsave).ss_len; \
81 * Append a single (paddr, len) to a sglist. sg is the list and ss is
82 * the current segment in the list. If we run out of segments then
83 * EFBIG will be returned.
86 _sglist_append_range(struct sglist *sg, struct sglist_seg **ssp,
87 vm_paddr_t paddr, size_t len)
89 struct sglist_seg *ss;
92 if (ss->ss_paddr + ss->ss_len == paddr)
95 if (sg->sg_nseg == sg->sg_maxseg)
107 * Worker routine to append a virtual address range (either kernel or
108 * user) to a scatter/gather list.
111 _sglist_append_buf(struct sglist *sg, void *buf, size_t len, pmap_t pmap,
114 struct sglist_seg *ss;
115 vm_offset_t vaddr, offset;
125 /* Do the first page. It may have an offset. */
126 vaddr = (vm_offset_t)buf;
127 offset = vaddr & PAGE_MASK;
129 paddr = pmap_extract(pmap, vaddr);
131 paddr = pmap_kextract(vaddr);
132 seglen = MIN(len, PAGE_SIZE - offset);
133 if (sg->sg_nseg == 0) {
135 ss->ss_paddr = paddr;
139 ss = &sg->sg_segs[sg->sg_nseg - 1];
140 error = _sglist_append_range(sg, &ss, paddr, seglen);
150 seglen = MIN(len, PAGE_SIZE);
152 paddr = pmap_extract(pmap, vaddr);
154 paddr = pmap_kextract(vaddr);
155 error = _sglist_append_range(sg, &ss, paddr, seglen);
168 * Determine the number of scatter/gather list elements needed to
169 * describe a kernel virtual address range.
172 sglist_count(void *buf, size_t len)
174 vm_offset_t vaddr, vendaddr;
175 vm_paddr_t lastaddr, paddr;
181 vaddr = trunc_page((vm_offset_t)buf);
182 vendaddr = (vm_offset_t)buf + len;
184 lastaddr = pmap_kextract(vaddr);
186 while (vaddr < vendaddr) {
187 paddr = pmap_kextract(vaddr);
188 if (lastaddr + PAGE_SIZE != paddr)
197 * Determine the number of scatter/gather list elements needed to
198 * describe a buffer backed by an array of VM pages.
201 sglist_count_vmpages(vm_page_t *m, size_t pgoff, size_t len)
203 vm_paddr_t lastaddr, paddr;
211 lastaddr = VM_PAGE_TO_PHYS(m[0]);
212 for (i = 1; len > PAGE_SIZE; len -= PAGE_SIZE, i++) {
213 paddr = VM_PAGE_TO_PHYS(m[i]);
214 if (lastaddr + PAGE_SIZE != paddr)
222 * Determine the number of scatter/gather list elements needed to
223 * describe an EXT_PGS buffer.
226 sglist_count_ext_pgs(struct mbuf_ext_pgs *ext_pgs, size_t off, size_t len)
228 vm_paddr_t nextaddr, paddr;
229 size_t seglen, segoff;
230 int i, nsegs, pglen, pgoff;
236 if (ext_pgs->hdr_len != 0) {
237 if (off >= ext_pgs->hdr_len) {
238 off -= ext_pgs->hdr_len;
240 seglen = ext_pgs->hdr_len - off;
242 seglen = MIN(seglen, len);
245 nsegs += sglist_count(&ext_pgs->hdr[segoff], seglen);
249 pgoff = ext_pgs->first_pg_off;
250 for (i = 0; i < ext_pgs->npgs && len > 0; i++) {
251 pglen = mbuf_ext_pg_len(ext_pgs, i, pgoff);
257 seglen = pglen - off;
258 segoff = pgoff + off;
260 seglen = MIN(seglen, len);
262 paddr = ext_pgs->pa[i] + segoff;
263 if (paddr != nextaddr)
265 nextaddr = paddr + seglen;
269 seglen = MIN(len, ext_pgs->trail_len - off);
271 nsegs += sglist_count(&ext_pgs->trail[off], seglen);
273 KASSERT(len == 0, ("len != 0"));
278 * Determine the number of scatter/gather list elements needed to
279 * describe an EXT_PGS mbuf.
282 sglist_count_mb_ext_pgs(struct mbuf *m)
285 MBUF_EXT_PGS_ASSERT(m);
286 return (sglist_count_ext_pgs(m->m_ext.ext_pgs, mtod(m, vm_offset_t),
291 * Allocate a scatter/gather list along with 'nsegs' segments. The
292 * 'mflags' parameters are the same as passed to malloc(9). The caller
293 * should use sglist_free() to free this list.
296 sglist_alloc(int nsegs, int mflags)
300 sg = malloc(sizeof(struct sglist) + nsegs * sizeof(struct sglist_seg),
304 sglist_init(sg, nsegs, (struct sglist_seg *)(sg + 1));
309 * Free a scatter/gather list allocated via sglist_allc().
312 sglist_free(struct sglist *sg)
318 if (refcount_release(&sg->sg_refs))
323 * Append the segments to describe a single kernel virtual address
324 * range to a scatter/gather list. If there are insufficient
325 * segments, then this fails with EFBIG.
328 sglist_append(struct sglist *sg, void *buf, size_t len)
333 if (sg->sg_maxseg == 0)
335 SGLIST_SAVE(sg, save);
336 error = _sglist_append_buf(sg, buf, len, NULL, NULL);
338 SGLIST_RESTORE(sg, save);
343 * Append the segments to describe a bio's data to a scatter/gather list.
344 * If there are insufficient segments, then this fails with EFBIG.
346 * NOTE: This function expects bio_bcount to be initialized.
349 sglist_append_bio(struct sglist *sg, struct bio *bp)
353 if ((bp->bio_flags & BIO_UNMAPPED) == 0)
354 error = sglist_append(sg, bp->bio_data, bp->bio_bcount);
356 error = sglist_append_vmpages(sg, bp->bio_ma,
357 bp->bio_ma_offset, bp->bio_bcount);
362 * Append a single physical address range to a scatter/gather list.
363 * If there are insufficient segments, then this fails with EFBIG.
366 sglist_append_phys(struct sglist *sg, vm_paddr_t paddr, size_t len)
368 struct sglist_seg *ss;
372 if (sg->sg_maxseg == 0)
377 if (sg->sg_nseg == 0) {
378 sg->sg_segs[0].ss_paddr = paddr;
379 sg->sg_segs[0].ss_len = len;
383 ss = &sg->sg_segs[sg->sg_nseg - 1];
384 SGLIST_SAVE(sg, save);
385 error = _sglist_append_range(sg, &ss, paddr, len);
387 SGLIST_RESTORE(sg, save);
392 * Append the segments to describe an EXT_PGS buffer to a
393 * scatter/gather list. If there are insufficient segments, then this
397 sglist_append_ext_pgs(struct sglist *sg, struct mbuf_ext_pgs *ext_pgs,
398 size_t off, size_t len)
400 size_t seglen, segoff;
402 int error, i, pglen, pgoff;
405 if (ext_pgs->hdr_len != 0) {
406 if (off >= ext_pgs->hdr_len) {
407 off -= ext_pgs->hdr_len;
409 seglen = ext_pgs->hdr_len - off;
411 seglen = MIN(seglen, len);
414 error = sglist_append(sg,
415 &ext_pgs->hdr[segoff], seglen);
418 pgoff = ext_pgs->first_pg_off;
419 for (i = 0; i < ext_pgs->npgs && error == 0 && len > 0; i++) {
420 pglen = mbuf_ext_pg_len(ext_pgs, i, pgoff);
426 seglen = pglen - off;
427 segoff = pgoff + off;
429 seglen = MIN(seglen, len);
431 paddr = ext_pgs->pa[i] + segoff;
432 error = sglist_append_phys(sg, paddr, seglen);
435 if (error == 0 && len > 0) {
436 seglen = MIN(len, ext_pgs->trail_len - off);
438 error = sglist_append(sg,
439 &ext_pgs->trail[off], seglen);
442 KASSERT(len == 0, ("len != 0"));
447 * Append the segments to describe an EXT_PGS mbuf to a scatter/gather
448 * list. If there are insufficient segments, then this fails with
452 sglist_append_mb_ext_pgs(struct sglist *sg, struct mbuf *m)
455 /* for now, all unmapped mbufs are assumed to be EXT_PGS */
456 MBUF_EXT_PGS_ASSERT(m);
457 return (sglist_append_ext_pgs(sg, m->m_ext.ext_pgs,
458 mtod(m, vm_offset_t), m->m_len));
462 * Append the segments that describe a single mbuf chain to a
463 * scatter/gather list. If there are insufficient segments, then this
467 sglist_append_mbuf(struct sglist *sg, struct mbuf *m0)
473 if (sg->sg_maxseg == 0)
477 SGLIST_SAVE(sg, save);
478 for (m = m0; m != NULL; m = m->m_next) {
480 if ((m->m_flags & M_NOMAP) != 0)
481 error = sglist_append_mb_ext_pgs(sg, m);
483 error = sglist_append(sg, m->m_data,
486 SGLIST_RESTORE(sg, save);
495 * Append the segments that describe a buffer spanning an array of VM
496 * pages. The buffer begins at an offset of 'pgoff' in the first
500 sglist_append_vmpages(struct sglist *sg, vm_page_t *m, size_t pgoff,
504 struct sglist_seg *ss;
509 if (sg->sg_maxseg == 0)
514 SGLIST_SAVE(sg, save);
516 if (sg->sg_nseg == 0) {
517 seglen = min(PAGE_SIZE - pgoff, len);
518 sg->sg_segs[0].ss_paddr = VM_PAGE_TO_PHYS(m[0]) + pgoff;
519 sg->sg_segs[0].ss_len = seglen;
525 ss = &sg->sg_segs[sg->sg_nseg - 1];
526 for (; len > 0; i++, len -= seglen) {
527 seglen = min(PAGE_SIZE - pgoff, len);
528 paddr = VM_PAGE_TO_PHYS(m[i]) + pgoff;
529 error = _sglist_append_range(sg, &ss, paddr, seglen);
531 SGLIST_RESTORE(sg, save);
540 * Append the segments that describe a single user address range to a
541 * scatter/gather list. If there are insufficient segments, then this
545 sglist_append_user(struct sglist *sg, void *buf, size_t len, struct thread *td)
550 if (sg->sg_maxseg == 0)
552 SGLIST_SAVE(sg, save);
553 error = _sglist_append_buf(sg, buf, len,
554 vmspace_pmap(td->td_proc->p_vmspace), NULL);
556 SGLIST_RESTORE(sg, save);
561 * Append a subset of an existing scatter/gather list 'source' to a
562 * the scatter/gather list 'sg'. If there are insufficient segments,
563 * then this fails with EFBIG.
566 sglist_append_sglist(struct sglist *sg, struct sglist *source, size_t offset,
570 struct sglist_seg *ss;
574 if (sg->sg_maxseg == 0 || length == 0)
576 SGLIST_SAVE(sg, save);
578 ss = &sg->sg_segs[sg->sg_nseg - 1];
579 for (i = 0; i < source->sg_nseg; i++) {
580 if (offset >= source->sg_segs[i].ss_len) {
581 offset -= source->sg_segs[i].ss_len;
584 seglen = source->sg_segs[i].ss_len - offset;
587 error = _sglist_append_range(sg, &ss,
588 source->sg_segs[i].ss_paddr + offset, seglen);
599 SGLIST_RESTORE(sg, save);
604 * Append the segments that describe a single uio to a scatter/gather
605 * list. If there are insufficient segments, then this fails with
609 sglist_append_uio(struct sglist *sg, struct uio *uio)
613 size_t resid, minlen;
617 if (sg->sg_maxseg == 0)
620 resid = uio->uio_resid;
623 if (uio->uio_segflg == UIO_USERSPACE) {
624 KASSERT(uio->uio_td != NULL,
625 ("sglist_append_uio: USERSPACE but no thread"));
626 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
631 SGLIST_SAVE(sg, save);
632 for (i = 0; i < uio->uio_iovcnt && resid != 0; i++) {
634 * Now at the first iovec to load. Load each iovec
635 * until we have exhausted the residual count.
637 minlen = MIN(resid, iov[i].iov_len);
639 error = _sglist_append_buf(sg, iov[i].iov_base, minlen,
642 SGLIST_RESTORE(sg, save);
652 * Append the segments that describe at most 'resid' bytes from a
653 * single uio to a scatter/gather list. If there are insufficient
654 * segments, then only the amount that fits is appended.
657 sglist_consume_uio(struct sglist *sg, struct uio *uio, size_t resid)
664 if (sg->sg_maxseg == 0)
667 if (uio->uio_segflg == UIO_USERSPACE) {
668 KASSERT(uio->uio_td != NULL,
669 ("sglist_consume_uio: USERSPACE but no thread"));
670 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
675 while (resid > 0 && uio->uio_resid) {
687 * Try to append this iovec. If we run out of room,
688 * then break out of the loop.
690 error = _sglist_append_buf(sg, iov->iov_base, len, pmap, &done);
691 iov->iov_base = (char *)iov->iov_base + done;
692 iov->iov_len -= done;
693 uio->uio_resid -= done;
694 uio->uio_offset += done;
703 * Allocate and populate a scatter/gather list to describe a single
704 * kernel virtual address range.
707 sglist_build(void *buf, size_t len, int mflags)
715 nsegs = sglist_count(buf, len);
716 sg = sglist_alloc(nsegs, mflags);
719 if (sglist_append(sg, buf, len) != 0) {
727 * Clone a new copy of a scatter/gather list.
730 sglist_clone(struct sglist *sg, int mflags)
736 new = sglist_alloc(sg->sg_maxseg, mflags);
739 new->sg_nseg = sg->sg_nseg;
740 bcopy(sg->sg_segs, new->sg_segs, sizeof(struct sglist_seg) *
746 * Calculate the total length of the segments described in a
747 * scatter/gather list.
750 sglist_length(struct sglist *sg)
756 for (i = 0; i < sg->sg_nseg; i++)
757 space += sg->sg_segs[i].ss_len;
762 * Split a scatter/gather list into two lists. The scatter/gather
763 * entries for the first 'length' bytes of the 'original' list are
764 * stored in the '*head' list and are removed from 'original'.
766 * If '*head' is NULL, then a new list will be allocated using
767 * 'mflags'. If M_NOWAIT is specified and the allocation fails,
768 * ENOMEM will be returned.
770 * If '*head' is not NULL, it should point to an empty sglist. If it
771 * does not have enough room for the remaining space, then EFBIG will
772 * be returned. If '*head' is not empty, then EINVAL will be
775 * If 'original' is shared (refcount > 1), then EDOOFUS will be
779 sglist_split(struct sglist *original, struct sglist **head, size_t length,
786 if (original->sg_refs > 1)
789 /* Figure out how big of a sglist '*head' has to hold. */
793 for (i = 0; i < original->sg_nseg; i++) {
794 space += original->sg_segs[i].ss_len;
796 if (space >= length) {
798 * If 'length' falls in the middle of a
799 * scatter/gather list entry, then 'split'
800 * holds how much of that entry will remain in
803 split = space - length;
808 /* Nothing to do, so leave head empty. */
813 sg = sglist_alloc(count, mflags);
819 if (sg->sg_maxseg < count)
821 if (sg->sg_nseg != 0)
825 /* Copy 'count' entries to 'sg' from 'original'. */
826 bcopy(original->sg_segs, sg->sg_segs, count *
827 sizeof(struct sglist_seg));
831 * If we had to split a list entry, fixup the last entry in
832 * 'sg' and the new first entry in 'original'. We also
833 * decrement 'count' by 1 since we will only be removing
834 * 'count - 1' segments from 'original' now.
838 sg->sg_segs[count].ss_len -= split;
839 original->sg_segs[count].ss_paddr =
840 sg->sg_segs[count].ss_paddr + split;
841 original->sg_segs[count].ss_len = split;
844 /* Trim 'count' entries from the front of 'original'. */
845 original->sg_nseg -= count;
846 bcopy(original->sg_segs + count, original->sg_segs, count *
847 sizeof(struct sglist_seg));
852 * Append the scatter/gather list elements in 'second' to the
853 * scatter/gather list 'first'. If there is not enough space in
854 * 'first', EFBIG is returned.
857 sglist_join(struct sglist *first, struct sglist *second)
859 struct sglist_seg *flast, *sfirst;
862 /* If 'second' is empty, there is nothing to do. */
863 if (second->sg_nseg == 0)
867 * If the first entry in 'second' can be appended to the last entry
868 * in 'first' then set append to '1'.
871 flast = &first->sg_segs[first->sg_nseg - 1];
872 sfirst = &second->sg_segs[0];
873 if (first->sg_nseg != 0 &&
874 flast->ss_paddr + flast->ss_len == sfirst->ss_paddr)
877 /* Make sure 'first' has enough room. */
878 if (first->sg_nseg + second->sg_nseg - append > first->sg_maxseg)
881 /* Merge last in 'first' and first in 'second' if needed. */
883 flast->ss_len += sfirst->ss_len;
885 /* Append new segments from 'second' to 'first'. */
886 bcopy(first->sg_segs + first->sg_nseg, second->sg_segs + append,
887 (second->sg_nseg - append) * sizeof(struct sglist_seg));
888 first->sg_nseg += second->sg_nseg - append;
889 sglist_reset(second);
894 * Generate a new scatter/gather list from a range of an existing
895 * scatter/gather list. The 'offset' and 'length' parameters specify
896 * the logical range of the 'original' list to extract. If that range
897 * is not a subset of the length of 'original', then EINVAL is
898 * returned. The new scatter/gather list is stored in '*slice'.
900 * If '*slice' is NULL, then a new list will be allocated using
901 * 'mflags'. If M_NOWAIT is specified and the allocation fails,
902 * ENOMEM will be returned.
904 * If '*slice' is not NULL, it should point to an empty sglist. If it
905 * does not have enough room for the remaining space, then EFBIG will
906 * be returned. If '*slice' is not empty, then EINVAL will be
910 sglist_slice(struct sglist *original, struct sglist **slice, size_t offset,
911 size_t length, int mflags)
914 size_t space, end, foffs, loffs;
921 /* Figure out how many segments '*slice' needs to have. */
922 end = offset + length;
927 for (i = 0; i < original->sg_nseg; i++) {
928 space += original->sg_segs[i].ss_len;
929 if (space > offset) {
931 * When we hit the first segment, store its index
932 * in 'fseg' and the offset into the first segment
933 * of 'offset' in 'foffs'.
937 foffs = offset - (space -
938 original->sg_segs[i].ss_len);
939 CTR1(KTR_DEV, "sglist_slice: foffs = %08lx",
945 * When we hit the last segment, break out of
946 * the loop. Store the amount of extra space
947 * at the end of this segment in 'loffs'.
951 CTR1(KTR_DEV, "sglist_slice: loffs = %08lx",
958 /* If we never hit 'end', then 'length' ran off the end, so fail. */
962 if (*slice == NULL) {
963 sg = sglist_alloc(count, mflags);
969 if (sg->sg_maxseg < count)
971 if (sg->sg_nseg != 0)
976 * Copy over 'count' segments from 'original' starting at
979 bcopy(original->sg_segs + fseg, sg->sg_segs,
980 count * sizeof(struct sglist_seg));
983 /* Fixup first and last segments if needed. */
985 sg->sg_segs[0].ss_paddr += foffs;
986 sg->sg_segs[0].ss_len -= foffs;
987 CTR2(KTR_DEV, "sglist_slice seg[0]: %08lx:%08lx",
988 (long)sg->sg_segs[0].ss_paddr, sg->sg_segs[0].ss_len);
991 sg->sg_segs[count - 1].ss_len -= loffs;
992 CTR2(KTR_DEV, "sglist_slice seg[%d]: len %08x", count - 1,
993 sg->sg_segs[count - 1].ss_len);