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