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