1 /* 2 * Copyright (c) 1994, David Greenman 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice unmodified, this list of conditions, and the following 10 * 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 * 15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 25 * SUCH DAMAGE. 26 * 27 * $FreeBSD: src/sys/kern/tty_subr.c,v 1.32 1999/08/28 00:46:21 peter Exp $ 28 * $DragonFly: src/sys/kern/tty_subr.c,v 1.4 2004/01/08 18:39:18 asmodai Exp $ 29 */ 30 31 /* 32 * clist support routines 33 */ 34 35 #include <sys/param.h> 36 #include <sys/kernel.h> 37 #include <sys/systm.h> 38 #include <sys/malloc.h> 39 #include <sys/tty.h> 40 #include <sys/clist.h> 41 42 static void clist_init (void *); 43 SYSINIT(clist, SI_SUB_CLIST, SI_ORDER_FIRST, clist_init, NULL) 44 45 static struct cblock *cfreelist = 0; 46 int cfreecount = 0; 47 static int cslushcount; 48 static int ctotcount; 49 50 #ifndef INITIAL_CBLOCKS 51 #define INITIAL_CBLOCKS 50 52 #endif 53 54 static struct cblock *cblock_alloc (void); 55 static void cblock_alloc_cblocks (int number); 56 static void cblock_free (struct cblock *cblockp); 57 static void cblock_free_cblocks (int number); 58 59 #include "opt_ddb.h" 60 #ifdef DDB 61 #include <ddb/ddb.h> 62 63 DB_SHOW_COMMAND(cbstat, cbstat) 64 { 65 int cbsize = CBSIZE; 66 67 printf( 68 "tot = %d (active = %d, free = %d (reserved = %d, slush = %d))\n", 69 ctotcount * cbsize, ctotcount * cbsize - cfreecount, cfreecount, 70 cfreecount - cslushcount * cbsize, cslushcount * cbsize); 71 } 72 #endif /* DDB */ 73 74 /* 75 * Called from init_main.c 76 */ 77 /* ARGSUSED*/ 78 static void 79 clist_init(dummy) 80 void *dummy; 81 { 82 /* 83 * Allocate an initial base set of cblocks as a 'slush'. 84 * We allocate non-slush cblocks with each initial ttyopen() and 85 * deallocate them with each ttyclose(). 86 * We should adjust the slush allocation. This can't be done in 87 * the i/o routines because they are sometimes called from 88 * interrupt handlers when it may be unsafe to call malloc(). 89 */ 90 cblock_alloc_cblocks(cslushcount = INITIAL_CBLOCKS); 91 } 92 93 /* 94 * Remove a cblock from the cfreelist queue and return a pointer 95 * to it. 96 */ 97 static __inline struct cblock * 98 cblock_alloc() 99 { 100 struct cblock *cblockp; 101 102 cblockp = cfreelist; 103 if (cblockp == NULL) 104 panic("clist reservation botch"); 105 cfreelist = cblockp->c_next; 106 cblockp->c_next = NULL; 107 cfreecount -= CBSIZE; 108 return (cblockp); 109 } 110 111 /* 112 * Add a cblock to the cfreelist queue. 113 */ 114 static __inline void 115 cblock_free(cblockp) 116 struct cblock *cblockp; 117 { 118 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1)) 119 bzero(cblockp->c_quote, sizeof cblockp->c_quote); 120 cblockp->c_next = cfreelist; 121 cfreelist = cblockp; 122 cfreecount += CBSIZE; 123 } 124 125 /* 126 * Allocate some cblocks for the cfreelist queue. 127 */ 128 static void 129 cblock_alloc_cblocks(number) 130 int number; 131 { 132 int i; 133 struct cblock *cbp; 134 135 for (i = 0; i < number; ++i) { 136 cbp = malloc(sizeof *cbp, M_TTYS, M_NOWAIT); 137 if (cbp == NULL) { 138 printf( 139 "clist_alloc_cblocks: M_NOWAIT malloc failed, trying M_WAITOK\n"); 140 cbp = malloc(sizeof *cbp, M_TTYS, M_WAITOK); 141 } 142 /* 143 * Freed cblocks have zero quotes and garbage elsewhere. 144 * Set the may-have-quote bit to force zeroing the quotes. 145 */ 146 setbit(cbp->c_quote, CBQSIZE * NBBY - 1); 147 cblock_free(cbp); 148 } 149 ctotcount += number; 150 } 151 152 /* 153 * Set the cblock allocation policy for a a clist. 154 * Must be called in process context at spltty(). 155 */ 156 void 157 clist_alloc_cblocks(clistp, ccmax, ccreserved) 158 struct clist *clistp; 159 int ccmax; 160 int ccreserved; 161 { 162 int dcbr; 163 164 /* 165 * Allow for wasted space at the head. 166 */ 167 if (ccmax != 0) 168 ccmax += CBSIZE - 1; 169 if (ccreserved != 0) 170 ccreserved += CBSIZE - 1; 171 172 clistp->c_cbmax = roundup(ccmax, CBSIZE) / CBSIZE; 173 dcbr = roundup(ccreserved, CBSIZE) / CBSIZE - clistp->c_cbreserved; 174 if (dcbr >= 0) 175 cblock_alloc_cblocks(dcbr); 176 else { 177 if (clistp->c_cbreserved + dcbr < clistp->c_cbcount) 178 dcbr = clistp->c_cbcount - clistp->c_cbreserved; 179 cblock_free_cblocks(-dcbr); 180 } 181 clistp->c_cbreserved += dcbr; 182 } 183 184 /* 185 * Free some cblocks from the cfreelist queue back to the 186 * system malloc pool. 187 */ 188 static void 189 cblock_free_cblocks(number) 190 int number; 191 { 192 int i; 193 194 for (i = 0; i < number; ++i) 195 free(cblock_alloc(), M_TTYS); 196 ctotcount -= number; 197 } 198 199 /* 200 * Free the cblocks reserved for a clist. 201 * Must be called at spltty(). 202 */ 203 void 204 clist_free_cblocks(clistp) 205 struct clist *clistp; 206 { 207 if (clistp->c_cbcount != 0) 208 panic("freeing active clist cblocks"); 209 cblock_free_cblocks(clistp->c_cbreserved); 210 clistp->c_cbmax = 0; 211 clistp->c_cbreserved = 0; 212 } 213 214 /* 215 * Get a character from the head of a clist. 216 */ 217 int 218 getc(clistp) 219 struct clist *clistp; 220 { 221 int chr = -1; 222 int s; 223 struct cblock *cblockp; 224 225 s = spltty(); 226 227 /* If there are characters in the list, get one */ 228 if (clistp->c_cc) { 229 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND); 230 chr = (u_char)*clistp->c_cf; 231 232 /* 233 * If this char is quoted, set the flag. 234 */ 235 if (isset(cblockp->c_quote, clistp->c_cf - (char *)cblockp->c_info)) 236 chr |= TTY_QUOTE; 237 238 /* 239 * Advance to next character. 240 */ 241 clistp->c_cf++; 242 clistp->c_cc--; 243 /* 244 * If we have advanced the 'first' character pointer 245 * past the end of this cblock, advance to the next one. 246 * If there are no more characters, set the first and 247 * last pointers to NULL. In either case, free the 248 * current cblock. 249 */ 250 if ((clistp->c_cf >= (char *)(cblockp+1)) || (clistp->c_cc == 0)) { 251 if (clistp->c_cc > 0) { 252 clistp->c_cf = cblockp->c_next->c_info; 253 } else { 254 clistp->c_cf = clistp->c_cl = NULL; 255 } 256 cblock_free(cblockp); 257 if (--clistp->c_cbcount >= clistp->c_cbreserved) 258 ++cslushcount; 259 } 260 } 261 262 splx(s); 263 return (chr); 264 } 265 266 /* 267 * Copy 'amount' of chars, beginning at head of clist 'clistp' to 268 * destination linear buffer 'dest'. Return number of characters 269 * actually copied. 270 */ 271 int 272 q_to_b(clistp, dest, amount) 273 struct clist *clistp; 274 char *dest; 275 int amount; 276 { 277 struct cblock *cblockp; 278 struct cblock *cblockn; 279 char *dest_orig = dest; 280 int numc; 281 int s; 282 283 s = spltty(); 284 285 while (clistp && amount && (clistp->c_cc > 0)) { 286 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND); 287 cblockn = cblockp + 1; /* pointer arithmetic! */ 288 numc = min(amount, (char *)cblockn - clistp->c_cf); 289 numc = min(numc, clistp->c_cc); 290 bcopy(clistp->c_cf, dest, numc); 291 amount -= numc; 292 clistp->c_cf += numc; 293 clistp->c_cc -= numc; 294 dest += numc; 295 /* 296 * If this cblock has been emptied, advance to the next 297 * one. If there are no more characters, set the first 298 * and last pointer to NULL. In either case, free the 299 * current cblock. 300 */ 301 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) { 302 if (clistp->c_cc > 0) { 303 clistp->c_cf = cblockp->c_next->c_info; 304 } else { 305 clistp->c_cf = clistp->c_cl = NULL; 306 } 307 cblock_free(cblockp); 308 if (--clistp->c_cbcount >= clistp->c_cbreserved) 309 ++cslushcount; 310 } 311 } 312 313 splx(s); 314 return (dest - dest_orig); 315 } 316 317 /* 318 * Flush 'amount' of chars, beginning at head of clist 'clistp'. 319 */ 320 void 321 ndflush(clistp, amount) 322 struct clist *clistp; 323 int amount; 324 { 325 struct cblock *cblockp; 326 struct cblock *cblockn; 327 int numc; 328 int s; 329 330 s = spltty(); 331 332 while (amount && (clistp->c_cc > 0)) { 333 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND); 334 cblockn = cblockp + 1; /* pointer arithmetic! */ 335 numc = min(amount, (char *)cblockn - clistp->c_cf); 336 numc = min(numc, clistp->c_cc); 337 amount -= numc; 338 clistp->c_cf += numc; 339 clistp->c_cc -= numc; 340 /* 341 * If this cblock has been emptied, advance to the next 342 * one. If there are no more characters, set the first 343 * and last pointer to NULL. In either case, free the 344 * current cblock. 345 */ 346 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) { 347 if (clistp->c_cc > 0) { 348 clistp->c_cf = cblockp->c_next->c_info; 349 } else { 350 clistp->c_cf = clistp->c_cl = NULL; 351 } 352 cblock_free(cblockp); 353 if (--clistp->c_cbcount >= clistp->c_cbreserved) 354 ++cslushcount; 355 } 356 } 357 358 splx(s); 359 } 360 361 /* 362 * Add a character to the end of a clist. Return -1 is no 363 * more clists, or 0 for success. 364 */ 365 int 366 putc(chr, clistp) 367 int chr; 368 struct clist *clistp; 369 { 370 struct cblock *cblockp; 371 int s; 372 373 s = spltty(); 374 375 if (clistp->c_cl == NULL) { 376 if (clistp->c_cbreserved < 1) { 377 splx(s); 378 printf("putc to a clist with no reserved cblocks\n"); 379 return (-1); /* nothing done */ 380 } 381 cblockp = cblock_alloc(); 382 clistp->c_cbcount = 1; 383 clistp->c_cf = clistp->c_cl = cblockp->c_info; 384 clistp->c_cc = 0; 385 } else { 386 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND); 387 if (((intptr_t)clistp->c_cl & CROUND) == 0) { 388 struct cblock *prev = (cblockp - 1); 389 390 if (clistp->c_cbcount >= clistp->c_cbreserved) { 391 if (clistp->c_cbcount >= clistp->c_cbmax 392 || cslushcount <= 0) { 393 splx(s); 394 return (-1); 395 } 396 --cslushcount; 397 } 398 cblockp = cblock_alloc(); 399 clistp->c_cbcount++; 400 prev->c_next = cblockp; 401 clistp->c_cl = cblockp->c_info; 402 } 403 } 404 405 /* 406 * If this character is quoted, set the quote bit, if not, clear it. 407 */ 408 if (chr & TTY_QUOTE) { 409 setbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info); 410 /* 411 * Use one of the spare quote bits to record that something 412 * may be quoted. 413 */ 414 setbit(cblockp->c_quote, CBQSIZE * NBBY - 1); 415 } else 416 clrbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info); 417 418 *clistp->c_cl++ = chr; 419 clistp->c_cc++; 420 421 splx(s); 422 return (0); 423 } 424 425 /* 426 * Copy data from linear buffer to clist chain. Return the 427 * number of characters not copied. 428 */ 429 int 430 b_to_q(src, amount, clistp) 431 char *src; 432 int amount; 433 struct clist *clistp; 434 { 435 struct cblock *cblockp; 436 char *firstbyte, *lastbyte; 437 u_char startmask, endmask; 438 int startbit, endbit, num_between, numc; 439 int s; 440 441 /* 442 * Avoid allocating an initial cblock and then not using it. 443 * c_cc == 0 must imply c_cbount == 0. 444 */ 445 if (amount <= 0) 446 return (amount); 447 448 s = spltty(); 449 450 /* 451 * If there are no cblocks assigned to this clist yet, 452 * then get one. 453 */ 454 if (clistp->c_cl == NULL) { 455 if (clistp->c_cbreserved < 1) { 456 splx(s); 457 printf("b_to_q to a clist with no reserved cblocks.\n"); 458 return (amount); /* nothing done */ 459 } 460 cblockp = cblock_alloc(); 461 clistp->c_cbcount = 1; 462 clistp->c_cf = clistp->c_cl = cblockp->c_info; 463 clistp->c_cc = 0; 464 } else { 465 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND); 466 } 467 468 while (amount) { 469 /* 470 * Get another cblock if needed. 471 */ 472 if (((intptr_t)clistp->c_cl & CROUND) == 0) { 473 struct cblock *prev = cblockp - 1; 474 475 if (clistp->c_cbcount >= clistp->c_cbreserved) { 476 if (clistp->c_cbcount >= clistp->c_cbmax 477 || cslushcount <= 0) { 478 splx(s); 479 return (amount); 480 } 481 --cslushcount; 482 } 483 cblockp = cblock_alloc(); 484 clistp->c_cbcount++; 485 prev->c_next = cblockp; 486 clistp->c_cl = cblockp->c_info; 487 } 488 489 /* 490 * Copy a chunk of the linear buffer up to the end 491 * of this cblock. 492 */ 493 numc = min(amount, (char *)(cblockp + 1) - clistp->c_cl); 494 bcopy(src, clistp->c_cl, numc); 495 496 /* 497 * Clear quote bits if they aren't known to be clear. 498 * The following could probably be made into a separate 499 * "bitzero()" routine, but why bother? 500 */ 501 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1)) { 502 startbit = clistp->c_cl - (char *)cblockp->c_info; 503 endbit = startbit + numc - 1; 504 505 firstbyte = (u_char *)cblockp->c_quote + (startbit / NBBY); 506 lastbyte = (u_char *)cblockp->c_quote + (endbit / NBBY); 507 508 /* 509 * Calculate mask of bits to preserve in first and 510 * last bytes. 511 */ 512 startmask = NBBY - (startbit % NBBY); 513 startmask = 0xff >> startmask; 514 endmask = (endbit % NBBY); 515 endmask = 0xff << (endmask + 1); 516 517 if (firstbyte != lastbyte) { 518 *firstbyte &= startmask; 519 *lastbyte &= endmask; 520 521 num_between = lastbyte - firstbyte - 1; 522 if (num_between) 523 bzero(firstbyte + 1, num_between); 524 } else { 525 *firstbyte &= (startmask | endmask); 526 } 527 } 528 529 /* 530 * ...and update pointer for the next chunk. 531 */ 532 src += numc; 533 clistp->c_cl += numc; 534 clistp->c_cc += numc; 535 amount -= numc; 536 /* 537 * If we go through the loop again, it's always 538 * for data in the next cblock, so by adding one (cblock), 539 * (which makes the pointer 1 beyond the end of this 540 * cblock) we prepare for the assignment of 'prev' 541 * above. 542 */ 543 cblockp += 1; 544 545 } 546 547 splx(s); 548 return (amount); 549 } 550 551 /* 552 * Get the next character in the clist. Store it at dst. Don't 553 * advance any clist pointers, but return a pointer to the next 554 * character position. 555 */ 556 char * 557 nextc(clistp, cp, dst) 558 struct clist *clistp; 559 char *cp; 560 int *dst; 561 { 562 struct cblock *cblockp; 563 564 ++cp; 565 /* 566 * See if the next character is beyond the end of 567 * the clist. 568 */ 569 if (clistp->c_cc && (cp != clistp->c_cl)) { 570 /* 571 * If the next character is beyond the end of this 572 * cblock, advance to the next cblock. 573 */ 574 if (((intptr_t)cp & CROUND) == 0) 575 cp = ((struct cblock *)cp - 1)->c_next->c_info; 576 cblockp = (struct cblock *)((intptr_t)cp & ~CROUND); 577 578 /* 579 * Get the character. Set the quote flag if this character 580 * is quoted. 581 */ 582 *dst = (u_char)*cp | (isset(cblockp->c_quote, cp - (char *)cblockp->c_info) ? TTY_QUOTE : 0); 583 584 return (cp); 585 } 586 587 return (NULL); 588 } 589 590 /* 591 * "Unput" a character from a clist. 592 */ 593 int 594 unputc(clistp) 595 struct clist *clistp; 596 { 597 struct cblock *cblockp = 0, *cbp = 0; 598 int s; 599 int chr = -1; 600 601 602 s = spltty(); 603 604 if (clistp->c_cc) { 605 --clistp->c_cc; 606 --clistp->c_cl; 607 608 chr = (u_char)*clistp->c_cl; 609 610 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND); 611 612 /* 613 * Set quote flag if this character was quoted. 614 */ 615 if (isset(cblockp->c_quote, (u_char *)clistp->c_cl - cblockp->c_info)) 616 chr |= TTY_QUOTE; 617 618 /* 619 * If all of the characters have been unput in this 620 * cblock, then find the previous one and free this 621 * one. 622 */ 623 if (clistp->c_cc && (clistp->c_cl <= (char *)cblockp->c_info)) { 624 cbp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND); 625 626 while (cbp->c_next != cblockp) 627 cbp = cbp->c_next; 628 629 /* 630 * When the previous cblock is at the end, the 'last' 631 * pointer always points (invalidly) one past. 632 */ 633 clistp->c_cl = (char *)(cbp+1); 634 cblock_free(cblockp); 635 if (--clistp->c_cbcount >= clistp->c_cbreserved) 636 ++cslushcount; 637 cbp->c_next = NULL; 638 } 639 } 640 641 /* 642 * If there are no more characters on the list, then 643 * free the last cblock. 644 */ 645 if ((clistp->c_cc == 0) && clistp->c_cl) { 646 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND); 647 cblock_free(cblockp); 648 if (--clistp->c_cbcount >= clistp->c_cbreserved) 649 ++cslushcount; 650 clistp->c_cf = clistp->c_cl = NULL; 651 } 652 653 splx(s); 654 return (chr); 655 } 656 657 /* 658 * Move characters in source clist to destination clist, 659 * preserving quote bits. 660 */ 661 void 662 catq(src_clistp, dest_clistp) 663 struct clist *src_clistp, *dest_clistp; 664 { 665 int chr, s; 666 667 s = spltty(); 668 /* 669 * If the destination clist is empty (has no cblocks atttached), 670 * and there are no possible complications with the resource counters, 671 * then we simply assign the current clist to the destination. 672 */ 673 if (!dest_clistp->c_cf 674 && src_clistp->c_cbcount <= src_clistp->c_cbmax 675 && src_clistp->c_cbcount <= dest_clistp->c_cbmax) { 676 dest_clistp->c_cf = src_clistp->c_cf; 677 dest_clistp->c_cl = src_clistp->c_cl; 678 src_clistp->c_cf = src_clistp->c_cl = NULL; 679 680 dest_clistp->c_cc = src_clistp->c_cc; 681 src_clistp->c_cc = 0; 682 dest_clistp->c_cbcount = src_clistp->c_cbcount; 683 src_clistp->c_cbcount = 0; 684 685 splx(s); 686 return; 687 } 688 689 splx(s); 690 691 /* 692 * XXX This should probably be optimized to more than one 693 * character at a time. 694 */ 695 while ((chr = getc(src_clistp)) != -1) 696 putc(chr, dest_clistp); 697 } 698