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 #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 }