xref: /freebsd/sys/kern/subr_sglist.c (revision edf8578117e8844e02c0121147f45e4609b30680)
1 /*-
2  * SPDX-License-Identifier: BSD-3-Clause
3  *
4  * Copyright (c) 2008 Yahoo!, Inc.
5  * All rights reserved.
6  * Written by: John Baldwin <jhb@FreeBSD.org>
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
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.
19  *
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
30  * SUCH DAMAGE.
31  */
32 
33 #include <sys/cdefs.h>
34 #include <sys/param.h>
35 #include <sys/kernel.h>
36 #include <sys/bio.h>
37 #include <sys/malloc.h>
38 #include <sys/mbuf.h>
39 #include <sys/proc.h>
40 #include <sys/sglist.h>
41 #include <sys/uio.h>
42 
43 #include <vm/vm.h>
44 #include <vm/vm_page.h>
45 #include <vm/pmap.h>
46 #include <vm/vm_map.h>
47 
48 #include <sys/ktr.h>
49 
50 static MALLOC_DEFINE(M_SGLIST, "sglist", "scatter/gather lists");
51 
52 /*
53  * Convenience macros to save the state of an sglist so it can be restored
54  * if an append attempt fails.  Since sglist's only grow we only need to
55  * save the current count of segments and the length of the ending segment.
56  * Earlier segments will not be changed by an append, and the only change
57  * that can occur to the ending segment is that it can be extended.
58  */
59 struct sgsave {
60 	u_short sg_nseg;
61 	size_t ss_len;
62 };
63 
64 #define	SGLIST_SAVE(sg, sgsave) do {					\
65 	(sgsave).sg_nseg = (sg)->sg_nseg;				\
66 	if ((sgsave).sg_nseg > 0)					\
67 		(sgsave).ss_len = (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len; \
68 	else								\
69 		(sgsave).ss_len = 0;					\
70 } while (0)
71 
72 #define	SGLIST_RESTORE(sg, sgsave) do {					\
73 	(sg)->sg_nseg = (sgsave).sg_nseg;				\
74 	if ((sgsave).sg_nseg > 0)					\
75 		(sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len = (sgsave).ss_len; \
76 } while (0)
77 
78 /*
79  * Append a single (paddr, len) to a sglist.  sg is the list and ss is
80  * the current segment in the list.  If we run out of segments then
81  * EFBIG will be returned.
82  */
83 static __inline int
84 _sglist_append_range(struct sglist *sg, struct sglist_seg **ssp,
85     vm_paddr_t paddr, size_t len)
86 {
87 	struct sglist_seg *ss;
88 
89 	ss = *ssp;
90 	if (ss->ss_paddr + ss->ss_len == paddr)
91 		ss->ss_len += len;
92 	else {
93 		if (sg->sg_nseg == sg->sg_maxseg)
94 			return (EFBIG);
95 		ss++;
96 		ss->ss_paddr = paddr;
97 		ss->ss_len = len;
98 		sg->sg_nseg++;
99 		*ssp = ss;
100 	}
101 	return (0);
102 }
103 
104 /*
105  * Worker routine to append a virtual address range (either kernel or
106  * user) to a scatter/gather list.
107  */
108 static __inline int
109 _sglist_append_buf(struct sglist *sg, void *buf, size_t len, pmap_t pmap,
110     size_t *donep)
111 {
112 	struct sglist_seg *ss;
113 	vm_offset_t vaddr, offset;
114 	vm_paddr_t paddr;
115 	size_t seglen;
116 	int error;
117 
118 	if (donep)
119 		*donep = 0;
120 	if (len == 0)
121 		return (0);
122 
123 	/* Do the first page.  It may have an offset. */
124 	vaddr = (vm_offset_t)buf;
125 	offset = vaddr & PAGE_MASK;
126 	if (pmap != NULL)
127 		paddr = pmap_extract(pmap, vaddr);
128 	else
129 		paddr = pmap_kextract(vaddr);
130 	seglen = MIN(len, PAGE_SIZE - offset);
131 	if (sg->sg_nseg == 0) {
132 		ss = sg->sg_segs;
133 		ss->ss_paddr = paddr;
134 		ss->ss_len = seglen;
135 		sg->sg_nseg = 1;
136 	} else {
137 		ss = &sg->sg_segs[sg->sg_nseg - 1];
138 		error = _sglist_append_range(sg, &ss, paddr, seglen);
139 		if (error)
140 			return (error);
141 	}
142 	vaddr += seglen;
143 	len -= seglen;
144 	if (donep)
145 		*donep += seglen;
146 
147 	while (len > 0) {
148 		seglen = MIN(len, PAGE_SIZE);
149 		if (pmap != NULL)
150 			paddr = pmap_extract(pmap, vaddr);
151 		else
152 			paddr = pmap_kextract(vaddr);
153 		error = _sglist_append_range(sg, &ss, paddr, seglen);
154 		if (error)
155 			return (error);
156 		vaddr += seglen;
157 		len -= seglen;
158 		if (donep)
159 			*donep += seglen;
160 	}
161 
162 	return (0);
163 }
164 
165 /*
166  * Determine the number of scatter/gather list elements needed to
167  * describe a kernel virtual address range.
168  */
169 int
170 sglist_count(void *buf, size_t len)
171 {
172 	vm_offset_t vaddr, vendaddr;
173 	vm_paddr_t lastaddr, paddr;
174 	int nsegs;
175 
176 	if (len == 0)
177 		return (0);
178 
179 	vaddr = trunc_page((vm_offset_t)buf);
180 	vendaddr = (vm_offset_t)buf + len;
181 	nsegs = 1;
182 	lastaddr = pmap_kextract(vaddr);
183 	vaddr += PAGE_SIZE;
184 	while (vaddr < vendaddr) {
185 		paddr = pmap_kextract(vaddr);
186 		if (lastaddr + PAGE_SIZE != paddr)
187 			nsegs++;
188 		lastaddr = paddr;
189 		vaddr += PAGE_SIZE;
190 	}
191 	return (nsegs);
192 }
193 
194 /*
195  * Determine the number of scatter/gather list elements needed to
196  * describe a buffer backed by an array of VM pages.
197  */
198 int
199 sglist_count_vmpages(vm_page_t *m, size_t pgoff, size_t len)
200 {
201 	vm_paddr_t lastaddr, paddr;
202 	int i, nsegs;
203 
204 	if (len == 0)
205 		return (0);
206 
207 	len += pgoff;
208 	nsegs = 1;
209 	lastaddr = VM_PAGE_TO_PHYS(m[0]);
210 	for (i = 1; len > PAGE_SIZE; len -= PAGE_SIZE, i++) {
211 		paddr = VM_PAGE_TO_PHYS(m[i]);
212 		if (lastaddr + PAGE_SIZE != paddr)
213 			nsegs++;
214 		lastaddr = paddr;
215 	}
216 	return (nsegs);
217 }
218 
219 /*
220  * Determine the number of scatter/gather list elements needed to
221  * describe an M_EXTPG mbuf.
222  */
223 int
224 sglist_count_mbuf_epg(struct mbuf *m, size_t off, size_t len)
225 {
226 	vm_paddr_t nextaddr, paddr;
227 	size_t seglen, segoff;
228 	int i, nsegs, pglen, pgoff;
229 
230 	if (len == 0)
231 		return (0);
232 
233 	nsegs = 0;
234 	if (m->m_epg_hdrlen != 0) {
235 		if (off >= m->m_epg_hdrlen) {
236 			off -= m->m_epg_hdrlen;
237 		} else {
238 			seglen = m->m_epg_hdrlen - off;
239 			segoff = off;
240 			seglen = MIN(seglen, len);
241 			off = 0;
242 			len -= seglen;
243 			nsegs += sglist_count(&m->m_epg_hdr[segoff],
244 			    seglen);
245 		}
246 	}
247 	nextaddr = 0;
248 	pgoff = m->m_epg_1st_off;
249 	for (i = 0; i < m->m_epg_npgs && len > 0; i++) {
250 		pglen = m_epg_pagelen(m, i, pgoff);
251 		if (off >= pglen) {
252 			off -= pglen;
253 			pgoff = 0;
254 			continue;
255 		}
256 		seglen = pglen - off;
257 		segoff = pgoff + off;
258 		off = 0;
259 		seglen = MIN(seglen, len);
260 		len -= seglen;
261 		paddr = m->m_epg_pa[i] + segoff;
262 		if (paddr != nextaddr)
263 			nsegs++;
264 		nextaddr = paddr + seglen;
265 		pgoff = 0;
266 	};
267 	if (len != 0) {
268 		seglen = MIN(len, m->m_epg_trllen - off);
269 		len -= seglen;
270 		nsegs += sglist_count(&m->m_epg_trail[off], seglen);
271 	}
272 	KASSERT(len == 0, ("len != 0"));
273 	return (nsegs);
274 }
275 
276 /*
277  * Allocate a scatter/gather list along with 'nsegs' segments.  The
278  * 'mflags' parameters are the same as passed to malloc(9).  The caller
279  * should use sglist_free() to free this list.
280  */
281 struct sglist *
282 sglist_alloc(int nsegs, int mflags)
283 {
284 	struct sglist *sg;
285 
286 	sg = malloc(sizeof(struct sglist) + nsegs * sizeof(struct sglist_seg),
287 	    M_SGLIST, mflags);
288 	if (sg == NULL)
289 		return (NULL);
290 	sglist_init(sg, nsegs, (struct sglist_seg *)(sg + 1));
291 	return (sg);
292 }
293 
294 /*
295  * Free a scatter/gather list allocated via sglist_allc().
296  */
297 void
298 sglist_free(struct sglist *sg)
299 {
300 
301 	if (sg == NULL)
302 		return;
303 
304 	if (refcount_release(&sg->sg_refs))
305 		free(sg, M_SGLIST);
306 }
307 
308 /*
309  * Append the segments to describe a single kernel virtual address
310  * range to a scatter/gather list.  If there are insufficient
311  * segments, then this fails with EFBIG.
312  */
313 int
314 sglist_append(struct sglist *sg, void *buf, size_t len)
315 {
316 	struct sgsave save;
317 	int error;
318 
319 	if (sg->sg_maxseg == 0)
320 		return (EINVAL);
321 	SGLIST_SAVE(sg, save);
322 	error = _sglist_append_buf(sg, buf, len, NULL, NULL);
323 	if (error)
324 		SGLIST_RESTORE(sg, save);
325 	return (error);
326 }
327 
328 /*
329  * Append the segments to describe a bio's data to a scatter/gather list.
330  * If there are insufficient segments, then this fails with EFBIG.
331  *
332  * NOTE: This function expects bio_bcount to be initialized.
333  */
334 int
335 sglist_append_bio(struct sglist *sg, struct bio *bp)
336 {
337 	int error;
338 
339 	if ((bp->bio_flags & BIO_UNMAPPED) == 0)
340 		error = sglist_append(sg, bp->bio_data, bp->bio_bcount);
341 	else
342 		error = sglist_append_vmpages(sg, bp->bio_ma,
343 		    bp->bio_ma_offset, bp->bio_bcount);
344 	return (error);
345 }
346 
347 /*
348  * Append a single physical address range to a scatter/gather list.
349  * If there are insufficient segments, then this fails with EFBIG.
350  */
351 int
352 sglist_append_phys(struct sglist *sg, vm_paddr_t paddr, size_t len)
353 {
354 	struct sglist_seg *ss;
355 	struct sgsave save;
356 	int error;
357 
358 	if (sg->sg_maxseg == 0)
359 		return (EINVAL);
360 	if (len == 0)
361 		return (0);
362 
363 	if (sg->sg_nseg == 0) {
364 		sg->sg_segs[0].ss_paddr = paddr;
365 		sg->sg_segs[0].ss_len = len;
366 		sg->sg_nseg = 1;
367 		return (0);
368 	}
369 	ss = &sg->sg_segs[sg->sg_nseg - 1];
370 	SGLIST_SAVE(sg, save);
371 	error = _sglist_append_range(sg, &ss, paddr, len);
372 	if (error)
373 		SGLIST_RESTORE(sg, save);
374 	return (error);
375 }
376 
377 /*
378  * Append the segments of single multi-page mbuf.
379  * If there are insufficient segments, then this fails with EFBIG.
380  */
381 int
382 sglist_append_mbuf_epg(struct sglist *sg, struct mbuf *m, size_t off,
383     size_t len)
384 {
385 	size_t seglen, segoff;
386 	vm_paddr_t paddr;
387 	int error, i, pglen, pgoff;
388 
389 	M_ASSERTEXTPG(m);
390 
391 	error = 0;
392 	if (m->m_epg_hdrlen != 0) {
393 		if (off >= m->m_epg_hdrlen) {
394 			off -= m->m_epg_hdrlen;
395 		} else {
396 			seglen = m->m_epg_hdrlen - off;
397 			segoff = off;
398 			seglen = MIN(seglen, len);
399 			off = 0;
400 			len -= seglen;
401 			error = sglist_append(sg,
402 			    &m->m_epg_hdr[segoff], seglen);
403 		}
404 	}
405 	pgoff = m->m_epg_1st_off;
406 	for (i = 0; i < m->m_epg_npgs && error == 0 && len > 0; i++) {
407 		pglen = m_epg_pagelen(m, i, pgoff);
408 		if (off >= pglen) {
409 			off -= pglen;
410 			pgoff = 0;
411 			continue;
412 		}
413 		seglen = pglen - off;
414 		segoff = pgoff + off;
415 		off = 0;
416 		seglen = MIN(seglen, len);
417 		len -= seglen;
418 		paddr = m->m_epg_pa[i] + segoff;
419 		error = sglist_append_phys(sg, paddr, seglen);
420 		pgoff = 0;
421 	};
422 	if (error == 0 && len > 0) {
423 		seglen = MIN(len, m->m_epg_trllen - off);
424 		len -= seglen;
425 		error = sglist_append(sg,
426 		    &m->m_epg_trail[off], seglen);
427 	}
428 	if (error == 0)
429 		KASSERT(len == 0, ("len != 0"));
430 	return (error);
431 }
432 
433 /*
434  * Append the segments that describe a single mbuf chain to a
435  * scatter/gather list.  If there are insufficient segments, then this
436  * fails with EFBIG.
437  */
438 int
439 sglist_append_mbuf(struct sglist *sg, struct mbuf *m0)
440 {
441 	struct sgsave save;
442 	struct mbuf *m;
443 	int error;
444 
445 	if (sg->sg_maxseg == 0)
446 		return (EINVAL);
447 
448 	error = 0;
449 	SGLIST_SAVE(sg, save);
450 	for (m = m0; m != NULL; m = m->m_next) {
451 		if (m->m_len > 0) {
452 			if ((m->m_flags & M_EXTPG) != 0)
453 				error = sglist_append_mbuf_epg(sg, m,
454 				    mtod(m, vm_offset_t), m->m_len);
455 			else
456 				error = sglist_append(sg, m->m_data,
457 				    m->m_len);
458 			if (error) {
459 				SGLIST_RESTORE(sg, save);
460 				return (error);
461 			}
462 		}
463 	}
464 	return (0);
465 }
466 
467 /*
468  * Append the segments that describe a single mbuf to a scatter/gather
469  * list.  If there are insufficient segments, then this fails with
470  * EFBIG.
471  */
472 int
473 sglist_append_single_mbuf(struct sglist *sg, struct mbuf *m)
474 {
475 	if ((m->m_flags & M_EXTPG) != 0)
476 		return (sglist_append_mbuf_epg(sg, m,
477 		    mtod(m, vm_offset_t), m->m_len));
478 	else
479 		return (sglist_append(sg, m->m_data, m->m_len));
480 }
481 
482 /*
483  * Append the segments that describe a buffer spanning an array of VM
484  * pages.  The buffer begins at an offset of 'pgoff' in the first
485  * page.
486  */
487 int
488 sglist_append_vmpages(struct sglist *sg, vm_page_t *m, size_t pgoff,
489     size_t len)
490 {
491 	struct sgsave save;
492 	struct sglist_seg *ss;
493 	vm_paddr_t paddr;
494 	size_t seglen;
495 	int error, i;
496 
497 	if (sg->sg_maxseg == 0)
498 		return (EINVAL);
499 	if (len == 0)
500 		return (0);
501 
502 	SGLIST_SAVE(sg, save);
503 	i = 0;
504 	if (sg->sg_nseg == 0) {
505 		seglen = min(PAGE_SIZE - pgoff, len);
506 		sg->sg_segs[0].ss_paddr = VM_PAGE_TO_PHYS(m[0]) + pgoff;
507 		sg->sg_segs[0].ss_len = seglen;
508 		sg->sg_nseg = 1;
509 		pgoff = 0;
510 		len -= seglen;
511 		i++;
512 	}
513 	ss = &sg->sg_segs[sg->sg_nseg - 1];
514 	for (; len > 0; i++, len -= seglen) {
515 		seglen = min(PAGE_SIZE - pgoff, len);
516 		paddr = VM_PAGE_TO_PHYS(m[i]) + pgoff;
517 		error = _sglist_append_range(sg, &ss, paddr, seglen);
518 		if (error) {
519 			SGLIST_RESTORE(sg, save);
520 			return (error);
521 		}
522 		pgoff = 0;
523 	}
524 	return (0);
525 }
526 
527 /*
528  * Append the segments that describe a single user address range to a
529  * scatter/gather list.  If there are insufficient segments, then this
530  * fails with EFBIG.
531  */
532 int
533 sglist_append_user(struct sglist *sg, void *buf, size_t len, struct thread *td)
534 {
535 	struct sgsave save;
536 	int error;
537 
538 	if (sg->sg_maxseg == 0)
539 		return (EINVAL);
540 	SGLIST_SAVE(sg, save);
541 	error = _sglist_append_buf(sg, buf, len,
542 	    vmspace_pmap(td->td_proc->p_vmspace), NULL);
543 	if (error)
544 		SGLIST_RESTORE(sg, save);
545 	return (error);
546 }
547 
548 /*
549  * Append a subset of an existing scatter/gather list 'source' to a
550  * the scatter/gather list 'sg'.  If there are insufficient segments,
551  * then this fails with EFBIG.
552  */
553 int
554 sglist_append_sglist(struct sglist *sg, struct sglist *source, size_t offset,
555     size_t length)
556 {
557 	struct sgsave save;
558 	struct sglist_seg *ss;
559 	size_t seglen;
560 	int error, i;
561 
562 	if (sg->sg_maxseg == 0 || length == 0)
563 		return (EINVAL);
564 	SGLIST_SAVE(sg, save);
565 	error = EINVAL;
566 	ss = &sg->sg_segs[sg->sg_nseg - 1];
567 	for (i = 0; i < source->sg_nseg; i++) {
568 		if (offset >= source->sg_segs[i].ss_len) {
569 			offset -= source->sg_segs[i].ss_len;
570 			continue;
571 		}
572 		seglen = source->sg_segs[i].ss_len - offset;
573 		if (seglen > length)
574 			seglen = length;
575 		error = _sglist_append_range(sg, &ss,
576 		    source->sg_segs[i].ss_paddr + offset, seglen);
577 		if (error)
578 			break;
579 		offset = 0;
580 		length -= seglen;
581 		if (length == 0)
582 			break;
583 	}
584 	if (length != 0)
585 		error = EINVAL;
586 	if (error)
587 		SGLIST_RESTORE(sg, save);
588 	return (error);
589 }
590 
591 /*
592  * Append the segments that describe a single uio to a scatter/gather
593  * list.  If there are insufficient segments, then this fails with
594  * EFBIG.
595  */
596 int
597 sglist_append_uio(struct sglist *sg, struct uio *uio)
598 {
599 	struct iovec *iov;
600 	struct sgsave save;
601 	size_t resid, minlen;
602 	pmap_t pmap;
603 	int error, i;
604 
605 	if (sg->sg_maxseg == 0)
606 		return (EINVAL);
607 
608 	resid = uio->uio_resid;
609 	iov = uio->uio_iov;
610 
611 	if (uio->uio_segflg == UIO_USERSPACE) {
612 		KASSERT(uio->uio_td != NULL,
613 		    ("sglist_append_uio: USERSPACE but no thread"));
614 		pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
615 	} else
616 		pmap = NULL;
617 
618 	error = 0;
619 	SGLIST_SAVE(sg, save);
620 	for (i = 0; i < uio->uio_iovcnt && resid != 0; i++) {
621 		/*
622 		 * Now at the first iovec to load.  Load each iovec
623 		 * until we have exhausted the residual count.
624 		 */
625 		minlen = MIN(resid, iov[i].iov_len);
626 		if (minlen > 0) {
627 			error = _sglist_append_buf(sg, iov[i].iov_base, minlen,
628 			    pmap, NULL);
629 			if (error) {
630 				SGLIST_RESTORE(sg, save);
631 				return (error);
632 			}
633 			resid -= minlen;
634 		}
635 	}
636 	return (0);
637 }
638 
639 /*
640  * Append the segments that describe at most 'resid' bytes from a
641  * single uio to a scatter/gather list.  If there are insufficient
642  * segments, then only the amount that fits is appended.
643  */
644 int
645 sglist_consume_uio(struct sglist *sg, struct uio *uio, size_t resid)
646 {
647 	struct iovec *iov;
648 	size_t done;
649 	pmap_t pmap;
650 	int error, len;
651 
652 	if (sg->sg_maxseg == 0)
653 		return (EINVAL);
654 
655 	if (uio->uio_segflg == UIO_USERSPACE) {
656 		KASSERT(uio->uio_td != NULL,
657 		    ("sglist_consume_uio: USERSPACE but no thread"));
658 		pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
659 	} else
660 		pmap = NULL;
661 
662 	error = 0;
663 	while (resid > 0 && uio->uio_resid) {
664 		iov = uio->uio_iov;
665 		len = iov->iov_len;
666 		if (len == 0) {
667 			uio->uio_iov++;
668 			uio->uio_iovcnt--;
669 			continue;
670 		}
671 		if (len > resid)
672 			len = resid;
673 
674 		/*
675 		 * Try to append this iovec.  If we run out of room,
676 		 * then break out of the loop.
677 		 */
678 		error = _sglist_append_buf(sg, iov->iov_base, len, pmap, &done);
679 		iov->iov_base = (char *)iov->iov_base + done;
680 		iov->iov_len -= done;
681 		uio->uio_resid -= done;
682 		uio->uio_offset += done;
683 		resid -= done;
684 		if (error)
685 			break;
686 	}
687 	return (0);
688 }
689 
690 /*
691  * Allocate and populate a scatter/gather list to describe a single
692  * kernel virtual address range.
693  */
694 struct sglist *
695 sglist_build(void *buf, size_t len, int mflags)
696 {
697 	struct sglist *sg;
698 	int nsegs;
699 
700 	if (len == 0)
701 		return (NULL);
702 
703 	nsegs = sglist_count(buf, len);
704 	sg = sglist_alloc(nsegs, mflags);
705 	if (sg == NULL)
706 		return (NULL);
707 	if (sglist_append(sg, buf, len) != 0) {
708 		sglist_free(sg);
709 		return (NULL);
710 	}
711 	return (sg);
712 }
713 
714 /*
715  * Clone a new copy of a scatter/gather list.
716  */
717 struct sglist *
718 sglist_clone(struct sglist *sg, int mflags)
719 {
720 	struct sglist *new;
721 
722 	if (sg == NULL)
723 		return (NULL);
724 	new = sglist_alloc(sg->sg_maxseg, mflags);
725 	if (new == NULL)
726 		return (NULL);
727 	new->sg_nseg = sg->sg_nseg;
728 	bcopy(sg->sg_segs, new->sg_segs, sizeof(struct sglist_seg) *
729 	    sg->sg_nseg);
730 	return (new);
731 }
732 
733 /*
734  * Calculate the total length of the segments described in a
735  * scatter/gather list.
736  */
737 size_t
738 sglist_length(struct sglist *sg)
739 {
740 	size_t space;
741 	int i;
742 
743 	space = 0;
744 	for (i = 0; i < sg->sg_nseg; i++)
745 		space += sg->sg_segs[i].ss_len;
746 	return (space);
747 }
748 
749 /*
750  * Split a scatter/gather list into two lists.  The scatter/gather
751  * entries for the first 'length' bytes of the 'original' list are
752  * stored in the '*head' list and are removed from 'original'.
753  *
754  * If '*head' is NULL, then a new list will be allocated using
755  * 'mflags'.  If M_NOWAIT is specified and the allocation fails,
756  * ENOMEM will be returned.
757  *
758  * If '*head' is not NULL, it should point to an empty sglist.  If it
759  * does not have enough room for the remaining space, then EFBIG will
760  * be returned.  If '*head' is not empty, then EINVAL will be
761  * returned.
762  *
763  * If 'original' is shared (refcount > 1), then EDOOFUS will be
764  * returned.
765  */
766 int
767 sglist_split(struct sglist *original, struct sglist **head, size_t length,
768     int mflags)
769 {
770 	struct sglist *sg;
771 	size_t space, split;
772 	int count, i;
773 
774 	if (original->sg_refs > 1)
775 		return (EDOOFUS);
776 
777 	/* Figure out how big of a sglist '*head' has to hold. */
778 	count = 0;
779 	space = 0;
780 	split = 0;
781 	for (i = 0; i < original->sg_nseg; i++) {
782 		space += original->sg_segs[i].ss_len;
783 		count++;
784 		if (space >= length) {
785 			/*
786 			 * If 'length' falls in the middle of a
787 			 * scatter/gather list entry, then 'split'
788 			 * holds how much of that entry will remain in
789 			 * 'original'.
790 			 */
791 			split = space - length;
792 			break;
793 		}
794 	}
795 
796 	/* Nothing to do, so leave head empty. */
797 	if (count == 0)
798 		return (0);
799 
800 	if (*head == NULL) {
801 		sg = sglist_alloc(count, mflags);
802 		if (sg == NULL)
803 			return (ENOMEM);
804 		*head = sg;
805 	} else {
806 		sg = *head;
807 		if (sg->sg_maxseg < count)
808 			return (EFBIG);
809 		if (sg->sg_nseg != 0)
810 			return (EINVAL);
811 	}
812 
813 	/* Copy 'count' entries to 'sg' from 'original'. */
814 	bcopy(original->sg_segs, sg->sg_segs, count *
815 	    sizeof(struct sglist_seg));
816 	sg->sg_nseg = count;
817 
818 	/*
819 	 * If we had to split a list entry, fixup the last entry in
820 	 * 'sg' and the new first entry in 'original'.  We also
821 	 * decrement 'count' by 1 since we will only be removing
822 	 * 'count - 1' segments from 'original' now.
823 	 */
824 	if (split != 0) {
825 		count--;
826 		sg->sg_segs[count].ss_len -= split;
827 		original->sg_segs[count].ss_paddr =
828 		    sg->sg_segs[count].ss_paddr + split;
829 		original->sg_segs[count].ss_len = split;
830 	}
831 
832 	/* Trim 'count' entries from the front of 'original'. */
833 	original->sg_nseg -= count;
834 	bcopy(original->sg_segs + count, original->sg_segs, count *
835 	    sizeof(struct sglist_seg));
836 	return (0);
837 }
838 
839 /*
840  * Append the scatter/gather list elements in 'second' to the
841  * scatter/gather list 'first'.  If there is not enough space in
842  * 'first', EFBIG is returned.
843  */
844 int
845 sglist_join(struct sglist *first, struct sglist *second)
846 {
847 	struct sglist_seg *flast, *sfirst;
848 	int append;
849 
850 	/* If 'second' is empty, there is nothing to do. */
851 	if (second->sg_nseg == 0)
852 		return (0);
853 
854 	/*
855 	 * If the first entry in 'second' can be appended to the last entry
856 	 * in 'first' then set append to '1'.
857 	 */
858 	append = 0;
859 	flast = &first->sg_segs[first->sg_nseg - 1];
860 	sfirst = &second->sg_segs[0];
861 	if (first->sg_nseg != 0 &&
862 	    flast->ss_paddr + flast->ss_len == sfirst->ss_paddr)
863 		append = 1;
864 
865 	/* Make sure 'first' has enough room. */
866 	if (first->sg_nseg + second->sg_nseg - append > first->sg_maxseg)
867 		return (EFBIG);
868 
869 	/* Merge last in 'first' and first in 'second' if needed. */
870 	if (append)
871 		flast->ss_len += sfirst->ss_len;
872 
873 	/* Append new segments from 'second' to 'first'. */
874 	bcopy(first->sg_segs + first->sg_nseg, second->sg_segs + append,
875 	    (second->sg_nseg - append) * sizeof(struct sglist_seg));
876 	first->sg_nseg += second->sg_nseg - append;
877 	sglist_reset(second);
878 	return (0);
879 }
880 
881 /*
882  * Generate a new scatter/gather list from a range of an existing
883  * scatter/gather list.  The 'offset' and 'length' parameters specify
884  * the logical range of the 'original' list to extract.  If that range
885  * is not a subset of the length of 'original', then EINVAL is
886  * returned.  The new scatter/gather list is stored in '*slice'.
887  *
888  * If '*slice' is NULL, then a new list will be allocated using
889  * 'mflags'.  If M_NOWAIT is specified and the allocation fails,
890  * ENOMEM will be returned.
891  *
892  * If '*slice' is not NULL, it should point to an empty sglist.  If it
893  * does not have enough room for the remaining space, then EFBIG will
894  * be returned.  If '*slice' is not empty, then EINVAL will be
895  * returned.
896  */
897 int
898 sglist_slice(struct sglist *original, struct sglist **slice, size_t offset,
899     size_t length, int mflags)
900 {
901 	struct sglist *sg;
902 	size_t space, end, foffs, loffs;
903 	int count, i, fseg;
904 
905 	/* Nothing to do. */
906 	if (length == 0)
907 		return (0);
908 
909 	/* Figure out how many segments '*slice' needs to have. */
910 	end = offset + length;
911 	space = 0;
912 	count = 0;
913 	fseg = 0;
914 	foffs = loffs = 0;
915 	for (i = 0; i < original->sg_nseg; i++) {
916 		space += original->sg_segs[i].ss_len;
917 		if (space > offset) {
918 			/*
919 			 * When we hit the first segment, store its index
920 			 * in 'fseg' and the offset into the first segment
921 			 * of 'offset' in 'foffs'.
922 			 */
923 			if (count == 0) {
924 				fseg = i;
925 				foffs = offset - (space -
926 				    original->sg_segs[i].ss_len);
927 				CTR1(KTR_DEV, "sglist_slice: foffs = %08lx",
928 				    foffs);
929 			}
930 			count++;
931 
932 			/*
933 			 * When we hit the last segment, break out of
934 			 * the loop.  Store the amount of extra space
935 			 * at the end of this segment in 'loffs'.
936 			 */
937 			if (space >= end) {
938 				loffs = space - end;
939 				CTR1(KTR_DEV, "sglist_slice: loffs = %08lx",
940 				    loffs);
941 				break;
942 			}
943 		}
944 	}
945 
946 	/* If we never hit 'end', then 'length' ran off the end, so fail. */
947 	if (space < end)
948 		return (EINVAL);
949 
950 	if (*slice == NULL) {
951 		sg = sglist_alloc(count, mflags);
952 		if (sg == NULL)
953 			return (ENOMEM);
954 		*slice = sg;
955 	} else {
956 		sg = *slice;
957 		if (sg->sg_maxseg < count)
958 			return (EFBIG);
959 		if (sg->sg_nseg != 0)
960 			return (EINVAL);
961 	}
962 
963 	/*
964 	 * Copy over 'count' segments from 'original' starting at
965 	 * 'fseg' to 'sg'.
966 	 */
967 	bcopy(original->sg_segs + fseg, sg->sg_segs,
968 	    count * sizeof(struct sglist_seg));
969 	sg->sg_nseg = count;
970 
971 	/* Fixup first and last segments if needed. */
972 	if (foffs != 0) {
973 		sg->sg_segs[0].ss_paddr += foffs;
974 		sg->sg_segs[0].ss_len -= foffs;
975 		CTR2(KTR_DEV, "sglist_slice seg[0]: %08lx:%08lx",
976 		    (long)sg->sg_segs[0].ss_paddr, sg->sg_segs[0].ss_len);
977 	}
978 	if (loffs != 0) {
979 		sg->sg_segs[count - 1].ss_len -= loffs;
980 		CTR2(KTR_DEV, "sglist_slice seg[%d]: len %08x", count - 1,
981 		    sg->sg_segs[count - 1].ss_len);
982 	}
983 	return (0);
984 }
985