1181905Sed/*- 2181905Sed * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org> 3181905Sed * All rights reserved. 4181905Sed * 5181905Sed * Portions of this software were developed under sponsorship from Snow 6181905Sed * B.V., the Netherlands. 7181905Sed * 8181905Sed * Redistribution and use in source and binary forms, with or without 9181905Sed * modification, are permitted provided that the following conditions 10181905Sed * are met: 11181905Sed * 1. Redistributions of source code must retain the above copyright 12181905Sed * notice, this list of conditions and the following disclaimer. 13181905Sed * 2. Redistributions in binary form must reproduce the above copyright 14181905Sed * notice, this list of conditions and the following disclaimer in the 15181905Sed * documentation and/or other materials provided with the distribution. 16181905Sed * 17181905Sed * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 18181905Sed * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19181905Sed * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 20181905Sed * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 21181905Sed * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 22181905Sed * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 23181905Sed * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 24181905Sed * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 25181905Sed * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 26181905Sed * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 27181905Sed * SUCH DAMAGE. 28181905Sed */ 29181905Sed 30181905Sed#include <sys/cdefs.h> 31181905Sed__FBSDID("$FreeBSD$"); 32181905Sed 33181905Sed#include <sys/param.h> 34181905Sed#include <sys/kernel.h> 35181905Sed#include <sys/lock.h> 36181905Sed#include <sys/queue.h> 37181905Sed#include <sys/sysctl.h> 38181905Sed#include <sys/systm.h> 39181905Sed#include <sys/tty.h> 40181905Sed#include <sys/uio.h> 41181905Sed 42181905Sed#include <vm/uma.h> 43181905Sed 44181905Sed/* 45181905Sed * TTY input queue buffering. 46181905Sed * 47181905Sed * Unlike the output queue, the input queue has more features that are 48181905Sed * needed to properly implement various features offered by the TTY 49181905Sed * interface: 50181905Sed * 51181905Sed * - Data can be removed from the tail of the queue, which is used to 52181905Sed * implement backspace. 53181905Sed * - Once in a while, input has to be `canonicalized'. When ICANON is 54181905Sed * turned on, this will be done after a CR has been inserted. 55181905Sed * Otherwise, it should be done after any character has been inserted. 56181905Sed * - The input queue can store one bit per byte, called the quoting bit. 57181905Sed * This bit is used by TTYDISC to make backspace work on quoted 58181905Sed * characters. 59181905Sed * 60181905Sed * In most cases, there is probably less input than output, so unlike 61181905Sed * the outq, we'll stick to 128 byte blocks here. 62181905Sed */ 63181905Sed 64192546Sedstatic int ttyinq_flush_secure = 1; 65192544SedSYSCTL_INT(_kern, OID_AUTO, tty_inq_flush_secure, CTLFLAG_RW, 66192544Sed &ttyinq_flush_secure, 0, "Zero buffers while flushing"); 67181905Sed 68181905Sed#define TTYINQ_QUOTESIZE (TTYINQ_DATASIZE / BMSIZE) 69181905Sed#define BMSIZE 32 70181905Sed#define GETBIT(tib,boff) \ 71181905Sed ((tib)->tib_quotes[(boff) / BMSIZE] & (1 << ((boff) % BMSIZE))) 72181905Sed#define SETBIT(tib,boff) \ 73181905Sed ((tib)->tib_quotes[(boff) / BMSIZE] |= (1 << ((boff) % BMSIZE))) 74181905Sed#define CLRBIT(tib,boff) \ 75181905Sed ((tib)->tib_quotes[(boff) / BMSIZE] &= ~(1 << ((boff) % BMSIZE))) 76181905Sed 77181905Sedstruct ttyinq_block { 78188096Sed struct ttyinq_block *tib_prev; 79188096Sed struct ttyinq_block *tib_next; 80188096Sed uint32_t tib_quotes[TTYINQ_QUOTESIZE]; 81188096Sed char tib_data[TTYINQ_DATASIZE]; 82181905Sed}; 83181905Sed 84181905Sedstatic uma_zone_t ttyinq_zone; 85181905Sed 86188096Sed#define TTYINQ_INSERT_TAIL(ti, tib) do { \ 87188096Sed if (ti->ti_end == 0) { \ 88188096Sed tib->tib_prev = NULL; \ 89188096Sed tib->tib_next = ti->ti_firstblock; \ 90188096Sed ti->ti_firstblock = tib; \ 91188096Sed } else { \ 92188096Sed tib->tib_prev = ti->ti_lastblock; \ 93188096Sed tib->tib_next = ti->ti_lastblock->tib_next; \ 94188096Sed ti->ti_lastblock->tib_next = tib; \ 95188096Sed } \ 96188096Sed if (tib->tib_next != NULL) \ 97188096Sed tib->tib_next->tib_prev = tib; \ 98188096Sed ti->ti_nblocks++; \ 99188096Sed} while (0) 100188096Sed 101188096Sed#define TTYINQ_REMOVE_HEAD(ti) do { \ 102188096Sed ti->ti_firstblock = ti->ti_firstblock->tib_next; \ 103188096Sed if (ti->ti_firstblock != NULL) \ 104188096Sed ti->ti_firstblock->tib_prev = NULL; \ 105188096Sed ti->ti_nblocks--; \ 106188096Sed} while (0) 107188096Sed 108188096Sed#define TTYINQ_RECYCLE(ti, tib) do { \ 109188096Sed if (ti->ti_quota <= ti->ti_nblocks) \ 110188096Sed uma_zfree(ttyinq_zone, tib); \ 111188096Sed else \ 112188096Sed TTYINQ_INSERT_TAIL(ti, tib); \ 113188096Sed} while (0) 114188096Sed 115181905Sedvoid 116181905Sedttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t size) 117181905Sed{ 118181905Sed struct ttyinq_block *tib; 119181905Sed 120182471Sed ti->ti_quota = howmany(size, TTYINQ_DATASIZE); 121181905Sed 122182471Sed while (ti->ti_quota > ti->ti_nblocks) { 123181905Sed /* 124181905Sed * List is getting bigger. 125181905Sed * Add new blocks to the tail of the list. 126181905Sed * 127181905Sed * We must unlock the TTY temporarily, because we need 128181905Sed * to allocate memory. This won't be a problem, because 129181905Sed * in the worst case, another thread ends up here, which 130181905Sed * may cause us to allocate too many blocks, but this 131181905Sed * will be caught by the loop below. 132181905Sed */ 133181905Sed tty_unlock(tp); 134181905Sed tib = uma_zalloc(ttyinq_zone, M_WAITOK); 135181905Sed tty_lock(tp); 136181905Sed 137188096Sed TTYINQ_INSERT_TAIL(ti, tib); 138181905Sed } 139182471Sed} 140181905Sed 141182471Sedvoid 142182471Sedttyinq_free(struct ttyinq *ti) 143182471Sed{ 144182471Sed struct ttyinq_block *tib; 145223575Sed 146182471Sed ttyinq_flush(ti); 147182471Sed ti->ti_quota = 0; 148181905Sed 149188096Sed while ((tib = ti->ti_firstblock) != NULL) { 150188096Sed TTYINQ_REMOVE_HEAD(ti); 151181905Sed uma_zfree(ttyinq_zone, tib); 152181905Sed } 153182471Sed 154182471Sed MPASS(ti->ti_nblocks == 0); 155181905Sed} 156181905Sed 157181905Sedint 158181905Sedttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio, 159181905Sed size_t rlen, size_t flen) 160181905Sed{ 161181905Sed 162181905Sed MPASS(rlen <= uio->uio_resid); 163181905Sed 164181905Sed while (rlen > 0) { 165181905Sed int error; 166181905Sed struct ttyinq_block *tib; 167181905Sed size_t cbegin, cend, clen; 168181905Sed 169181905Sed /* See if there still is data. */ 170181905Sed if (ti->ti_begin == ti->ti_linestart) 171181905Sed return (0); 172188096Sed tib = ti->ti_firstblock; 173181905Sed if (tib == NULL) 174181905Sed return (0); 175181905Sed 176181905Sed /* 177181905Sed * The end address should be the lowest of these three: 178181905Sed * - The write pointer 179181905Sed * - The blocksize - we can't read beyond the block 180181905Sed * - The end address if we could perform the full read 181181905Sed */ 182181905Sed cbegin = ti->ti_begin; 183181905Sed cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen), 184181905Sed TTYINQ_DATASIZE); 185181905Sed clen = cend - cbegin; 186181905Sed MPASS(clen >= flen); 187181905Sed rlen -= clen; 188181905Sed 189181905Sed /* 190181905Sed * We can prevent buffering in some cases: 191181905Sed * - We need to read the block until the end. 192181905Sed * - We don't need to read the block until the end, but 193181905Sed * there is no data beyond it, which allows us to move 194181905Sed * the write pointer to a new block. 195181905Sed */ 196181905Sed if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) { 197181905Sed /* 198181905Sed * Fast path: zero copy. Remove the first block, 199181905Sed * so we can unlock the TTY temporarily. 200181905Sed */ 201188096Sed TTYINQ_REMOVE_HEAD(ti); 202181905Sed ti->ti_begin = 0; 203181905Sed 204181905Sed /* 205181905Sed * Because we remove the first block, we must 206181905Sed * fix up the block offsets. 207181905Sed */ 208181905Sed#define CORRECT_BLOCK(t) do { \ 209188096Sed if (t <= TTYINQ_DATASIZE) \ 210181905Sed t = 0; \ 211188096Sed else \ 212181905Sed t -= TTYINQ_DATASIZE; \ 213181905Sed} while (0) 214181905Sed CORRECT_BLOCK(ti->ti_linestart); 215181905Sed CORRECT_BLOCK(ti->ti_reprint); 216181905Sed CORRECT_BLOCK(ti->ti_end); 217181905Sed#undef CORRECT_BLOCK 218181905Sed 219181905Sed /* 220181905Sed * Temporary unlock and copy the data to 221181905Sed * userspace. We may need to flush trailing 222181905Sed * bytes, like EOF characters. 223181905Sed */ 224181905Sed tty_unlock(tp); 225181905Sed error = uiomove(tib->tib_data + cbegin, 226181905Sed clen - flen, uio); 227181905Sed tty_lock(tp); 228181905Sed 229182471Sed /* Block can now be readded to the list. */ 230188096Sed TTYINQ_RECYCLE(ti, tib); 231181905Sed } else { 232181905Sed char ob[TTYINQ_DATASIZE - 1]; 233181905Sed 234181905Sed /* 235181905Sed * Slow path: store data in a temporary buffer. 236181905Sed */ 237181905Sed memcpy(ob, tib->tib_data + cbegin, clen - flen); 238181905Sed ti->ti_begin += clen; 239181905Sed MPASS(ti->ti_begin < TTYINQ_DATASIZE); 240181905Sed 241181905Sed /* Temporary unlock and copy the data to userspace. */ 242181905Sed tty_unlock(tp); 243181905Sed error = uiomove(ob, clen - flen, uio); 244181905Sed tty_lock(tp); 245182471Sed } 246181905Sed 247182471Sed if (error != 0) 248182471Sed return (error); 249182471Sed if (tty_gone(tp)) 250182471Sed return (ENXIO); 251181905Sed } 252181905Sed 253181905Sed return (0); 254181905Sed} 255181905Sed 256181905Sedstatic __inline void 257181905Sedttyinq_set_quotes(struct ttyinq_block *tib, size_t offset, 258181905Sed size_t length, int value) 259181905Sed{ 260181905Sed 261181905Sed if (value) { 262181905Sed /* Set the bits. */ 263181905Sed for (; length > 0; length--, offset++) 264181905Sed SETBIT(tib, offset); 265181905Sed } else { 266181905Sed /* Unset the bits. */ 267181905Sed for (; length > 0; length--, offset++) 268181905Sed CLRBIT(tib, offset); 269181905Sed } 270181905Sed} 271181905Sed 272181905Sedsize_t 273181905Sedttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 274181905Sed{ 275181905Sed const char *cbuf = buf; 276181905Sed struct ttyinq_block *tib; 277181905Sed unsigned int boff; 278181905Sed size_t l; 279223575Sed 280181905Sed while (nbytes > 0) { 281181905Sed boff = ti->ti_end % TTYINQ_DATASIZE; 282181905Sed 283181905Sed if (ti->ti_end == 0) { 284181905Sed /* First time we're being used or drained. */ 285181905Sed MPASS(ti->ti_begin == 0); 286188096Sed tib = ti->ti_firstblock; 287181905Sed if (tib == NULL) { 288181905Sed /* Queue has no blocks. */ 289181905Sed break; 290181905Sed } 291188096Sed ti->ti_lastblock = tib; 292181905Sed } else if (boff == 0) { 293181905Sed /* We reached the end of this block on last write. */ 294188096Sed tib = ti->ti_lastblock->tib_next; 295181905Sed if (tib == NULL) { 296181905Sed /* We've reached the watermark. */ 297181905Sed break; 298181905Sed } 299181905Sed ti->ti_lastblock = tib; 300188096Sed } else { 301188096Sed tib = ti->ti_lastblock; 302181905Sed } 303181905Sed 304181905Sed /* Don't copy more than was requested. */ 305181905Sed l = MIN(nbytes, TTYINQ_DATASIZE - boff); 306181905Sed MPASS(l > 0); 307181905Sed memcpy(tib->tib_data + boff, cbuf, l); 308181905Sed 309181905Sed /* Set the quoting bits for the proper region. */ 310181905Sed ttyinq_set_quotes(tib, boff, l, quote); 311181905Sed 312181905Sed cbuf += l; 313181905Sed nbytes -= l; 314181905Sed ti->ti_end += l; 315181905Sed } 316223575Sed 317181905Sed return (cbuf - (const char *)buf); 318181905Sed} 319181905Sed 320181905Sedint 321181905Sedttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 322181905Sed{ 323181905Sed size_t ret; 324181905Sed 325181905Sed if (ttyinq_bytesleft(ti) < nbytes) 326181905Sed return (-1); 327181905Sed 328181905Sed /* We should always be able to write it back. */ 329181905Sed ret = ttyinq_write(ti, buf, nbytes, quote); 330181905Sed MPASS(ret == nbytes); 331181905Sed 332181905Sed return (0); 333181905Sed} 334181905Sed 335181905Sedvoid 336181905Sedttyinq_canonicalize(struct ttyinq *ti) 337181905Sed{ 338181905Sed 339181905Sed ti->ti_linestart = ti->ti_reprint = ti->ti_end; 340181905Sed ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock; 341181905Sed} 342181905Sed 343181905Sedsize_t 344181905Sedttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen, 345181905Sed char *lastc) 346181905Sed{ 347188096Sed struct ttyinq_block *tib = ti->ti_firstblock; 348181905Sed unsigned int boff = ti->ti_begin; 349181905Sed unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart), 350181905Sed ti->ti_begin + maxlen); 351181905Sed 352181905Sed MPASS(maxlen > 0); 353181905Sed 354181905Sed if (tib == NULL) 355181905Sed return (0); 356181905Sed 357181905Sed while (boff < bend) { 358229272Sed if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) { 359181905Sed *lastc = tib->tib_data[boff]; 360181905Sed return (boff - ti->ti_begin + 1); 361181905Sed } 362181905Sed boff++; 363181905Sed } 364181905Sed 365181905Sed /* Not found - just process the entire block. */ 366181905Sed return (bend - ti->ti_begin); 367181905Sed} 368181905Sed 369181905Sedvoid 370181905Sedttyinq_flush(struct ttyinq *ti) 371181905Sed{ 372202583Sed struct ttyinq_block *tib; 373181905Sed 374181905Sed ti->ti_begin = 0; 375181905Sed ti->ti_linestart = 0; 376181905Sed ti->ti_reprint = 0; 377181905Sed ti->ti_end = 0; 378181905Sed 379192544Sed /* Zero all data in the input queue to get rid of passwords. */ 380192544Sed if (ttyinq_flush_secure) { 381192544Sed for (tib = ti->ti_firstblock; tib != NULL; tib = tib->tib_next) 382192544Sed bzero(&tib->tib_data, sizeof tib->tib_data); 383181905Sed } 384181905Sed} 385181905Sed 386181905Sedint 387181905Sedttyinq_peekchar(struct ttyinq *ti, char *c, int *quote) 388181905Sed{ 389181905Sed unsigned int boff; 390181905Sed struct ttyinq_block *tib = ti->ti_lastblock; 391181905Sed 392181905Sed if (ti->ti_linestart == ti->ti_end) 393181905Sed return (-1); 394181905Sed 395181905Sed MPASS(ti->ti_end > 0); 396181905Sed boff = (ti->ti_end - 1) % TTYINQ_DATASIZE; 397181905Sed 398181905Sed *c = tib->tib_data[boff]; 399181905Sed *quote = GETBIT(tib, boff); 400223575Sed 401181905Sed return (0); 402181905Sed} 403181905Sed 404181905Sedvoid 405181905Sedttyinq_unputchar(struct ttyinq *ti) 406181905Sed{ 407181905Sed 408181905Sed MPASS(ti->ti_linestart < ti->ti_end); 409181905Sed 410181905Sed if (--ti->ti_end % TTYINQ_DATASIZE == 0) { 411181905Sed /* Roll back to the previous block. */ 412188096Sed ti->ti_lastblock = ti->ti_lastblock->tib_prev; 413181905Sed /* 414181905Sed * This can only fail if we are unputchar()'ing the 415181905Sed * first character in the queue. 416181905Sed */ 417181905Sed MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0)); 418181905Sed } 419181905Sed} 420181905Sed 421181905Sedvoid 422181905Sedttyinq_reprintpos_set(struct ttyinq *ti) 423181905Sed{ 424181905Sed 425181905Sed ti->ti_reprint = ti->ti_end; 426181905Sed ti->ti_reprintblock = ti->ti_lastblock; 427181905Sed} 428181905Sed 429181905Sedvoid 430181905Sedttyinq_reprintpos_reset(struct ttyinq *ti) 431181905Sed{ 432181905Sed 433181905Sed ti->ti_reprint = ti->ti_linestart; 434181905Sed ti->ti_reprintblock = ti->ti_startblock; 435181905Sed} 436181905Sed 437181905Sedstatic void 438181905Sedttyinq_line_iterate(struct ttyinq *ti, 439181905Sed ttyinq_line_iterator_t *iterator, void *data, 440181905Sed unsigned int offset, struct ttyinq_block *tib) 441181905Sed{ 442181905Sed unsigned int boff; 443181905Sed 444181905Sed /* Use the proper block when we're at the queue head. */ 445181905Sed if (offset == 0) 446188096Sed tib = ti->ti_firstblock; 447181905Sed 448181905Sed /* Iterate all characters and call the iterator function. */ 449181905Sed for (; offset < ti->ti_end; offset++) { 450181905Sed boff = offset % TTYINQ_DATASIZE; 451181905Sed MPASS(tib != NULL); 452181905Sed 453181905Sed /* Call back the iterator function. */ 454181905Sed iterator(data, tib->tib_data[boff], GETBIT(tib, boff)); 455181905Sed 456181905Sed /* Last byte iterated - go to the next block. */ 457181905Sed if (boff == TTYINQ_DATASIZE - 1) 458188096Sed tib = tib->tib_next; 459181905Sed MPASS(tib != NULL); 460181905Sed } 461181905Sed} 462181905Sed 463181905Sedvoid 464181905Sedttyinq_line_iterate_from_linestart(struct ttyinq *ti, 465181905Sed ttyinq_line_iterator_t *iterator, void *data) 466181905Sed{ 467181905Sed 468181905Sed ttyinq_line_iterate(ti, iterator, data, 469181905Sed ti->ti_linestart, ti->ti_startblock); 470181905Sed} 471181905Sed 472181905Sedvoid 473181905Sedttyinq_line_iterate_from_reprintpos(struct ttyinq *ti, 474181905Sed ttyinq_line_iterator_t *iterator, void *data) 475181905Sed{ 476181905Sed 477181905Sed ttyinq_line_iterate(ti, iterator, data, 478181905Sed ti->ti_reprint, ti->ti_reprintblock); 479181905Sed} 480181905Sed 481181905Sedstatic void 482181905Sedttyinq_startup(void *dummy) 483181905Sed{ 484181905Sed 485181905Sed ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block), 486181905Sed NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0); 487181905Sed} 488181905Sed 489181905SedSYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL); 490