sys/kern/subr_sglist.c

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