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