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