sys/kern/subr_sglist.c

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