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 * $FreeBSD: src/sys/kern/subr_sglist.c,v 1.3 2009/08/21 02:59:07 jhb Exp $ 31 */ 32 33 34 #include <sys/param.h> 35 #include <sys/kernel.h> 36 #include <sys/malloc.h> 37 #include <sys/mbuf.h> 38 #include <sys/proc.h> 39 #include <sys/sglist.h> 40 #include <sys/uio.h> 41 42 #include <vm/vm.h> 43 #include <vm/pmap.h> 44 #include <vm/vm_map.h> 45 46 #include <sys/ktr.h> 47 48 static MALLOC_DEFINE(M_SGLIST, "sglist", "scatter/gather lists"); 49 50 /* 51 * Convenience macros to save the state of an sglist so it can be restored 52 * if an append attempt fails. Since sglist's only grow we only need to 53 * save the current count of segments and the length of the ending segment. 54 * Earlier segments will not be changed by an append, and the only change 55 * that can occur to the ending segment is that it can be extended. 56 */ 57 struct sgsave { 58 u_short sg_nseg; 59 size_t ss_len; 60 }; 61 62 #define SGLIST_SAVE(sg, sgsave) do { \ 63 (sgsave).sg_nseg = (sg)->sg_nseg; \ 64 if ((sgsave).sg_nseg > 0) \ 65 (sgsave).ss_len = (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len; \ 66 else \ 67 (sgsave).ss_len = 0; \ 68 } while (0) 69 70 #define SGLIST_RESTORE(sg, sgsave) do { \ 71 (sg)->sg_nseg = (sgsave).sg_nseg; \ 72 if ((sgsave).sg_nseg > 0) \ 73 (sg)->sg_segs[(sgsave).sg_nseg - 1].ss_len = (sgsave).ss_len; \ 74 } while (0) 75 76 /* 77 * Append a single (paddr, len) to a sglist. sg is the list and ss is 78 * the current segment in the list. If we run out of segments then 79 * EFBIG will be returned. 80 */ 81 static __inline int 82 _sglist_append_range(struct sglist *sg, struct sglist_seg **ssp, 83 vm_paddr_t paddr, size_t len) 84 { 85 struct sglist_seg *ss; 86 87 ss = *ssp; 88 if (ss->ss_paddr + ss->ss_len == paddr) 89 ss->ss_len += len; 90 else { 91 if (sg->sg_nseg == sg->sg_maxseg) 92 return (EFBIG); 93 ss++; 94 ss->ss_paddr = paddr; 95 ss->ss_len = len; 96 sg->sg_nseg++; 97 *ssp = ss; 98 } 99 return (0); 100 } 101 102 /* 103 * Worker routine to append a virtual address range (either kernel or 104 * user) to a scatter/gather list. 105 */ 106 static __inline int 107 _sglist_append_buf(struct sglist *sg, void *buf, size_t len, pmap_t pmap, 108 size_t *donep) 109 { 110 struct sglist_seg *ss; 111 vm_offset_t vaddr, offset; 112 vm_paddr_t paddr; 113 size_t seglen; 114 int error; 115 116 if (donep) 117 *donep = 0; 118 if (len == 0) 119 return (0); 120 121 /* Do the first page. It may have an offset. */ 122 vaddr = (vm_offset_t)buf; 123 offset = vaddr & PAGE_MASK; 124 if (pmap != NULL) 125 paddr = pmap_extract(pmap, vaddr); 126 else 127 paddr = pmap_kextract(vaddr); 128 seglen = MIN(len, PAGE_SIZE - offset); 129 if (sg->sg_nseg == 0) { 130 ss = sg->sg_segs; 131 ss->ss_paddr = paddr; 132 ss->ss_len = seglen; 133 sg->sg_nseg = 1; 134 } else { 135 ss = &sg->sg_segs[sg->sg_nseg - 1]; 136 error = _sglist_append_range(sg, &ss, paddr, seglen); 137 if (error) 138 return (error); 139 } 140 vaddr += seglen; 141 len -= seglen; 142 if (donep) 143 *donep += seglen; 144 145 while (len > 0) { 146 seglen = MIN(len, PAGE_SIZE); 147 if (pmap != NULL) 148 paddr = pmap_extract(pmap, vaddr); 149 else 150 paddr = pmap_kextract(vaddr); 151 error = _sglist_append_range(sg, &ss, paddr, seglen); 152 if (error) 153 return (error); 154 vaddr += seglen; 155 len -= seglen; 156 if (donep) 157 *donep += seglen; 158 } 159 160 return (0); 161 } 162 163 /* 164 * Determine the number of scatter/gather list elements needed to 165 * describe a kernel virtual address range. 166 */ 167 int 168 sglist_count(void *buf, size_t len) 169 { 170 vm_offset_t vaddr, vendaddr; 171 vm_paddr_t lastaddr, paddr; 172 int nsegs; 173 174 if (len == 0) 175 return (0); 176 177 vaddr = trunc_page((vm_offset_t)buf); 178 vendaddr = (vm_offset_t)buf + len; 179 nsegs = 1; 180 lastaddr = pmap_kextract(vaddr); 181 vaddr += PAGE_SIZE; 182 while (vaddr < vendaddr) { 183 paddr = pmap_kextract(vaddr); 184 if (lastaddr + PAGE_SIZE != paddr) 185 nsegs++; 186 lastaddr = paddr; 187 vaddr += PAGE_SIZE; 188 } 189 return (nsegs); 190 } 191 192 /* 193 * Allocate a scatter/gather list along with 'nsegs' segments. The 194 * 'mflags' parameters are the same as passed to kmalloc(9). The caller 195 * should use sglist_free() to free this list. 196 */ 197 struct sglist * 198 sglist_alloc(int nsegs, int mflags) 199 { 200 struct sglist *sg; 201 202 sg = kmalloc(sizeof(struct sglist) + nsegs * sizeof(struct sglist_seg), 203 M_SGLIST, mflags); 204 if (sg == NULL) 205 return (NULL); 206 sglist_init(sg, nsegs, (struct sglist_seg *)(sg + 1)); 207 return (sg); 208 } 209 210 /* 211 * Free a scatter/gather list allocated via sglist_allc(). 212 */ 213 void 214 sglist_free(struct sglist *sg) 215 { 216 217 if (refcount_release(&sg->sg_refs)) 218 kfree(sg, M_SGLIST); 219 } 220 221 /* 222 * Append the segments to describe a single kernel virtual address 223 * range to a scatter/gather list. If there are insufficient 224 * segments, then this fails with EFBIG. 225 */ 226 int 227 sglist_append(struct sglist *sg, void *buf, size_t len) 228 { 229 struct sgsave save; 230 int error; 231 232 if (sg->sg_maxseg == 0) 233 return (EINVAL); 234 SGLIST_SAVE(sg, save); 235 error = _sglist_append_buf(sg, buf, len, NULL, NULL); 236 if (error) 237 SGLIST_RESTORE(sg, save); 238 return (error); 239 } 240 241 /* 242 * Append a single physical address range to a scatter/gather list. 243 * If there are insufficient segments, then this fails with EFBIG. 244 */ 245 int 246 sglist_append_phys(struct sglist *sg, vm_paddr_t paddr, size_t len) 247 { 248 struct sglist_seg *ss; 249 struct sgsave save; 250 int error; 251 252 if (sg->sg_maxseg == 0) 253 return (EINVAL); 254 if (len == 0) 255 return (0); 256 257 if (sg->sg_nseg == 0) { 258 sg->sg_segs[0].ss_paddr = paddr; 259 sg->sg_segs[0].ss_len = len; 260 sg->sg_nseg = 1; 261 return (0); 262 } 263 ss = &sg->sg_segs[sg->sg_nseg - 1]; 264 SGLIST_SAVE(sg, save); 265 error = _sglist_append_range(sg, &ss, paddr, len); 266 if (error) 267 SGLIST_RESTORE(sg, save); 268 return (error); 269 } 270 271 /* 272 * Append the segments that describe a single mbuf chain to a 273 * scatter/gather list. If there are insufficient segments, then this 274 * fails with EFBIG. 275 */ 276 int 277 sglist_append_mbuf(struct sglist *sg, struct mbuf *m0) 278 { 279 struct sgsave save; 280 struct mbuf *m; 281 int error; 282 283 if (sg->sg_maxseg == 0) 284 return (EINVAL); 285 286 error = 0; 287 SGLIST_SAVE(sg, save); 288 for (m = m0; m != NULL; m = m->m_next) { 289 if (m->m_len > 0) { 290 error = sglist_append(sg, m->m_data, m->m_len); 291 if (error) { 292 SGLIST_RESTORE(sg, save); 293 return (error); 294 } 295 } 296 } 297 return (0); 298 } 299 300 /* 301 * Append the segments that describe a single user address range to a 302 * scatter/gather list. If there are insufficient segments, then this 303 * fails with EFBIG. 304 */ 305 int 306 sglist_append_user(struct sglist *sg, void *buf, size_t len, struct thread *td) 307 { 308 struct sgsave save; 309 int error; 310 311 if (sg->sg_maxseg == 0) 312 return (EINVAL); 313 SGLIST_SAVE(sg, save); 314 error = _sglist_append_buf(sg, buf, len, 315 vmspace_pmap(td->td_proc->p_vmspace), NULL); 316 if (error) 317 SGLIST_RESTORE(sg, save); 318 return (error); 319 } 320 321 /* 322 * Append the segments that describe a single uio to a scatter/gather 323 * list. If there are insufficient segments, then this fails with 324 * EFBIG. 325 */ 326 int 327 sglist_append_uio(struct sglist *sg, struct uio *uio) 328 { 329 struct iovec *iov; 330 struct sgsave save; 331 size_t resid, minlen; 332 pmap_t pmap; 333 int error, i; 334 335 if (sg->sg_maxseg == 0) 336 return (EINVAL); 337 338 resid = uio->uio_resid; 339 iov = uio->uio_iov; 340 341 if (uio->uio_segflg == UIO_USERSPACE) { 342 KASSERT(uio->uio_td != NULL, 343 ("sglist_append_uio: USERSPACE but no thread")); 344 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace); 345 } else 346 pmap = NULL; 347 348 error = 0; 349 SGLIST_SAVE(sg, save); 350 for (i = 0; i < uio->uio_iovcnt && resid != 0; i++) { 351 /* 352 * Now at the first iovec to load. Load each iovec 353 * until we have exhausted the residual count. 354 */ 355 minlen = MIN(resid, iov[i].iov_len); 356 if (minlen > 0) { 357 error = _sglist_append_buf(sg, iov[i].iov_base, minlen, 358 pmap, NULL); 359 if (error) { 360 SGLIST_RESTORE(sg, save); 361 return (error); 362 } 363 resid -= minlen; 364 } 365 } 366 return (0); 367 } 368 369 /* 370 * Append the segments that describe at most 'resid' bytes from a 371 * single uio to a scatter/gather list. If there are insufficient 372 * segments, then only the amount that fits is appended. 373 */ 374 int 375 sglist_consume_uio(struct sglist *sg, struct uio *uio, size_t resid) 376 { 377 struct iovec *iov; 378 size_t done; 379 pmap_t pmap; 380 int error, len; 381 382 if (sg->sg_maxseg == 0) 383 return (EINVAL); 384 385 if (uio->uio_segflg == UIO_USERSPACE) { 386 KASSERT(uio->uio_td != NULL, 387 ("sglist_consume_uio: USERSPACE but no thread")); 388 pmap = vmspace_pmap(uio->uio_td->td_proc->p_vmspace); 389 } else 390 pmap = NULL; 391 392 error = 0; 393 while (resid > 0 && uio->uio_resid) { 394 iov = uio->uio_iov; 395 len = iov->iov_len; 396 if (len == 0) { 397 uio->uio_iov++; 398 uio->uio_iovcnt--; 399 continue; 400 } 401 if (len > resid) 402 len = resid; 403 404 /* 405 * Try to append this iovec. If we run out of room, 406 * then break out of the loop. 407 */ 408 error = _sglist_append_buf(sg, iov->iov_base, len, pmap, &done); 409 iov->iov_base = (char *)iov->iov_base + done; 410 iov->iov_len -= done; 411 uio->uio_resid -= done; 412 uio->uio_offset += done; 413 resid -= done; 414 if (error) 415 break; 416 } 417 return (0); 418 } 419 420 /* 421 * Allocate and populate a scatter/gather list to describe a single 422 * kernel virtual address range. 423 */ 424 struct sglist * 425 sglist_build(void *buf, size_t len, int mflags) 426 { 427 struct sglist *sg; 428 int nsegs; 429 430 if (len == 0) 431 return (NULL); 432 433 nsegs = sglist_count(buf, len); 434 sg = sglist_alloc(nsegs, mflags); 435 if (sg == NULL) 436 return (NULL); 437 if (sglist_append(sg, buf, len) != 0) { 438 sglist_free(sg); 439 return (NULL); 440 } 441 return (sg); 442 } 443 444 /* 445 * Clone a new copy of a scatter/gather list. 446 */ 447 struct sglist * 448 sglist_clone(struct sglist *sg, int mflags) 449 { 450 struct sglist *new; 451 452 if (sg == NULL) 453 return (NULL); 454 new = sglist_alloc(sg->sg_maxseg, mflags); 455 if (new == NULL) 456 return (NULL); 457 new->sg_nseg = sg->sg_nseg; 458 bcopy(sg->sg_segs, new->sg_segs, sizeof(struct sglist_seg) * 459 sg->sg_nseg); 460 return (new); 461 } 462 463 /* 464 * Calculate the total length of the segments described in a 465 * scatter/gather list. 466 */ 467 size_t 468 sglist_length(struct sglist *sg) 469 { 470 size_t space; 471 int i; 472 473 space = 0; 474 for (i = 0; i < sg->sg_nseg; i++) 475 space += sg->sg_segs[i].ss_len; 476 return (space); 477 } 478 479 /* 480 * Split a scatter/gather list into two lists. The scatter/gather 481 * entries for the first 'length' bytes of the 'original' list are 482 * stored in the '*head' list and are removed from 'original'. 483 * 484 * If '*head' is NULL, then a new list will be allocated using 485 * 'mflags'. If M_NOWAIT is specified and the allocation fails, 486 * ENOMEM will be returned. 487 * 488 * If '*head' is not NULL, it should point to an empty sglist. If it 489 * does not have enough room for the remaining space, then EFBIG will 490 * be returned. If '*head' is not empty, then EINVAL will be 491 * returned. 492 * 493 * If 'original' is shared (refcount > 1), then EDOOFUS will be 494 * returned. 495 */ 496 int 497 sglist_split(struct sglist *original, struct sglist **head, size_t length, 498 int mflags) 499 { 500 struct sglist *sg; 501 size_t space, split; 502 int count, i; 503 504 if (original->sg_refs > 1) 505 return (EDOOFUS); 506 507 /* Figure out how big of a sglist '*head' has to hold. */ 508 count = 0; 509 space = 0; 510 split = 0; 511 for (i = 0; i < original->sg_nseg; i++) { 512 space += original->sg_segs[i].ss_len; 513 count++; 514 if (space >= length) { 515 /* 516 * If 'length' falls in the middle of a 517 * scatter/gather list entry, then 'split' 518 * holds how much of that entry will remain in 519 * 'original'. 520 */ 521 split = space - length; 522 break; 523 } 524 } 525 526 /* Nothing to do, so leave head empty. */ 527 if (count == 0) 528 return (0); 529 530 if (*head == NULL) { 531 sg = sglist_alloc(count, mflags); 532 if (sg == NULL) 533 return (ENOMEM); 534 *head = sg; 535 } else { 536 sg = *head; 537 if (sg->sg_maxseg < count) 538 return (EFBIG); 539 if (sg->sg_nseg != 0) 540 return (EINVAL); 541 } 542 543 /* Copy 'count' entries to 'sg' from 'original'. */ 544 bcopy(original->sg_segs, sg->sg_segs, count * 545 sizeof(struct sglist_seg)); 546 sg->sg_nseg = count; 547 548 /* 549 * If we had to split a list entry, fixup the last entry in 550 * 'sg' and the new first entry in 'original'. We also 551 * decrement 'count' by 1 since we will only be removing 552 * 'count - 1' segments from 'original' now. 553 */ 554 if (split != 0) { 555 count--; 556 sg->sg_segs[count].ss_len -= split; 557 original->sg_segs[count].ss_paddr = 558 sg->sg_segs[count].ss_paddr + split; 559 original->sg_segs[count].ss_len = split; 560 } 561 562 /* Trim 'count' entries from the front of 'original'. */ 563 original->sg_nseg -= count; 564 bcopy(original->sg_segs + count, original->sg_segs, count * 565 sizeof(struct sglist_seg)); 566 return (0); 567 } 568 569 /* 570 * Append the scatter/gather list elements in 'second' to the 571 * scatter/gather list 'first'. If there is not enough space in 572 * 'first', EFBIG is returned. 573 */ 574 int 575 sglist_join(struct sglist *first, struct sglist *second) 576 { 577 struct sglist_seg *flast, *sfirst; 578 int append; 579 580 /* If 'second' is empty, there is nothing to do. */ 581 if (second->sg_nseg == 0) 582 return (0); 583 584 /* 585 * If the first entry in 'second' can be appended to the last entry 586 * in 'first' then set append to '1'. 587 */ 588 append = 0; 589 flast = &first->sg_segs[first->sg_nseg - 1]; 590 sfirst = &second->sg_segs[0]; 591 if (first->sg_nseg != 0 && 592 flast->ss_paddr + flast->ss_len == sfirst->ss_paddr) 593 append = 1; 594 595 /* Make sure 'first' has enough room. */ 596 if (first->sg_nseg + second->sg_nseg - append > first->sg_maxseg) 597 return (EFBIG); 598 599 /* Merge last in 'first' and first in 'second' if needed. */ 600 if (append) 601 flast->ss_len += sfirst->ss_len; 602 603 /* Append new segments from 'second' to 'first'. */ 604 bcopy(first->sg_segs + first->sg_nseg, second->sg_segs + append, 605 (second->sg_nseg - append) * sizeof(struct sglist_seg)); 606 first->sg_nseg += second->sg_nseg - append; 607 sglist_reset(second); 608 return (0); 609 } 610 611 /* 612 * Generate a new scatter/gather list from a range of an existing 613 * scatter/gather list. The 'offset' and 'length' parameters specify 614 * the logical range of the 'original' list to extract. If that range 615 * is not a subset of the length of 'original', then EINVAL is 616 * returned. The new scatter/gather list is stored in '*slice'. 617 * 618 * If '*slice' is NULL, then a new list will be allocated using 619 * 'mflags'. If M_NOWAIT is specified and the allocation fails, 620 * ENOMEM will be returned. 621 * 622 * If '*slice' is not NULL, it should point to an empty sglist. If it 623 * does not have enough room for the remaining space, then EFBIG will 624 * be returned. If '*slice' is not empty, then EINVAL will be 625 * returned. 626 */ 627 int 628 sglist_slice(struct sglist *original, struct sglist **slice, size_t offset, 629 size_t length, int mflags) 630 { 631 struct sglist *sg; 632 size_t space, end, foffs, loffs; 633 int count, i, fseg; 634 635 /* Nothing to do. */ 636 if (length == 0) 637 return (0); 638 639 /* Figure out how many segments '*slice' needs to have. */ 640 end = offset + length; 641 space = 0; 642 count = 0; 643 fseg = 0; 644 foffs = loffs = 0; 645 for (i = 0; i < original->sg_nseg; i++) { 646 space += original->sg_segs[i].ss_len; 647 if (space > offset) { 648 /* 649 * When we hit the first segment, store its index 650 * in 'fseg' and the offset into the first segment 651 * of 'offset' in 'foffs'. 652 */ 653 if (count == 0) { 654 fseg = i; 655 foffs = offset - (space - 656 original->sg_segs[i].ss_len); 657 } 658 count++; 659 660 /* 661 * When we hit the last segment, break out of 662 * the loop. Store the amount of extra space 663 * at the end of this segment in 'loffs'. 664 */ 665 if (space >= end) { 666 loffs = space - end; 667 break; 668 } 669 } 670 } 671 672 /* If we never hit 'end', then 'length' ran off the end, so fail. */ 673 if (space < end) 674 return (EINVAL); 675 676 if (*slice == NULL) { 677 sg = sglist_alloc(count, mflags); 678 if (sg == NULL) 679 return (ENOMEM); 680 *slice = sg; 681 } else { 682 sg = *slice; 683 if (sg->sg_maxseg < count) 684 return (EFBIG); 685 if (sg->sg_nseg != 0) 686 return (EINVAL); 687 } 688 689 /* 690 * Copy over 'count' segments from 'original' starting at 691 * 'fseg' to 'sg'. 692 */ 693 bcopy(original->sg_segs + fseg, sg->sg_segs, 694 count * sizeof(struct sglist_seg)); 695 sg->sg_nseg = count; 696 697 /* Fixup first and last segments if needed. */ 698 if (foffs != 0) { 699 sg->sg_segs[0].ss_paddr += foffs; 700 sg->sg_segs[0].ss_len -= foffs; 701 } 702 if (loffs != 0) { 703 sg->sg_segs[count - 1].ss_len -= loffs; 704 } 705 return (0); 706 } 707