2 * Copyright (c) 2008 Yahoo!, Inc.
4 * Written by: John Baldwin <jhb@FreeBSD.org>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the name of the author nor the names of any co-contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
19 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
22 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
23 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
24 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
25 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
26 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
27 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * $FreeBSD: src/sys/kern/subr_sglist.c,v 1.3 2009/08/21 02:59:07 jhb Exp $
34 #include <sys/param.h>
35 #include <sys/kernel.h>
36 #include <sys/malloc.h>
39 #include <sys/sglist.h>
44 #include <vm/vm_map.h>
48 static MALLOC_DEFINE(M_SGLIST, "sglist", "scatter/gather lists");
51 * Convenience macros to save the state of an sglist so it can be restored
52 * if an append attempt fails. Since sglist's only grow we only need to
53 * save the current count of segments and the length of the ending segment.
54 * Earlier segments will not be changed by an append, and the only change
55 * that can occur to the ending segment is that it can be extended.
62 #define SGLIST_SAVE(sg, sgsave) do { \
63 (sgsave).sg_nseg = (sg)->sg_nseg; \
64 if ((sgsave).sg_nseg > 0) \
65 (sgsave).ss_len = (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len; \
67 (sgsave).ss_len = 0; \
70 #define SGLIST_RESTORE(sg, sgsave) do { \
71 (sg)->sg_nseg = (sgsave).sg_nseg; \
72 if ((sgsave).sg_nseg > 0) \
73 (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len = (sgsave).ss_len; \
77 * Append a single (paddr, len) to a sglist. sg is the list and ss is
78 * the current segment in the list. If we run out of segments then
79 * EFBIG will be returned.
82 _sglist_append_range(struct sglist *sg, struct sglist_seg **ssp,
83 vm_paddr_t paddr, size_t len)
85 struct sglist_seg *ss;
88 if (ss->ss_paddr + ss->ss_len == paddr)
91 if (sg->sg_nseg == sg->sg_maxseg)
103 * Worker routine to append a virtual address range (either kernel or
104 * user) to a scatter/gather list.
107 _sglist_append_buf(struct sglist *sg, void *buf, size_t len, pmap_t pmap,
110 struct sglist_seg *ss;
111 vm_offset_t vaddr, offset;
122 /* Do the first page. It may have an offset. */
123 vaddr = (vm_offset_t)buf;
124 offset = vaddr & PAGE_MASK;
126 paddr = pmap_extract(pmap, vaddr, &handle);
128 paddr = pmap_kextract(vaddr);
131 seglen = MIN(len, PAGE_SIZE - offset);
132 if (sg->sg_nseg == 0) {
134 ss->ss_paddr = paddr;
138 ss = &sg->sg_segs[sg->sg_nseg - 1];
139 error = _sglist_append_range(sg, &ss, paddr, seglen);
141 pmap_extract_done(handle);
145 pmap_extract_done(handle);
152 seglen = MIN(len, PAGE_SIZE);
154 paddr = pmap_extract(pmap, vaddr, &handle);
155 error = _sglist_append_range(sg, &ss, paddr, seglen);
156 pmap_extract_done(handle);
158 paddr = pmap_kextract(vaddr);
159 error = _sglist_append_range(sg, &ss, paddr, seglen);
173 * Determine the number of scatter/gather list elements needed to
174 * describe a kernel virtual address range.
177 sglist_count(void *buf, size_t len)
179 vm_offset_t vaddr, vendaddr;
180 vm_paddr_t lastaddr, paddr;
186 vaddr = trunc_page((vm_offset_t)buf);
187 vendaddr = (vm_offset_t)buf + len;
189 lastaddr = pmap_kextract(vaddr);
191 while (vaddr < vendaddr) {
192 paddr = pmap_kextract(vaddr);
193 if (lastaddr + PAGE_SIZE != paddr)
202 * Allocate a scatter/gather list along with 'nsegs' segments. The
203 * 'mflags' parameters are the same as passed to kmalloc(9). The caller
204 * should use sglist_free() to free this list.
207 sglist_alloc(int nsegs, int mflags)
211 sg = kmalloc(sizeof(struct sglist) + nsegs * sizeof(struct sglist_seg),
215 sglist_init(sg, nsegs, (struct sglist_seg *)(sg + 1));
220 * Free a scatter/gather list allocated via sglist_allc().
223 sglist_free(struct sglist *sg)
226 if (refcount_release(&sg->sg_refs))
231 * Append the segments to describe a single kernel virtual address
232 * range to a scatter/gather list. If there are insufficient
233 * segments, then this fails with EFBIG.
236 sglist_append(struct sglist *sg, void *buf, size_t len)
241 if (sg->sg_maxseg == 0)
243 SGLIST_SAVE(sg, save);
244 error = _sglist_append_buf(sg, buf, len, NULL, NULL);
246 SGLIST_RESTORE(sg, save);
251 * Append a single physical address range to a scatter/gather list.
252 * If there are insufficient segments, then this fails with EFBIG.
255 sglist_append_phys(struct sglist *sg, vm_paddr_t paddr, size_t len)
257 struct sglist_seg *ss;
261 if (sg->sg_maxseg == 0)
266 if (sg->sg_nseg == 0) {
267 sg->sg_segs[0].ss_paddr = paddr;
268 sg->sg_segs[0].ss_len = len;
272 ss = &sg->sg_segs[sg->sg_nseg - 1];
273 SGLIST_SAVE(sg, save);
274 error = _sglist_append_range(sg, &ss, paddr, len);
276 SGLIST_RESTORE(sg, save);
281 * Append the segments that describe a single mbuf chain to a
282 * scatter/gather list. If there are insufficient segments, then this
286 sglist_append_mbuf(struct sglist *sg, struct mbuf *m0)
292 if (sg->sg_maxseg == 0)
296 SGLIST_SAVE(sg, save);
297 for (m = m0; m != NULL; m = m->m_next) {
299 error = sglist_append(sg, m->m_data, m->m_len);
301 SGLIST_RESTORE(sg, save);
310 * Append the segments that describe a single user address range to a
311 * scatter/gather list. If there are insufficient segments, then this
315 sglist_append_user(struct sglist *sg, void *buf, size_t len, struct thread *td)
320 if (sg->sg_maxseg == 0)
322 SGLIST_SAVE(sg, save);
323 error = _sglist_append_buf(sg, buf, len,
324 vmspace_pmap(td->td_proc->p_vmspace), NULL);
326 SGLIST_RESTORE(sg, save);
331 * Append the segments that describe a single uio to a scatter/gather
332 * list. If there are insufficient segments, then this fails with
336 sglist_append_uio(struct sglist *sg, struct uio *uio)
340 size_t resid, minlen;
344 if (sg->sg_maxseg == 0)
347 resid = uio->uio_resid;
350 if (uio->uio_segflg == UIO_USERSPACE) {
351 KASSERT(uio->uio_td != NULL,
352 ("sglist_append_uio: USERSPACE but no thread"));
353 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
358 SGLIST_SAVE(sg, save);
359 for (i = 0; i < uio->uio_iovcnt && resid != 0; i++) {
361 * Now at the first iovec to load. Load each iovec
362 * until we have exhausted the residual count.
364 minlen = MIN(resid, iov[i].iov_len);
366 error = _sglist_append_buf(sg, iov[i].iov_base, minlen,
369 SGLIST_RESTORE(sg, save);
379 * Append the segments that describe at most 'resid' bytes from a
380 * single uio to a scatter/gather list. If there are insufficient
381 * segments, then only the amount that fits is appended.
384 sglist_consume_uio(struct sglist *sg, struct uio *uio, size_t resid)
391 if (sg->sg_maxseg == 0)
394 if (uio->uio_segflg == UIO_USERSPACE) {
395 KASSERT(uio->uio_td != NULL,
396 ("sglist_consume_uio: USERSPACE but no thread"));
397 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
402 while (resid > 0 && uio->uio_resid) {
414 * Try to append this iovec. If we run out of room,
415 * then break out of the loop.
417 error = _sglist_append_buf(sg, iov->iov_base, len, pmap, &done);
418 iov->iov_base = (char *)iov->iov_base + done;
419 iov->iov_len -= done;
420 uio->uio_resid -= done;
421 uio->uio_offset += done;
430 * Allocate and populate a scatter/gather list to describe a single
431 * kernel virtual address range.
434 sglist_build(void *buf, size_t len, int mflags)
442 nsegs = sglist_count(buf, len);
443 sg = sglist_alloc(nsegs, mflags);
446 if (sglist_append(sg, buf, len) != 0) {
454 * Clone a new copy of a scatter/gather list.
457 sglist_clone(struct sglist *sg, int mflags)
463 new = sglist_alloc(sg->sg_maxseg, mflags);
466 new->sg_nseg = sg->sg_nseg;
467 bcopy(sg->sg_segs, new->sg_segs, sizeof(struct sglist_seg) *
473 * Calculate the total length of the segments described in a
474 * scatter/gather list.
477 sglist_length(struct sglist *sg)
483 for (i = 0; i < sg->sg_nseg; i++)
484 space += sg->sg_segs[i].ss_len;
489 * Split a scatter/gather list into two lists. The scatter/gather
490 * entries for the first 'length' bytes of the 'original' list are
491 * stored in the '*head' list and are removed from 'original'.
493 * If '*head' is NULL, then a new list will be allocated using
494 * 'mflags'. If M_NOWAIT is specified and the allocation fails,
495 * ENOMEM will be returned.
497 * If '*head' is not NULL, it should point to an empty sglist. If it
498 * does not have enough room for the remaining space, then EFBIG will
499 * be returned. If '*head' is not empty, then EINVAL will be
502 * If 'original' is shared (refcount > 1), then EDOOFUS will be
506 sglist_split(struct sglist *original, struct sglist **head, size_t length,
513 if (original->sg_refs > 1)
516 /* Figure out how big of a sglist '*head' has to hold. */
520 for (i = 0; i < original->sg_nseg; i++) {
521 space += original->sg_segs[i].ss_len;
523 if (space >= length) {
525 * If 'length' falls in the middle of a
526 * scatter/gather list entry, then 'split'
527 * holds how much of that entry will remain in
530 split = space - length;
535 /* Nothing to do, so leave head empty. */
540 sg = sglist_alloc(count, mflags);
546 if (sg->sg_maxseg < count)
548 if (sg->sg_nseg != 0)
552 /* Copy 'count' entries to 'sg' from 'original'. */
553 bcopy(original->sg_segs, sg->sg_segs, count *
554 sizeof(struct sglist_seg));
558 * If we had to split a list entry, fixup the last entry in
559 * 'sg' and the new first entry in 'original'. We also
560 * decrement 'count' by 1 since we will only be removing
561 * 'count - 1' segments from 'original' now.
565 sg->sg_segs[count].ss_len -= split;
566 original->sg_segs[count].ss_paddr =
567 sg->sg_segs[count].ss_paddr + split;
568 original->sg_segs[count].ss_len = split;
571 /* Trim 'count' entries from the front of 'original'. */
572 original->sg_nseg -= count;
573 bcopy(original->sg_segs + count, original->sg_segs, count *
574 sizeof(struct sglist_seg));
579 * Append the scatter/gather list elements in 'second' to the
580 * scatter/gather list 'first'. If there is not enough space in
581 * 'first', EFBIG is returned.
584 sglist_join(struct sglist *first, struct sglist *second)
586 struct sglist_seg *flast, *sfirst;
589 /* If 'second' is empty, there is nothing to do. */
590 if (second->sg_nseg == 0)
594 * If the first entry in 'second' can be appended to the last entry
595 * in 'first' then set append to '1'.
598 flast = &first->sg_segs[first->sg_nseg - 1];
599 sfirst = &second->sg_segs[0];
600 if (first->sg_nseg != 0 &&
601 flast->ss_paddr + flast->ss_len == sfirst->ss_paddr)
604 /* Make sure 'first' has enough room. */
605 if (first->sg_nseg + second->sg_nseg - append > first->sg_maxseg)
608 /* Merge last in 'first' and first in 'second' if needed. */
610 flast->ss_len += sfirst->ss_len;
612 /* Append new segments from 'second' to 'first'. */
613 bcopy(first->sg_segs + first->sg_nseg, second->sg_segs + append,
614 (second->sg_nseg - append) * sizeof(struct sglist_seg));
615 first->sg_nseg += second->sg_nseg - append;
616 sglist_reset(second);
621 * Generate a new scatter/gather list from a range of an existing
622 * scatter/gather list. The 'offset' and 'length' parameters specify
623 * the logical range of the 'original' list to extract. If that range
624 * is not a subset of the length of 'original', then EINVAL is
625 * returned. The new scatter/gather list is stored in '*slice'.
627 * If '*slice' is NULL, then a new list will be allocated using
628 * 'mflags'. If M_NOWAIT is specified and the allocation fails,
629 * ENOMEM will be returned.
631 * If '*slice' is not NULL, it should point to an empty sglist. If it
632 * does not have enough room for the remaining space, then EFBIG will
633 * be returned. If '*slice' is not empty, then EINVAL will be
637 sglist_slice(struct sglist *original, struct sglist **slice, size_t offset,
638 size_t length, int mflags)
641 size_t space, end, foffs, loffs;
648 /* Figure out how many segments '*slice' needs to have. */
649 end = offset + length;
654 for (i = 0; i < original->sg_nseg; i++) {
655 space += original->sg_segs[i].ss_len;
656 if (space > offset) {
658 * When we hit the first segment, store its index
659 * in 'fseg' and the offset into the first segment
660 * of 'offset' in 'foffs'.
664 foffs = offset - (space -
665 original->sg_segs[i].ss_len);
670 * When we hit the last segment, break out of
671 * the loop. Store the amount of extra space
672 * at the end of this segment in 'loffs'.
681 /* If we never hit 'end', then 'length' ran off the end, so fail. */
685 if (*slice == NULL) {
686 sg = sglist_alloc(count, mflags);
692 if (sg->sg_maxseg < count)
694 if (sg->sg_nseg != 0)
699 * Copy over 'count' segments from 'original' starting at
702 bcopy(original->sg_segs + fseg, sg->sg_segs,
703 count * sizeof(struct sglist_seg));
706 /* Fixup first and last segments if needed. */
708 sg->sg_segs[0].ss_paddr += foffs;
709 sg->sg_segs[0].ss_len -= foffs;
712 sg->sg_segs[count - 1].ss_len -= loffs;