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