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