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 static int ttyinq_flush_secure = 1; 65 SYSCTL_INT(_kern, OID_AUTO, tty_inq_flush_secure, CTLFLAG_RW, 66 &ttyinq_flush_secure, 0, "Zero buffers while flushing"); 67 68 #define TTYINQ_QUOTESIZE (TTYINQ_DATASIZE / BMSIZE) 69 #define BMSIZE 32 70 #define GETBIT(tib,boff) \ 71 ((tib)->tib_quotes[(boff) / BMSIZE] & (1 << ((boff) % BMSIZE))) 72 #define SETBIT(tib,boff) \ 73 ((tib)->tib_quotes[(boff) / BMSIZE] |= (1 << ((boff) % BMSIZE))) 74 #define CLRBIT(tib,boff) \ 75 ((tib)->tib_quotes[(boff) / BMSIZE] &= ~(1 << ((boff) % BMSIZE))) 76 77 struct ttyinq_block { 78 struct ttyinq_block *tib_prev; 79 struct ttyinq_block *tib_next; 80 uint32_t tib_quotes[TTYINQ_QUOTESIZE]; 81 char tib_data[TTYINQ_DATASIZE]; 82 }; 83 84 static uma_zone_t ttyinq_zone; 85 86 #define TTYINQ_INSERT_TAIL(ti, tib) do { \ 87 if (ti->ti_end == 0) { \ 88 tib->tib_prev = NULL; \ 89 tib->tib_next = ti->ti_firstblock; \ 90 ti->ti_firstblock = tib; \ 91 } else { \ 92 tib->tib_prev = ti->ti_lastblock; \ 93 tib->tib_next = ti->ti_lastblock->tib_next; \ 94 ti->ti_lastblock->tib_next = tib; \ 95 } \ 96 if (tib->tib_next != NULL) \ 97 tib->tib_next->tib_prev = tib; \ 98 ti->ti_nblocks++; \ 99 } while (0) 100 101 #define TTYINQ_REMOVE_HEAD(ti) do { \ 102 ti->ti_firstblock = ti->ti_firstblock->tib_next; \ 103 if (ti->ti_firstblock != NULL) \ 104 ti->ti_firstblock->tib_prev = NULL; \ 105 ti->ti_nblocks--; \ 106 } while (0) 107 108 #define TTYINQ_RECYCLE(ti, tib) do { \ 109 if (ti->ti_quota <= ti->ti_nblocks) \ 110 uma_zfree(ttyinq_zone, tib); \ 111 else \ 112 TTYINQ_INSERT_TAIL(ti, tib); \ 113 } while (0) 114 115 void 116 ttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t size) 117 { 118 struct ttyinq_block *tib; 119 120 ti->ti_quota = howmany(size, TTYINQ_DATASIZE); 121 122 while (ti->ti_quota > ti->ti_nblocks) { 123 /* 124 * List is getting bigger. 125 * Add new blocks to the tail of the list. 126 * 127 * We must unlock the TTY temporarily, because we need 128 * to allocate memory. This won't be a problem, because 129 * in the worst case, another thread ends up here, which 130 * may cause us to allocate too many blocks, but this 131 * will be caught by the loop below. 132 */ 133 tty_unlock(tp); 134 tib = uma_zalloc(ttyinq_zone, M_WAITOK); 135 tty_lock(tp); 136 137 TTYINQ_INSERT_TAIL(ti, tib); 138 } 139 } 140 141 void 142 ttyinq_free(struct ttyinq *ti) 143 { 144 struct ttyinq_block *tib; 145 146 ttyinq_flush(ti); 147 ti->ti_quota = 0; 148 149 while ((tib = ti->ti_firstblock) != NULL) { 150 TTYINQ_REMOVE_HEAD(ti); 151 uma_zfree(ttyinq_zone, tib); 152 } 153 154 MPASS(ti->ti_nblocks == 0); 155 } 156 157 int 158 ttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio, 159 size_t rlen, size_t flen) 160 { 161 162 MPASS(rlen <= uio->uio_resid); 163 164 while (rlen > 0) { 165 int error; 166 struct ttyinq_block *tib; 167 size_t cbegin, cend, clen; 168 169 /* See if there still is data. */ 170 if (ti->ti_begin == ti->ti_linestart) 171 return (0); 172 tib = ti->ti_firstblock; 173 if (tib == NULL) 174 return (0); 175 176 /* 177 * The end address should be the lowest of these three: 178 * - The write pointer 179 * - The blocksize - we can't read beyond the block 180 * - The end address if we could perform the full read 181 */ 182 cbegin = ti->ti_begin; 183 cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen), 184 TTYINQ_DATASIZE); 185 clen = cend - cbegin; 186 MPASS(clen >= flen); 187 rlen -= clen; 188 189 /* 190 * We can prevent buffering in some cases: 191 * - We need to read the block until the end. 192 * - We don't need to read the block until the end, but 193 * there is no data beyond it, which allows us to move 194 * the write pointer to a new block. 195 */ 196 if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) { 197 /* 198 * Fast path: zero copy. Remove the first block, 199 * so we can unlock the TTY temporarily. 200 */ 201 TTYINQ_REMOVE_HEAD(ti); 202 ti->ti_begin = 0; 203 204 /* 205 * Because we remove the first block, we must 206 * fix up the block offsets. 207 */ 208 #define CORRECT_BLOCK(t) do { \ 209 if (t <= TTYINQ_DATASIZE) \ 210 t = 0; \ 211 else \ 212 t -= TTYINQ_DATASIZE; \ 213 } while (0) 214 CORRECT_BLOCK(ti->ti_linestart); 215 CORRECT_BLOCK(ti->ti_reprint); 216 CORRECT_BLOCK(ti->ti_end); 217 #undef CORRECT_BLOCK 218 219 /* 220 * Temporary unlock and copy the data to 221 * userspace. We may need to flush trailing 222 * bytes, like EOF characters. 223 */ 224 tty_unlock(tp); 225 error = uiomove(tib->tib_data + cbegin, 226 clen - flen, uio); 227 tty_lock(tp); 228 229 /* Block can now be readded to the list. */ 230 TTYINQ_RECYCLE(ti, tib); 231 } else { 232 char ob[TTYINQ_DATASIZE - 1]; 233 234 /* 235 * Slow path: store data in a temporary buffer. 236 */ 237 memcpy(ob, tib->tib_data + cbegin, clen - flen); 238 ti->ti_begin += clen; 239 MPASS(ti->ti_begin < TTYINQ_DATASIZE); 240 241 /* Temporary unlock and copy the data to userspace. */ 242 tty_unlock(tp); 243 error = uiomove(ob, clen - flen, uio); 244 tty_lock(tp); 245 } 246 247 if (error != 0) 248 return (error); 249 if (tty_gone(tp)) 250 return (ENXIO); 251 } 252 253 return (0); 254 } 255 256 static __inline void 257 ttyinq_set_quotes(struct ttyinq_block *tib, size_t offset, 258 size_t length, int value) 259 { 260 261 if (value) { 262 /* Set the bits. */ 263 for (; length > 0; length--, offset++) 264 SETBIT(tib, offset); 265 } else { 266 /* Unset the bits. */ 267 for (; length > 0; length--, offset++) 268 CLRBIT(tib, offset); 269 } 270 } 271 272 size_t 273 ttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 274 { 275 const char *cbuf = buf; 276 struct ttyinq_block *tib; 277 unsigned int boff; 278 size_t l; 279 280 while (nbytes > 0) { 281 boff = ti->ti_end % TTYINQ_DATASIZE; 282 283 if (ti->ti_end == 0) { 284 /* First time we're being used or drained. */ 285 MPASS(ti->ti_begin == 0); 286 tib = ti->ti_firstblock; 287 if (tib == NULL) { 288 /* Queue has no blocks. */ 289 break; 290 } 291 ti->ti_lastblock = tib; 292 } else if (boff == 0) { 293 /* We reached the end of this block on last write. */ 294 tib = ti->ti_lastblock->tib_next; 295 if (tib == NULL) { 296 /* We've reached the watermark. */ 297 break; 298 } 299 ti->ti_lastblock = tib; 300 } else { 301 tib = ti->ti_lastblock; 302 } 303 304 /* Don't copy more than was requested. */ 305 l = MIN(nbytes, TTYINQ_DATASIZE - boff); 306 MPASS(l > 0); 307 memcpy(tib->tib_data + boff, cbuf, l); 308 309 /* Set the quoting bits for the proper region. */ 310 ttyinq_set_quotes(tib, boff, l, quote); 311 312 cbuf += l; 313 nbytes -= l; 314 ti->ti_end += l; 315 } 316 317 return (cbuf - (const char *)buf); 318 } 319 320 int 321 ttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 322 { 323 size_t ret; 324 325 if (ttyinq_bytesleft(ti) < nbytes) 326 return (-1); 327 328 /* We should always be able to write it back. */ 329 ret = ttyinq_write(ti, buf, nbytes, quote); 330 MPASS(ret == nbytes); 331 332 return (0); 333 } 334 335 void 336 ttyinq_canonicalize(struct ttyinq *ti) 337 { 338 339 ti->ti_linestart = ti->ti_reprint = ti->ti_end; 340 ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock; 341 } 342 343 size_t 344 ttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen, 345 char *lastc) 346 { 347 struct ttyinq_block *tib = ti->ti_firstblock; 348 unsigned int boff = ti->ti_begin; 349 unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart), 350 ti->ti_begin + maxlen); 351 352 MPASS(maxlen > 0); 353 354 if (tib == NULL) 355 return (0); 356 357 while (boff < bend) { 358 if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) { 359 *lastc = tib->tib_data[boff]; 360 return (boff - ti->ti_begin + 1); 361 } 362 boff++; 363 } 364 365 /* Not found - just process the entire block. */ 366 return (bend - ti->ti_begin); 367 } 368 369 void 370 ttyinq_flush(struct ttyinq *ti) 371 { 372 struct ttyinq_block *tib; 373 374 ti->ti_begin = 0; 375 ti->ti_linestart = 0; 376 ti->ti_reprint = 0; 377 ti->ti_end = 0; 378 379 /* Zero all data in the input queue to get rid of passwords. */ 380 if (ttyinq_flush_secure) { 381 for (tib = ti->ti_firstblock; tib != NULL; tib = tib->tib_next) 382 bzero(&tib->tib_data, sizeof tib->tib_data); 383 } 384 } 385 386 int 387 ttyinq_peekchar(struct ttyinq *ti, char *c, int *quote) 388 { 389 unsigned int boff; 390 struct ttyinq_block *tib = ti->ti_lastblock; 391 392 if (ti->ti_linestart == ti->ti_end) 393 return (-1); 394 395 MPASS(ti->ti_end > 0); 396 boff = (ti->ti_end - 1) % TTYINQ_DATASIZE; 397 398 *c = tib->tib_data[boff]; 399 *quote = GETBIT(tib, boff); 400 401 return (0); 402 } 403 404 void 405 ttyinq_unputchar(struct ttyinq *ti) 406 { 407 408 MPASS(ti->ti_linestart < ti->ti_end); 409 410 if (--ti->ti_end % TTYINQ_DATASIZE == 0) { 411 /* Roll back to the previous block. */ 412 ti->ti_lastblock = ti->ti_lastblock->tib_prev; 413 /* 414 * This can only fail if we are unputchar()'ing the 415 * first character in the queue. 416 */ 417 MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0)); 418 } 419 } 420 421 void 422 ttyinq_reprintpos_set(struct ttyinq *ti) 423 { 424 425 ti->ti_reprint = ti->ti_end; 426 ti->ti_reprintblock = ti->ti_lastblock; 427 } 428 429 void 430 ttyinq_reprintpos_reset(struct ttyinq *ti) 431 { 432 433 ti->ti_reprint = ti->ti_linestart; 434 ti->ti_reprintblock = ti->ti_startblock; 435 } 436 437 static void 438 ttyinq_line_iterate(struct ttyinq *ti, 439 ttyinq_line_iterator_t *iterator, void *data, 440 unsigned int offset, struct ttyinq_block *tib) 441 { 442 unsigned int boff; 443 444 /* Use the proper block when we're at the queue head. */ 445 if (offset == 0) 446 tib = ti->ti_firstblock; 447 448 /* Iterate all characters and call the iterator function. */ 449 for (; offset < ti->ti_end; offset++) { 450 boff = offset % TTYINQ_DATASIZE; 451 MPASS(tib != NULL); 452 453 /* Call back the iterator function. */ 454 iterator(data, tib->tib_data[boff], GETBIT(tib, boff)); 455 456 /* Last byte iterated - go to the next block. */ 457 if (boff == TTYINQ_DATASIZE - 1) 458 tib = tib->tib_next; 459 MPASS(tib != NULL); 460 } 461 } 462 463 void 464 ttyinq_line_iterate_from_linestart(struct ttyinq *ti, 465 ttyinq_line_iterator_t *iterator, void *data) 466 { 467 468 ttyinq_line_iterate(ti, iterator, data, 469 ti->ti_linestart, ti->ti_startblock); 470 } 471 472 void 473 ttyinq_line_iterate_from_reprintpos(struct ttyinq *ti, 474 ttyinq_line_iterator_t *iterator, void *data) 475 { 476 477 ttyinq_line_iterate(ti, iterator, data, 478 ti->ti_reprint, ti->ti_reprintblock); 479 } 480 481 static void 482 ttyinq_startup(void *dummy) 483 { 484 485 ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block), 486 NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0); 487 } 488 489 SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL); 490