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