sys/kern/tty_inq.c

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