1/*-
2 * Copyright (c) 2008 Yahoo!, Inc.
3 * All rights reserved.
4 * Written by: John Baldwin <jhb@FreeBSD.org>
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
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.
17 *
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
28 * SUCH DAMAGE.
29 */
30
31#include <sys/cdefs.h>
32__FBSDID("$FreeBSD: stable/11/sys/kern/subr_sglist.c 345039 2019-03-11 22:48:51Z jhb $");
33
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
50static 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 */
59struct 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 */
83static __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 */
108static __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 */
169int
170sglist_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 */
198int
199sglist_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 * Allocate a scatter/gather list along with 'nsegs' segments.  The
221 * 'mflags' parameters are the same as passed to malloc(9).  The caller
222 * should use sglist_free() to free this list.
223 */
224struct sglist *
225sglist_alloc(int nsegs, int mflags)
226{
227	struct sglist *sg;
228
229	sg = malloc(sizeof(struct sglist) + nsegs * sizeof(struct sglist_seg),
230	    M_SGLIST, mflags);
231	if (sg == NULL)
232		return (NULL);
233	sglist_init(sg, nsegs, (struct sglist_seg *)(sg + 1));
234	return (sg);
235}
236
237/*
238 * Free a scatter/gather list allocated via sglist_allc().
239 */
240void
241sglist_free(struct sglist *sg)
242{
243
244	if (sg == NULL)
245		return;
246
247	if (refcount_release(&sg->sg_refs))
248		free(sg, M_SGLIST);
249}
250
251/*
252 * Append the segments to describe a single kernel virtual address
253 * range to a scatter/gather list.  If there are insufficient
254 * segments, then this fails with EFBIG.
255 */
256int
257sglist_append(struct sglist *sg, void *buf, size_t len)
258{
259	struct sgsave save;
260	int error;
261
262	if (sg->sg_maxseg == 0)
263		return (EINVAL);
264	SGLIST_SAVE(sg, save);
265	error = _sglist_append_buf(sg, buf, len, NULL, NULL);
266	if (error)
267		SGLIST_RESTORE(sg, save);
268	return (error);
269}
270
271/*
272 * Append the segments to describe a bio's data to a scatter/gather list.
273 * If there are insufficient segments, then this fails with EFBIG.
274 *
275 * NOTE: This function expects bio_bcount to be initialized.
276 */
277int
278sglist_append_bio(struct sglist *sg, struct bio *bp)
279{
280	int error;
281
282	if ((bp->bio_flags & BIO_UNMAPPED) == 0)
283		error = sglist_append(sg, bp->bio_data, bp->bio_bcount);
284	else
285		error = sglist_append_vmpages(sg, bp->bio_ma,
286		    bp->bio_ma_offset, bp->bio_bcount);
287	return (error);
288}
289
290/*
291 * Append a single physical address range to a scatter/gather list.
292 * If there are insufficient segments, then this fails with EFBIG.
293 */
294int
295sglist_append_phys(struct sglist *sg, vm_paddr_t paddr, size_t len)
296{
297	struct sglist_seg *ss;
298	struct sgsave save;
299	int error;
300
301	if (sg->sg_maxseg == 0)
302		return (EINVAL);
303	if (len == 0)
304		return (0);
305
306	if (sg->sg_nseg == 0) {
307		sg->sg_segs[0].ss_paddr = paddr;
308		sg->sg_segs[0].ss_len = len;
309		sg->sg_nseg = 1;
310		return (0);
311	}
312	ss = &sg->sg_segs[sg->sg_nseg - 1];
313	SGLIST_SAVE(sg, save);
314	error = _sglist_append_range(sg, &ss, paddr, len);
315	if (error)
316		SGLIST_RESTORE(sg, save);
317	return (error);
318}
319
320/*
321 * Append the segments that describe a single mbuf chain to a
322 * scatter/gather list.  If there are insufficient segments, then this
323 * fails with EFBIG.
324 */
325int
326sglist_append_mbuf(struct sglist *sg, struct mbuf *m0)
327{
328	struct sgsave save;
329	struct mbuf *m;
330	int error;
331
332	if (sg->sg_maxseg == 0)
333		return (EINVAL);
334
335	error = 0;
336	SGLIST_SAVE(sg, save);
337	for (m = m0; m != NULL; m = m->m_next) {
338		if (m->m_len > 0) {
339			error = sglist_append(sg, m->m_data, m->m_len);
340			if (error) {
341				SGLIST_RESTORE(sg, save);
342				return (error);
343			}
344		}
345	}
346	return (0);
347}
348
349/*
350 * Append the segments that describe a buffer spanning an array of VM
351 * pages.  The buffer begins at an offset of 'pgoff' in the first
352 * page.
353 */
354int
355sglist_append_vmpages(struct sglist *sg, vm_page_t *m, size_t pgoff,
356    size_t len)
357{
358	struct sgsave save;
359	struct sglist_seg *ss;
360	vm_paddr_t paddr;
361	size_t seglen;
362	int error, i;
363
364	if (sg->sg_maxseg == 0)
365		return (EINVAL);
366	if (len == 0)
367		return (0);
368
369	SGLIST_SAVE(sg, save);
370	i = 0;
371	if (sg->sg_nseg == 0) {
372		seglen = min(PAGE_SIZE - pgoff, len);
373		sg->sg_segs[0].ss_paddr = VM_PAGE_TO_PHYS(m[0]) + pgoff;
374		sg->sg_segs[0].ss_len = seglen;
375		sg->sg_nseg = 1;
376		pgoff = 0;
377		len -= seglen;
378		i++;
379	}
380	ss = &sg->sg_segs[sg->sg_nseg - 1];
381	for (; len > 0; i++, len -= seglen) {
382		seglen = min(PAGE_SIZE - pgoff, len);
383		paddr = VM_PAGE_TO_PHYS(m[i]) + pgoff;
384		error = _sglist_append_range(sg, &ss, paddr, seglen);
385		if (error) {
386			SGLIST_RESTORE(sg, save);
387			return (error);
388		}
389		pgoff = 0;
390	}
391	return (0);
392}
393
394/*
395 * Append the segments that describe a single user address range to a
396 * scatter/gather list.  If there are insufficient segments, then this
397 * fails with EFBIG.
398 */
399int
400sglist_append_user(struct sglist *sg, void *buf, size_t len, struct thread *td)
401{
402	struct sgsave save;
403	int error;
404
405	if (sg->sg_maxseg == 0)
406		return (EINVAL);
407	SGLIST_SAVE(sg, save);
408	error = _sglist_append_buf(sg, buf, len,
409	    vmspace_pmap(td->td_proc->p_vmspace), NULL);
410	if (error)
411		SGLIST_RESTORE(sg, save);
412	return (error);
413}
414
415/*
416 * Append a subset of an existing scatter/gather list 'source' to a
417 * the scatter/gather list 'sg'.  If there are insufficient segments,
418 * then this fails with EFBIG.
419 */
420int
421sglist_append_sglist(struct sglist *sg, struct sglist *source, size_t offset,
422    size_t length)
423{
424	struct sgsave save;
425	struct sglist_seg *ss;
426	size_t seglen;
427	int error, i;
428
429	if (sg->sg_maxseg == 0 || length == 0)
430		return (EINVAL);
431	SGLIST_SAVE(sg, save);
432	error = EINVAL;
433	ss = &sg->sg_segs[sg->sg_nseg - 1];
434	for (i = 0; i < source->sg_nseg; i++) {
435		if (offset >= source->sg_segs[i].ss_len) {
436			offset -= source->sg_segs[i].ss_len;
437			continue;
438		}
439		seglen = source->sg_segs[i].ss_len - offset;
440		if (seglen > length)
441			seglen = length;
442		error = _sglist_append_range(sg, &ss,
443		    source->sg_segs[i].ss_paddr + offset, seglen);
444		if (error)
445			break;
446		offset = 0;
447		length -= seglen;
448		if (length == 0)
449			break;
450	}
451	if (length != 0)
452		error = EINVAL;
453	if (error)
454		SGLIST_RESTORE(sg, save);
455	return (error);
456}
457
458/*
459 * Append the segments that describe a single uio to a scatter/gather
460 * list.  If there are insufficient segments, then this fails with
461 * EFBIG.
462 */
463int
464sglist_append_uio(struct sglist *sg, struct uio *uio)
465{
466	struct iovec *iov;
467	struct sgsave save;
468	size_t resid, minlen;
469	pmap_t pmap;
470	int error, i;
471
472	if (sg->sg_maxseg == 0)
473		return (EINVAL);
474
475	resid = uio->uio_resid;
476	iov = uio->uio_iov;
477
478	if (uio->uio_segflg == UIO_USERSPACE) {
479		KASSERT(uio->uio_td != NULL,
480		    ("sglist_append_uio: USERSPACE but no thread"));
481		pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
482	} else
483		pmap = NULL;
484
485	error = 0;
486	SGLIST_SAVE(sg, save);
487	for (i = 0; i < uio->uio_iovcnt && resid != 0; i++) {
488		/*
489		 * Now at the first iovec to load.  Load each iovec
490		 * until we have exhausted the residual count.
491		 */
492		minlen = MIN(resid, iov[i].iov_len);
493		if (minlen > 0) {
494			error = _sglist_append_buf(sg, iov[i].iov_base, minlen,
495			    pmap, NULL);
496			if (error) {
497				SGLIST_RESTORE(sg, save);
498				return (error);
499			}
500			resid -= minlen;
501		}
502	}
503	return (0);
504}
505
506/*
507 * Append the segments that describe at most 'resid' bytes from a
508 * single uio to a scatter/gather list.  If there are insufficient
509 * segments, then only the amount that fits is appended.
510 */
511int
512sglist_consume_uio(struct sglist *sg, struct uio *uio, size_t resid)
513{
514	struct iovec *iov;
515	size_t done;
516	pmap_t pmap;
517	int error, len;
518
519	if (sg->sg_maxseg == 0)
520		return (EINVAL);
521
522	if (uio->uio_segflg == UIO_USERSPACE) {
523		KASSERT(uio->uio_td != NULL,
524		    ("sglist_consume_uio: USERSPACE but no thread"));
525		pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace);
526	} else
527		pmap = NULL;
528
529	error = 0;
530	while (resid > 0 && uio->uio_resid) {
531		iov = uio->uio_iov;
532		len = iov->iov_len;
533		if (len == 0) {
534			uio->uio_iov++;
535			uio->uio_iovcnt--;
536			continue;
537		}
538		if (len > resid)
539			len = resid;
540
541		/*
542		 * Try to append this iovec.  If we run out of room,
543		 * then break out of the loop.
544		 */
545		error = _sglist_append_buf(sg, iov->iov_base, len, pmap, &done);
546		iov->iov_base = (char *)iov->iov_base + done;
547		iov->iov_len -= done;
548		uio->uio_resid -= done;
549		uio->uio_offset += done;
550		resid -= done;
551		if (error)
552			break;
553	}
554	return (0);
555}
556
557/*
558 * Allocate and populate a scatter/gather list to describe a single
559 * kernel virtual address range.
560 */
561struct sglist *
562sglist_build(void *buf, size_t len, int mflags)
563{
564	struct sglist *sg;
565	int nsegs;
566
567	if (len == 0)
568		return (NULL);
569
570	nsegs = sglist_count(buf, len);
571	sg = sglist_alloc(nsegs, mflags);
572	if (sg == NULL)
573		return (NULL);
574	if (sglist_append(sg, buf, len) != 0) {
575		sglist_free(sg);
576		return (NULL);
577	}
578	return (sg);
579}
580
581/*
582 * Clone a new copy of a scatter/gather list.
583 */
584struct sglist *
585sglist_clone(struct sglist *sg, int mflags)
586{
587	struct sglist *new;
588
589	if (sg == NULL)
590		return (NULL);
591	new = sglist_alloc(sg->sg_maxseg, mflags);
592	if (new == NULL)
593		return (NULL);
594	new->sg_nseg = sg->sg_nseg;
595	bcopy(sg->sg_segs, new->sg_segs, sizeof(struct sglist_seg) *
596	    sg->sg_nseg);
597	return (new);
598}
599
600/*
601 * Calculate the total length of the segments described in a
602 * scatter/gather list.
603 */
604size_t
605sglist_length(struct sglist *sg)
606{
607	size_t space;
608	int i;
609
610	space = 0;
611	for (i = 0; i < sg->sg_nseg; i++)
612		space += sg->sg_segs[i].ss_len;
613	return (space);
614}
615
616/*
617 * Split a scatter/gather list into two lists.  The scatter/gather
618 * entries for the first 'length' bytes of the 'original' list are
619 * stored in the '*head' list and are removed from 'original'.
620 *
621 * If '*head' is NULL, then a new list will be allocated using
622 * 'mflags'.  If M_NOWAIT is specified and the allocation fails,
623 * ENOMEM will be returned.
624 *
625 * If '*head' is not NULL, it should point to an empty sglist.  If it
626 * does not have enough room for the remaining space, then EFBIG will
627 * be returned.  If '*head' is not empty, then EINVAL will be
628 * returned.
629 *
630 * If 'original' is shared (refcount > 1), then EDOOFUS will be
631 * returned.
632 */
633int
634sglist_split(struct sglist *original, struct sglist **head, size_t length,
635    int mflags)
636{
637	struct sglist *sg;
638	size_t space, split;
639	int count, i;
640
641	if (original->sg_refs > 1)
642		return (EDOOFUS);
643
644	/* Figure out how big of a sglist '*head' has to hold. */
645	count = 0;
646	space = 0;
647	split = 0;
648	for (i = 0; i < original->sg_nseg; i++) {
649		space += original->sg_segs[i].ss_len;
650		count++;
651		if (space >= length) {
652			/*
653			 * If 'length' falls in the middle of a
654			 * scatter/gather list entry, then 'split'
655			 * holds how much of that entry will remain in
656			 * 'original'.
657			 */
658			split = space - length;
659			break;
660		}
661	}
662
663	/* Nothing to do, so leave head empty. */
664	if (count == 0)
665		return (0);
666
667	if (*head == NULL) {
668		sg = sglist_alloc(count, mflags);
669		if (sg == NULL)
670			return (ENOMEM);
671		*head = sg;
672	} else {
673		sg = *head;
674		if (sg->sg_maxseg < count)
675			return (EFBIG);
676		if (sg->sg_nseg != 0)
677			return (EINVAL);
678	}
679
680	/* Copy 'count' entries to 'sg' from 'original'. */
681	bcopy(original->sg_segs, sg->sg_segs, count *
682	    sizeof(struct sglist_seg));
683	sg->sg_nseg = count;
684
685	/*
686	 * If we had to split a list entry, fixup the last entry in
687	 * 'sg' and the new first entry in 'original'.  We also
688	 * decrement 'count' by 1 since we will only be removing
689	 * 'count - 1' segments from 'original' now.
690	 */
691	if (split != 0) {
692		count--;
693		sg->sg_segs[count].ss_len -= split;
694		original->sg_segs[count].ss_paddr =
695		    sg->sg_segs[count].ss_paddr + split;
696		original->sg_segs[count].ss_len = split;
697	}
698
699	/* Trim 'count' entries from the front of 'original'. */
700	original->sg_nseg -= count;
701	bcopy(original->sg_segs + count, original->sg_segs, count *
702	    sizeof(struct sglist_seg));
703	return (0);
704}
705
706/*
707 * Append the scatter/gather list elements in 'second' to the
708 * scatter/gather list 'first'.  If there is not enough space in
709 * 'first', EFBIG is returned.
710 */
711int
712sglist_join(struct sglist *first, struct sglist *second)
713{
714	struct sglist_seg *flast, *sfirst;
715	int append;
716
717	/* If 'second' is empty, there is nothing to do. */
718	if (second->sg_nseg == 0)
719		return (0);
720
721	/*
722	 * If the first entry in 'second' can be appended to the last entry
723	 * in 'first' then set append to '1'.
724	 */
725	append = 0;
726	flast = &first->sg_segs[first->sg_nseg - 1];
727	sfirst = &second->sg_segs[0];
728	if (first->sg_nseg != 0 &&
729	    flast->ss_paddr + flast->ss_len == sfirst->ss_paddr)
730		append = 1;
731
732	/* Make sure 'first' has enough room. */
733	if (first->sg_nseg + second->sg_nseg - append > first->sg_maxseg)
734		return (EFBIG);
735
736	/* Merge last in 'first' and first in 'second' if needed. */
737	if (append)
738		flast->ss_len += sfirst->ss_len;
739
740	/* Append new segments from 'second' to 'first'. */
741	bcopy(first->sg_segs + first->sg_nseg, second->sg_segs + append,
742	    (second->sg_nseg - append) * sizeof(struct sglist_seg));
743	first->sg_nseg += second->sg_nseg - append;
744	sglist_reset(second);
745	return (0);
746}
747
748/*
749 * Generate a new scatter/gather list from a range of an existing
750 * scatter/gather list.  The 'offset' and 'length' parameters specify
751 * the logical range of the 'original' list to extract.  If that range
752 * is not a subset of the length of 'original', then EINVAL is
753 * returned.  The new scatter/gather list is stored in '*slice'.
754 *
755 * If '*slice' is NULL, then a new list will be allocated using
756 * 'mflags'.  If M_NOWAIT is specified and the allocation fails,
757 * ENOMEM will be returned.
758 *
759 * If '*slice' is not NULL, it should point to an empty sglist.  If it
760 * does not have enough room for the remaining space, then EFBIG will
761 * be returned.  If '*slice' is not empty, then EINVAL will be
762 * returned.
763 */
764int
765sglist_slice(struct sglist *original, struct sglist **slice, size_t offset,
766    size_t length, int mflags)
767{
768	struct sglist *sg;
769	size_t space, end, foffs, loffs;
770	int count, i, fseg;
771
772	/* Nothing to do. */
773	if (length == 0)
774		return (0);
775
776	/* Figure out how many segments '*slice' needs to have. */
777	end = offset + length;
778	space = 0;
779	count = 0;
780	fseg = 0;
781	foffs = loffs = 0;
782	for (i = 0; i < original->sg_nseg; i++) {
783		space += original->sg_segs[i].ss_len;
784		if (space > offset) {
785			/*
786			 * When we hit the first segment, store its index
787			 * in 'fseg' and the offset into the first segment
788			 * of 'offset' in 'foffs'.
789			 */
790			if (count == 0) {
791				fseg = i;
792				foffs = offset - (space -
793				    original->sg_segs[i].ss_len);
794				CTR1(KTR_DEV, "sglist_slice: foffs = %08lx",
795				    foffs);
796			}
797			count++;
798
799			/*
800			 * When we hit the last segment, break out of
801			 * the loop.  Store the amount of extra space
802			 * at the end of this segment in 'loffs'.
803			 */
804			if (space >= end) {
805				loffs = space - end;
806				CTR1(KTR_DEV, "sglist_slice: loffs = %08lx",
807				    loffs);
808				break;
809			}
810		}
811	}
812
813	/* If we never hit 'end', then 'length' ran off the end, so fail. */
814	if (space < end)
815		return (EINVAL);
816
817	if (*slice == NULL) {
818		sg = sglist_alloc(count, mflags);
819		if (sg == NULL)
820			return (ENOMEM);
821		*slice = sg;
822	} else {
823		sg = *slice;
824		if (sg->sg_maxseg < count)
825			return (EFBIG);
826		if (sg->sg_nseg != 0)
827			return (EINVAL);
828	}
829
830	/*
831	 * Copy over 'count' segments from 'original' starting at
832	 * 'fseg' to 'sg'.
833	 */
834	bcopy(original->sg_segs + fseg, sg->sg_segs,
835	    count * sizeof(struct sglist_seg));
836	sg->sg_nseg = count;
837
838	/* Fixup first and last segments if needed. */
839	if (foffs != 0) {
840		sg->sg_segs[0].ss_paddr += foffs;
841		sg->sg_segs[0].ss_len -= foffs;
842		CTR2(KTR_DEV, "sglist_slice seg[0]: %08lx:%08lx",
843		    (long)sg->sg_segs[0].ss_paddr, sg->sg_segs[0].ss_len);
844	}
845	if (loffs != 0) {
846		sg->sg_segs[count - 1].ss_len -= loffs;
847		CTR2(KTR_DEV, "sglist_slice seg[%d]: len %08x", count - 1,
848		    sg->sg_segs[count - 1].ss_len);
849	}
850	return (0);
851}
852