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