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: stable/11/sys/kern/tty_inq.c 314538 2017-03-02 04:23:53Z ian $"); 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 115314538Sianint 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 137314538Sian if (tty_gone(tp)) { 138314538Sian uma_zfree(ttyinq_zone, tib); 139314538Sian return (ENXIO); 140314538Sian } 141314538Sian 142188096Sed TTYINQ_INSERT_TAIL(ti, tib); 143181905Sed } 144314538Sian return (0); 145182471Sed} 146181905Sed 147182471Sedvoid 148182471Sedttyinq_free(struct ttyinq *ti) 149182471Sed{ 150182471Sed struct ttyinq_block *tib; 151223575Sed 152182471Sed ttyinq_flush(ti); 153182471Sed ti->ti_quota = 0; 154181905Sed 155188096Sed while ((tib = ti->ti_firstblock) != NULL) { 156188096Sed TTYINQ_REMOVE_HEAD(ti); 157181905Sed uma_zfree(ttyinq_zone, tib); 158181905Sed } 159182471Sed 160182471Sed MPASS(ti->ti_nblocks == 0); 161181905Sed} 162181905Sed 163181905Sedint 164181905Sedttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio, 165181905Sed size_t rlen, size_t flen) 166181905Sed{ 167181905Sed 168181905Sed MPASS(rlen <= uio->uio_resid); 169181905Sed 170181905Sed while (rlen > 0) { 171181905Sed int error; 172181905Sed struct ttyinq_block *tib; 173181905Sed size_t cbegin, cend, clen; 174181905Sed 175181905Sed /* See if there still is data. */ 176181905Sed if (ti->ti_begin == ti->ti_linestart) 177181905Sed return (0); 178188096Sed tib = ti->ti_firstblock; 179181905Sed if (tib == NULL) 180181905Sed return (0); 181181905Sed 182181905Sed /* 183181905Sed * The end address should be the lowest of these three: 184181905Sed * - The write pointer 185181905Sed * - The blocksize - we can't read beyond the block 186181905Sed * - The end address if we could perform the full read 187181905Sed */ 188181905Sed cbegin = ti->ti_begin; 189181905Sed cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen), 190181905Sed TTYINQ_DATASIZE); 191181905Sed clen = cend - cbegin; 192181905Sed MPASS(clen >= flen); 193181905Sed rlen -= clen; 194181905Sed 195181905Sed /* 196181905Sed * We can prevent buffering in some cases: 197181905Sed * - We need to read the block until the end. 198181905Sed * - We don't need to read the block until the end, but 199181905Sed * there is no data beyond it, which allows us to move 200181905Sed * the write pointer to a new block. 201181905Sed */ 202181905Sed if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) { 203181905Sed /* 204181905Sed * Fast path: zero copy. Remove the first block, 205181905Sed * so we can unlock the TTY temporarily. 206181905Sed */ 207188096Sed TTYINQ_REMOVE_HEAD(ti); 208181905Sed ti->ti_begin = 0; 209181905Sed 210181905Sed /* 211181905Sed * Because we remove the first block, we must 212181905Sed * fix up the block offsets. 213181905Sed */ 214181905Sed#define CORRECT_BLOCK(t) do { \ 215188096Sed if (t <= TTYINQ_DATASIZE) \ 216181905Sed t = 0; \ 217188096Sed else \ 218181905Sed t -= TTYINQ_DATASIZE; \ 219181905Sed} while (0) 220181905Sed CORRECT_BLOCK(ti->ti_linestart); 221181905Sed CORRECT_BLOCK(ti->ti_reprint); 222181905Sed CORRECT_BLOCK(ti->ti_end); 223181905Sed#undef CORRECT_BLOCK 224181905Sed 225181905Sed /* 226181905Sed * Temporary unlock and copy the data to 227181905Sed * userspace. We may need to flush trailing 228181905Sed * bytes, like EOF characters. 229181905Sed */ 230181905Sed tty_unlock(tp); 231181905Sed error = uiomove(tib->tib_data + cbegin, 232181905Sed clen - flen, uio); 233181905Sed tty_lock(tp); 234181905Sed 235182471Sed /* Block can now be readded to the list. */ 236188096Sed TTYINQ_RECYCLE(ti, tib); 237181905Sed } else { 238181905Sed char ob[TTYINQ_DATASIZE - 1]; 239181905Sed 240181905Sed /* 241181905Sed * Slow path: store data in a temporary buffer. 242181905Sed */ 243181905Sed memcpy(ob, tib->tib_data + cbegin, clen - flen); 244181905Sed ti->ti_begin += clen; 245181905Sed MPASS(ti->ti_begin < TTYINQ_DATASIZE); 246181905Sed 247181905Sed /* Temporary unlock and copy the data to userspace. */ 248181905Sed tty_unlock(tp); 249181905Sed error = uiomove(ob, clen - flen, uio); 250181905Sed tty_lock(tp); 251182471Sed } 252181905Sed 253182471Sed if (error != 0) 254182471Sed return (error); 255182471Sed if (tty_gone(tp)) 256182471Sed return (ENXIO); 257181905Sed } 258181905Sed 259181905Sed return (0); 260181905Sed} 261181905Sed 262181905Sedstatic __inline void 263181905Sedttyinq_set_quotes(struct ttyinq_block *tib, size_t offset, 264181905Sed size_t length, int value) 265181905Sed{ 266181905Sed 267181905Sed if (value) { 268181905Sed /* Set the bits. */ 269181905Sed for (; length > 0; length--, offset++) 270181905Sed SETBIT(tib, offset); 271181905Sed } else { 272181905Sed /* Unset the bits. */ 273181905Sed for (; length > 0; length--, offset++) 274181905Sed CLRBIT(tib, offset); 275181905Sed } 276181905Sed} 277181905Sed 278181905Sedsize_t 279181905Sedttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 280181905Sed{ 281181905Sed const char *cbuf = buf; 282181905Sed struct ttyinq_block *tib; 283181905Sed unsigned int boff; 284181905Sed size_t l; 285223575Sed 286181905Sed while (nbytes > 0) { 287181905Sed boff = ti->ti_end % TTYINQ_DATASIZE; 288181905Sed 289181905Sed if (ti->ti_end == 0) { 290181905Sed /* First time we're being used or drained. */ 291181905Sed MPASS(ti->ti_begin == 0); 292188096Sed tib = ti->ti_firstblock; 293181905Sed if (tib == NULL) { 294181905Sed /* Queue has no blocks. */ 295181905Sed break; 296181905Sed } 297188096Sed ti->ti_lastblock = tib; 298181905Sed } else if (boff == 0) { 299181905Sed /* We reached the end of this block on last write. */ 300188096Sed tib = ti->ti_lastblock->tib_next; 301181905Sed if (tib == NULL) { 302181905Sed /* We've reached the watermark. */ 303181905Sed break; 304181905Sed } 305181905Sed ti->ti_lastblock = tib; 306188096Sed } else { 307188096Sed tib = ti->ti_lastblock; 308181905Sed } 309181905Sed 310181905Sed /* Don't copy more than was requested. */ 311181905Sed l = MIN(nbytes, TTYINQ_DATASIZE - boff); 312181905Sed MPASS(l > 0); 313181905Sed memcpy(tib->tib_data + boff, cbuf, l); 314181905Sed 315181905Sed /* Set the quoting bits for the proper region. */ 316181905Sed ttyinq_set_quotes(tib, boff, l, quote); 317181905Sed 318181905Sed cbuf += l; 319181905Sed nbytes -= l; 320181905Sed ti->ti_end += l; 321181905Sed } 322223575Sed 323181905Sed return (cbuf - (const char *)buf); 324181905Sed} 325181905Sed 326181905Sedint 327181905Sedttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote) 328181905Sed{ 329181905Sed size_t ret; 330181905Sed 331181905Sed if (ttyinq_bytesleft(ti) < nbytes) 332181905Sed return (-1); 333181905Sed 334181905Sed /* We should always be able to write it back. */ 335181905Sed ret = ttyinq_write(ti, buf, nbytes, quote); 336181905Sed MPASS(ret == nbytes); 337181905Sed 338181905Sed return (0); 339181905Sed} 340181905Sed 341181905Sedvoid 342181905Sedttyinq_canonicalize(struct ttyinq *ti) 343181905Sed{ 344181905Sed 345181905Sed ti->ti_linestart = ti->ti_reprint = ti->ti_end; 346181905Sed ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock; 347181905Sed} 348181905Sed 349181905Sedsize_t 350181905Sedttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen, 351181905Sed char *lastc) 352181905Sed{ 353188096Sed struct ttyinq_block *tib = ti->ti_firstblock; 354181905Sed unsigned int boff = ti->ti_begin; 355181905Sed unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart), 356181905Sed ti->ti_begin + maxlen); 357181905Sed 358181905Sed MPASS(maxlen > 0); 359181905Sed 360181905Sed if (tib == NULL) 361181905Sed return (0); 362181905Sed 363181905Sed while (boff < bend) { 364229272Sed if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) { 365181905Sed *lastc = tib->tib_data[boff]; 366181905Sed return (boff - ti->ti_begin + 1); 367181905Sed } 368181905Sed boff++; 369181905Sed } 370181905Sed 371181905Sed /* Not found - just process the entire block. */ 372181905Sed return (bend - ti->ti_begin); 373181905Sed} 374181905Sed 375181905Sedvoid 376181905Sedttyinq_flush(struct ttyinq *ti) 377181905Sed{ 378202583Sed struct ttyinq_block *tib; 379181905Sed 380181905Sed ti->ti_begin = 0; 381181905Sed ti->ti_linestart = 0; 382181905Sed ti->ti_reprint = 0; 383181905Sed ti->ti_end = 0; 384181905Sed 385192544Sed /* Zero all data in the input queue to get rid of passwords. */ 386192544Sed if (ttyinq_flush_secure) { 387192544Sed for (tib = ti->ti_firstblock; tib != NULL; tib = tib->tib_next) 388192544Sed bzero(&tib->tib_data, sizeof tib->tib_data); 389181905Sed } 390181905Sed} 391181905Sed 392181905Sedint 393181905Sedttyinq_peekchar(struct ttyinq *ti, char *c, int *quote) 394181905Sed{ 395181905Sed unsigned int boff; 396181905Sed struct ttyinq_block *tib = ti->ti_lastblock; 397181905Sed 398181905Sed if (ti->ti_linestart == ti->ti_end) 399181905Sed return (-1); 400181905Sed 401181905Sed MPASS(ti->ti_end > 0); 402181905Sed boff = (ti->ti_end - 1) % TTYINQ_DATASIZE; 403181905Sed 404181905Sed *c = tib->tib_data[boff]; 405181905Sed *quote = GETBIT(tib, boff); 406223575Sed 407181905Sed return (0); 408181905Sed} 409181905Sed 410181905Sedvoid 411181905Sedttyinq_unputchar(struct ttyinq *ti) 412181905Sed{ 413181905Sed 414181905Sed MPASS(ti->ti_linestart < ti->ti_end); 415181905Sed 416181905Sed if (--ti->ti_end % TTYINQ_DATASIZE == 0) { 417181905Sed /* Roll back to the previous block. */ 418188096Sed ti->ti_lastblock = ti->ti_lastblock->tib_prev; 419181905Sed /* 420181905Sed * This can only fail if we are unputchar()'ing the 421181905Sed * first character in the queue. 422181905Sed */ 423181905Sed MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0)); 424181905Sed } 425181905Sed} 426181905Sed 427181905Sedvoid 428181905Sedttyinq_reprintpos_set(struct ttyinq *ti) 429181905Sed{ 430181905Sed 431181905Sed ti->ti_reprint = ti->ti_end; 432181905Sed ti->ti_reprintblock = ti->ti_lastblock; 433181905Sed} 434181905Sed 435181905Sedvoid 436181905Sedttyinq_reprintpos_reset(struct ttyinq *ti) 437181905Sed{ 438181905Sed 439181905Sed ti->ti_reprint = ti->ti_linestart; 440181905Sed ti->ti_reprintblock = ti->ti_startblock; 441181905Sed} 442181905Sed 443181905Sedstatic void 444181905Sedttyinq_line_iterate(struct ttyinq *ti, 445181905Sed ttyinq_line_iterator_t *iterator, void *data, 446181905Sed unsigned int offset, struct ttyinq_block *tib) 447181905Sed{ 448181905Sed unsigned int boff; 449181905Sed 450181905Sed /* Use the proper block when we're at the queue head. */ 451181905Sed if (offset == 0) 452188096Sed tib = ti->ti_firstblock; 453181905Sed 454181905Sed /* Iterate all characters and call the iterator function. */ 455181905Sed for (; offset < ti->ti_end; offset++) { 456181905Sed boff = offset % TTYINQ_DATASIZE; 457181905Sed MPASS(tib != NULL); 458181905Sed 459181905Sed /* Call back the iterator function. */ 460181905Sed iterator(data, tib->tib_data[boff], GETBIT(tib, boff)); 461181905Sed 462181905Sed /* Last byte iterated - go to the next block. */ 463181905Sed if (boff == TTYINQ_DATASIZE - 1) 464188096Sed tib = tib->tib_next; 465181905Sed MPASS(tib != NULL); 466181905Sed } 467181905Sed} 468181905Sed 469181905Sedvoid 470181905Sedttyinq_line_iterate_from_linestart(struct ttyinq *ti, 471181905Sed ttyinq_line_iterator_t *iterator, void *data) 472181905Sed{ 473181905Sed 474181905Sed ttyinq_line_iterate(ti, iterator, data, 475181905Sed ti->ti_linestart, ti->ti_startblock); 476181905Sed} 477181905Sed 478181905Sedvoid 479181905Sedttyinq_line_iterate_from_reprintpos(struct ttyinq *ti, 480181905Sed ttyinq_line_iterator_t *iterator, void *data) 481181905Sed{ 482181905Sed 483181905Sed ttyinq_line_iterate(ti, iterator, data, 484181905Sed ti->ti_reprint, ti->ti_reprintblock); 485181905Sed} 486181905Sed 487181905Sedstatic void 488181905Sedttyinq_startup(void *dummy) 489181905Sed{ 490181905Sed 491181905Sed ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block), 492181905Sed NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0); 493181905Sed} 494181905Sed 495181905SedSYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL); 496