1 /*- 2 * SPDX-License-Identifier: BSD-2-Clause 3 * 4 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org> 5 * All rights reserved. 6 * 7 * Portions of this software were developed under sponsorship from Snow 8 * B.V., the Netherlands. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 20 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 22 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 23 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 24 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 25 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 27 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 28 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 29 * SUCH DAMAGE. 30 */ 31 32 #include <sys/param.h> 33 #include <sys/kernel.h> 34 #include <sys/lock.h> 35 #include <sys/queue.h> 36 #include <sys/sysctl.h> 37 #include <sys/systm.h> 38 #include <sys/tty.h> 39 #include <sys/uio.h> 40 41 #include <vm/uma.h> 42 43 /* 44 * TTY input queue buffering. 45 * 46 * Unlike the output queue, the input queue has more features that are 47 * needed to properly implement various features offered by the TTY 48 * interface: 49 * 50 * - Data can be removed from the tail of the queue, which is used to 51 * implement backspace. 52 * - Once in a while, input has to be `canonicalized'. When ICANON is 53 * turned on, this will be done after a CR has been inserted. 54 * Otherwise, it should be done after any character has been inserted. 55 * - The input queue can store one bit per byte, called the quoting bit. 56 * This bit is used by TTYDISC to make backspace work on quoted 57 * characters. 58 * 59 * In most cases, there is probably less input than output, so unlike 60 * the outq, we'll stick to 128 byte blocks here. 61 */ 62 63 static int ttyinq_flush_secure = 1; 64 SYSCTL_INT(_kern, OID_AUTO, tty_inq_flush_secure, CTLFLAG_RW, 65 &ttyinq_flush_secure, 0, "Zero buffers while flushing"); 66 67 #define TTYINQ_QUOTESIZE (TTYINQ_DATASIZE / BMSIZE) 68 #define BMSIZE 32 69 #define GETBIT(tib,boff) \ 70 ((tib)->tib_quotes[(boff) / BMSIZE] & (1 << ((boff) % BMSIZE))) 71 #define SETBIT(tib,boff) \ 72 ((tib)->tib_quotes[(boff) / BMSIZE] |= (1 << ((boff) % BMSIZE))) 73 #define CLRBIT(tib,boff) \ 74 ((tib)->tib_quotes[(boff) / BMSIZE] &= ~(1 << ((boff) % BMSIZE))) 75 76 struct ttyinq_block { 77 struct ttyinq_block *tib_prev; 78 struct ttyinq_block *tib_next; 79 uint32_t tib_quotes[TTYINQ_QUOTESIZE]; 80 char tib_data[TTYINQ_DATASIZE]; 81 }; 82 83 static uma_zone_t ttyinq_zone; 84 85 #define TTYINQ_INSERT_TAIL(ti, tib) do { \ 86 if (ti->ti_end == 0) { \ 87 tib->tib_prev = NULL; \ 88 tib->tib_next = ti->ti_firstblock; \ 89 ti->ti_firstblock = tib; \ 90 } else { \ 91 tib->tib_prev = ti->ti_lastblock; \ 92 tib->tib_next = ti->ti_lastblock->tib_next; \ 93 ti->ti_lastblock->tib_next = tib; \ 94 } \ 95 if (tib->tib_next != NULL) \ 96 tib->tib_next->tib_prev = tib; \ 97 ti->ti_nblocks++; \ 98 } while (0) 99 100 #define TTYINQ_REMOVE_HEAD(ti) do { \ 101 ti->ti_firstblock = ti->ti_firstblock->tib_next; \ 102 if (ti->ti_firstblock != NULL) \ 103 ti->ti_firstblock->tib_prev = NULL; \ 104 ti->ti_nblocks--; \ 105 } while (0) 106 107 #define TTYINQ_RECYCLE(ti, tib) do { \ 108 if (ti->ti_quota <= ti->ti_nblocks) \ 109 uma_zfree(ttyinq_zone, tib); \ 110 else \ 111 TTYINQ_INSERT_TAIL(ti, tib); \ 112 } while (0) 113 114 int 115 ttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t size) 116 { 117 struct ttyinq_block *tib; 118 119 ti->ti_quota = howmany(size, TTYINQ_DATASIZE); 120 121 while (ti->ti_quota > ti->ti_nblocks) { 122 /* 123 * List is getting bigger. 124 * Add new blocks to the tail of the list. 125 * 126 * We must unlock the TTY temporarily, because we need 127 * to allocate memory. This won't be a problem, because 128 * in the worst case, another thread ends up here, which 129 * may cause us to allocate too many blocks, but this 130 * will be caught by the loop below. 131 */ 132 tty_unlock(tp); 133 tib = uma_zalloc(ttyinq_zone, M_WAITOK); 134 tty_lock(tp); 135 136 if (tty_gone(tp)) { 137 uma_zfree(ttyinq_zone, tib); 138 return (ENXIO); 139 } 140 141 TTYINQ_INSERT_TAIL(ti, tib); 142 } 143 return (0); 144 } 145 146 void 147 ttyinq_free(struct ttyinq *ti) 148 { 149 struct ttyinq_block *tib; 150 151 ttyinq_flush(ti); 152 ti->ti_quota = 0; 153 154 while ((tib = ti->ti_firstblock) != NULL) { 155 TTYINQ_REMOVE_HEAD(ti); 156 uma_zfree(ttyinq_zone, tib); 157 } 158 159 MPASS(ti->ti_nblocks == 0); 160 } 161 162 int 163 ttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio, 164 size_t rlen, size_t flen) 165 { 166 167 /* rlen includes flen, flen bytes will be trimmed from the end. */ 168 MPASS(rlen - flen <= uio->uio_resid); 169 170 while (rlen > 0) { 171 int error; 172 struct ttyinq_block *tib; 173 size_t cbegin, cend, clen; 174 175 /* See if there still is data. */ 176 if (ti->ti_begin == ti->ti_linestart) 177 return (0); 178 tib = ti->ti_firstblock; 179 if (tib == NULL) 180 return (0); 181 182 /* 183 * The end address should be the lowest of these three: 184 * - The write pointer 185 * - The blocksize - we can't read beyond the block 186 * - The end address if we could perform the full read 187 */ 188 cbegin = ti->ti_begin; 189 cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen), 190 TTYINQ_DATASIZE); 191 clen = cend - cbegin; 192 MPASS(clen >= flen); 193 rlen -= clen; 194 195 /* 196 * Caller shouldn't request that we trim anything if we might be 197 * reading across blocks. We could handle it, but today we do 198 * not. 199 */ 200 if (flen > 0) 201 MPASS(rlen == 0); 202 203 /* 204 * We can prevent buffering in some cases: 205 * - We need to read the block until the end. 206 * - We don't need to read the block until the end, but 207 * there is no data beyond it, which allows us to move 208 * the write pointer to a new block. 209 */ 210 if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) { 211 /* 212 * Fast path: zero copy. Remove the first block, 213 * so we can unlock the TTY temporarily. 214 */ 215 TTYINQ_REMOVE_HEAD(ti); 216 ti->ti_begin = 0; 217 218 /* 219 * Because we remove the first block, we must 220 * fix up the block offsets. 221 */ 222 #define CORRECT_BLOCK(t) do { \ 223 if (t <= TTYINQ_DATASIZE) \ 224 t = 0; \ 225 else \ 226 t -= TTYINQ_DATASIZE; \ 227 } while (0) 228 CORRECT_BLOCK(ti->ti_linestart); 229 CORRECT_BLOCK(ti->ti_reprint); 230 CORRECT_BLOCK(ti->ti_end); 231 #undef CORRECT_BLOCK 232 233 /* 234 * Temporary unlock and copy the data to 235 * userspace. We may need to flush trailing 236 * bytes, like EOF characters. 237 */ 238 tty_unlock(tp); 239 error = uiomove(tib->tib_data + cbegin, 240 clen - flen, uio); 241 tty_lock(tp); 242 243 /* Block can now be readded to the list. */ 244 TTYINQ_RECYCLE(ti, tib); 245 } else { 246 char ob[TTYINQ_DATASIZE - 1]; 247 248 /* 249 * Slow path: store data in a temporary buffer. 250 */ 251 memcpy(ob, tib->tib_data + cbegin, clen - flen); 252 ti->ti_begin += clen; 253 MPASS(ti->ti_begin < TTYINQ_DATASIZE); 254 255 /* Temporary unlock and copy the data to userspace. */ 256 tty_unlock(tp); 257 error = uiomove(ob, clen - flen, uio); 258 tty_lock(tp); 259 } 260 261 if (error != 0) 262 return (error); 263 if (tty_gone(tp)) 264 return (ENXIO); 265 } 266 267 return (0); 268 } 269 270 static __inline void 271 ttyinq_set_quotes(struct ttyinq_block *tib, size_t offset, 272 size_t length, int value) 273 { 274 275 if (value) { 276 /* Set the bits. */ 277 for (; length > 0; length--, offset++) 278 SETBIT(tib, offset); 279 } else { 280 /* Unset the bits. */ 281 for (; length > 0; length--, offset++) 282 CLRBIT(tib, offset); 283 } 284 } 285 286 size_t 287 ttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 288 { 289 const char *cbuf = buf; 290 struct ttyinq_block *tib; 291 unsigned int boff; 292 size_t l; 293 294 while (nbytes > 0) { 295 boff = ti->ti_end % TTYINQ_DATASIZE; 296 297 if (ti->ti_end == 0) { 298 /* First time we're being used or drained. */ 299 MPASS(ti->ti_begin == 0); 300 tib = ti->ti_firstblock; 301 if (tib == NULL) { 302 /* Queue has no blocks. */ 303 break; 304 } 305 ti->ti_lastblock = tib; 306 } else if (boff == 0) { 307 /* We reached the end of this block on last write. */ 308 tib = ti->ti_lastblock->tib_next; 309 if (tib == NULL) { 310 /* We've reached the watermark. */ 311 break; 312 } 313 ti->ti_lastblock = tib; 314 } else { 315 tib = ti->ti_lastblock; 316 } 317 318 /* Don't copy more than was requested. */ 319 l = MIN(nbytes, TTYINQ_DATASIZE - boff); 320 MPASS(l > 0); 321 memcpy(tib->tib_data + boff, cbuf, l); 322 323 /* Set the quoting bits for the proper region. */ 324 ttyinq_set_quotes(tib, boff, l, quote); 325 326 cbuf += l; 327 nbytes -= l; 328 ti->ti_end += l; 329 } 330 331 return (cbuf - (const char *)buf); 332 } 333 334 int 335 ttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 336 { 337 size_t ret __unused; 338 339 if (ttyinq_bytesleft(ti) < nbytes) 340 return (-1); 341 342 /* We should always be able to write it back. */ 343 ret = ttyinq_write(ti, buf, nbytes, quote); 344 MPASS(ret == nbytes); 345 346 return (0); 347 } 348 349 void 350 ttyinq_canonicalize(struct ttyinq *ti) 351 { 352 353 ti->ti_linestart = ti->ti_reprint = ti->ti_end; 354 ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock; 355 } 356 357 /* 358 * Canonicalize at one of the break characters; we'll work backwards from the 359 * lastblock to firstblock to try and find the latest one. 360 */ 361 void 362 ttyinq_canonicalize_break(struct ttyinq *ti, const char *breakc) 363 { 364 struct ttyinq_block *tib = ti->ti_lastblock; 365 unsigned int canon, off; 366 unsigned int boff; 367 368 /* No block, no change needed. */ 369 if (tib == NULL || ti->ti_end == 0) 370 return; 371 372 /* Start just past the end... */ 373 off = ti->ti_end; 374 canon = ti->ti_begin; 375 376 while (off > ti->ti_begin) { 377 off--; 378 boff = off % TTYINQ_DATASIZE; 379 380 if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) { 381 canon = off + 1; 382 break; 383 } 384 385 if (off != ti->ti_begin && boff == 0) 386 tib = tib->tib_prev; 387 } 388 389 MPASS(canon > ti->ti_begin || off == ti->ti_begin); 390 391 /* 392 * We should only be able to hit canon == ti_begin if we walked 393 * everything we have and didn't find any of the break characters, so 394 * if canon == ti_begin then tib is already the correct block and we 395 * should avoid touching it. 396 * 397 * For all other scenarios, if canon lies on a block boundary then tib 398 * has already advanced to the previous block. 399 */ 400 if (canon != ti->ti_begin && (canon % TTYINQ_DATASIZE) == 0) 401 tib = tib->tib_next; 402 ti->ti_linestart = ti->ti_reprint = canon; 403 ti->ti_startblock = ti->ti_reprintblock = tib; 404 } 405 406 size_t 407 ttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen, 408 char *lastc) 409 { 410 struct ttyinq_block *tib = ti->ti_firstblock; 411 unsigned int boff = ti->ti_begin; 412 unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart), 413 ti->ti_begin + maxlen); 414 415 MPASS(maxlen > 0); 416 417 if (tib == NULL) 418 return (0); 419 420 while (boff < bend) { 421 if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) { 422 *lastc = tib->tib_data[boff]; 423 return (boff - ti->ti_begin + 1); 424 } 425 boff++; 426 } 427 428 /* Not found - just process the entire block. */ 429 return (bend - ti->ti_begin); 430 } 431 432 void 433 ttyinq_flush(struct ttyinq *ti) 434 { 435 struct ttyinq_block *tib; 436 437 ti->ti_begin = 0; 438 ti->ti_linestart = 0; 439 ti->ti_reprint = 0; 440 ti->ti_end = 0; 441 442 /* Zero all data in the input queue to get rid of passwords. */ 443 if (ttyinq_flush_secure) { 444 for (tib = ti->ti_firstblock; tib != NULL; tib = tib->tib_next) 445 bzero(&tib->tib_data, sizeof tib->tib_data); 446 } 447 } 448 449 int 450 ttyinq_peekchar(struct ttyinq *ti, char *c, int *quote) 451 { 452 unsigned int boff; 453 struct ttyinq_block *tib = ti->ti_lastblock; 454 455 if (ti->ti_linestart == ti->ti_end) 456 return (-1); 457 458 MPASS(ti->ti_end > 0); 459 boff = (ti->ti_end - 1) % TTYINQ_DATASIZE; 460 461 *c = tib->tib_data[boff]; 462 *quote = GETBIT(tib, boff); 463 464 return (0); 465 } 466 467 void 468 ttyinq_unputchar(struct ttyinq *ti) 469 { 470 471 MPASS(ti->ti_linestart < ti->ti_end); 472 473 if (--ti->ti_end % TTYINQ_DATASIZE == 0) { 474 /* Roll back to the previous block. */ 475 ti->ti_lastblock = ti->ti_lastblock->tib_prev; 476 /* 477 * This can only fail if we are unputchar()'ing the 478 * first character in the queue. 479 */ 480 MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0)); 481 } 482 } 483 484 void 485 ttyinq_reprintpos_set(struct ttyinq *ti) 486 { 487 488 ti->ti_reprint = ti->ti_end; 489 ti->ti_reprintblock = ti->ti_lastblock; 490 } 491 492 void 493 ttyinq_reprintpos_reset(struct ttyinq *ti) 494 { 495 496 ti->ti_reprint = ti->ti_linestart; 497 ti->ti_reprintblock = ti->ti_startblock; 498 } 499 500 static void 501 ttyinq_line_iterate(struct ttyinq *ti, 502 ttyinq_line_iterator_t *iterator, void *data, 503 unsigned int offset, struct ttyinq_block *tib) 504 { 505 unsigned int boff; 506 507 /* Use the proper block when we're at the queue head. */ 508 if (offset == 0) 509 tib = ti->ti_firstblock; 510 511 /* Iterate all characters and call the iterator function. */ 512 for (; offset < ti->ti_end; offset++) { 513 boff = offset % TTYINQ_DATASIZE; 514 MPASS(tib != NULL); 515 516 /* Call back the iterator function. */ 517 iterator(data, tib->tib_data[boff], GETBIT(tib, boff)); 518 519 /* Last byte iterated - go to the next block. */ 520 if (boff == TTYINQ_DATASIZE - 1) 521 tib = tib->tib_next; 522 } 523 } 524 525 void 526 ttyinq_line_iterate_from_linestart(struct ttyinq *ti, 527 ttyinq_line_iterator_t *iterator, void *data) 528 { 529 530 ttyinq_line_iterate(ti, iterator, data, 531 ti->ti_linestart, ti->ti_startblock); 532 } 533 534 void 535 ttyinq_line_iterate_from_reprintpos(struct ttyinq *ti, 536 ttyinq_line_iterator_t *iterator, void *data) 537 { 538 539 ttyinq_line_iterate(ti, iterator, data, 540 ti->ti_reprint, ti->ti_reprintblock); 541 } 542 543 static void 544 ttyinq_startup(void *dummy) 545 { 546 547 ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block), 548 NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0); 549 } 550 551 SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL); 552