sys/kern/tty_inq.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause
   3  *
   4  * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
   5  * All rights reserved.
   6  *
   7  * Portions of this software were developed under sponsorship from Snow
   8  * B.V., the Netherlands.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  */
  31
  32 #include <sys/param.h>
  33 #include <sys/kernel.h>
  34 #include <sys/lock.h>
  35 #include <sys/queue.h>
  36 #include <sys/sysctl.h>
  37 #include <sys/systm.h>
  38 #include <sys/tty.h>
  39 #include <sys/uio.h>
  40
  41 #include <vm/uma.h>
  42
  43 /*
  44  * TTY input queue buffering.
  45  *
  46  * Unlike the output queue, the input queue has more features that are
  47  * needed to properly implement various features offered by the TTY
  48  * interface:
  49  *
  50  * - Data can be removed from the tail of the queue, which is used to
  51  *   implement backspace.
  52  * - Once in a while, input has to be `canonicalized'. When ICANON is
  53  *   turned on, this will be done after a CR has been inserted.
  54  *   Otherwise, it should be done after any character has been inserted.
  55  * - The input queue can store one bit per byte, called the quoting bit.
  56  *   This bit is used by TTYDISC to make backspace work on quoted
  57  *   characters.
  58  *
  59  * In most cases, there is probably less input than output, so unlike
  60  * the outq, we'll stick to 128 byte blocks here.
  61  */
  62
  63 static int ttyinq_flush_secure = 1;
  64 SYSCTL_INT(_kern, OID_AUTO, tty_inq_flush_secure, CTLFLAG_RW,
  65         &ttyinq_flush_secure, 0, "Zero buffers while flushing");
  66
  67 #define TTYINQ_QUOTESIZE        (TTYINQ_DATASIZE / BMSIZE)
  68 #define BMSIZE                  32
  69 #define GETBIT(tib,boff) \
  70         ((tib)->tib_quotes[(boff) / BMSIZE] & (1 << ((boff) % BMSIZE)))
  71 #define SETBIT(tib,boff) \
  72         ((tib)->tib_quotes[(boff) / BMSIZE] |= (1 << ((boff) % BMSIZE)))
  73 #define CLRBIT(tib,boff) \
  74         ((tib)->tib_quotes[(boff) / BMSIZE] &= ~(1 << ((boff) % BMSIZE)))
  75
  76 struct ttyinq_block {
  77         struct ttyinq_block     *tib_prev;
  78         struct ttyinq_block     *tib_next;
  79         uint32_t                tib_quotes[TTYINQ_QUOTESIZE];
  80         char                    tib_data[TTYINQ_DATASIZE];
  81 };
  82
  83 static uma_zone_t ttyinq_zone;
  84
  85 #define TTYINQ_INSERT_TAIL(ti, tib) do {                                \
  86         if (ti->ti_end == 0) {                                          \
  87                 tib->tib_prev = NULL;                                   \
  88                 tib->tib_next = ti->ti_firstblock;                      \
  89                 ti->ti_firstblock = tib;                                \
  90         } else {                                                        \
  91                 tib->tib_prev = ti->ti_lastblock;                       \
  92                 tib->tib_next = ti->ti_lastblock->tib_next;             \
  93                 ti->ti_lastblock->tib_next = tib;                       \
  94         }                                                               \
  95         if (tib->tib_next != NULL)                                      \
  96                 tib->tib_next->tib_prev = tib;                          \
  97         ti->ti_nblocks++;                                               \
  98 } while (0)
  99
 100 #define TTYINQ_REMOVE_HEAD(ti) do {                                     \
 101         ti->ti_firstblock = ti->ti_firstblock->tib_next;                \
 102         if (ti->ti_firstblock != NULL)                                  \
 103                 ti->ti_firstblock->tib_prev = NULL;                     \
 104         ti->ti_nblocks--;                                               \
 105 } while (0)
 106
 107 #define TTYINQ_RECYCLE(ti, tib) do {                                    \
 108         if (ti->ti_quota <= ti->ti_nblocks)                             \
 109                 uma_zfree(ttyinq_zone, tib);                            \
 110         else                                                            \
 111                 TTYINQ_INSERT_TAIL(ti, tib);                            \
 112 } while (0)
 113
 114 int
 115 ttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t size)
 116 {
 117         struct ttyinq_block *tib;
 118
 119         ti->ti_quota = howmany(size, TTYINQ_DATASIZE);
 120
 121         while (ti->ti_quota > ti->ti_nblocks) {
 122                 /*
 123                  * List is getting bigger.
 124                  * Add new blocks to the tail of the list.
 125                  *
 126                  * We must unlock the TTY temporarily, because we need
 127                  * to allocate memory. This won't be a problem, because
 128                  * in the worst case, another thread ends up here, which
 129                  * may cause us to allocate too many blocks, but this
 130                  * will be caught by the loop below.
 131                  */
 132                 tty_unlock(tp);
 133                 tib = uma_zalloc(ttyinq_zone, M_WAITOK);
 134                 tty_lock(tp);
 135
 136                 if (tty_gone(tp)) {
 137                         uma_zfree(ttyinq_zone, tib);
 138                         return (ENXIO);
 139                 }
 140
 141                 TTYINQ_INSERT_TAIL(ti, tib);
 142         }
 143         return (0);
 144 }
 145
 146 void
 147 ttyinq_free(struct ttyinq *ti)
 148 {
 149         struct ttyinq_block *tib;
 150
 151         ttyinq_flush(ti);
 152         ti->ti_quota = 0;
 153
 154         while ((tib = ti->ti_firstblock) != NULL) {
 155                 TTYINQ_REMOVE_HEAD(ti);
 156                 uma_zfree(ttyinq_zone, tib);
 157         }
 158
 159         MPASS(ti->ti_nblocks == 0);
 160 }
 161
 162 int
 163 ttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio,
 164     size_t rlen, size_t flen)
 165 {
 166
 167         /* rlen includes flen, flen bytes will be trimmed from the end. */
 168         MPASS(rlen - flen <= uio->uio_resid);
 169
 170         while (rlen > 0) {
 171                 int error;
 172                 struct ttyinq_block *tib;
 173                 size_t cbegin, cend, clen;
 174
 175                 /* See if there still is data. */
 176                 if (ti->ti_begin == ti->ti_linestart)
 177                         return (0);
 178                 tib = ti->ti_firstblock;
 179                 if (tib == NULL)
 180                         return (0);
 181
 182                 /*
 183                  * The end address should be the lowest of these three:
 184                  * - The write pointer
 185                  * - The blocksize - we can't read beyond the block
 186                  * - The end address if we could perform the full read
 187                  */
 188                 cbegin = ti->ti_begin;
 189                 cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen),
 190                     TTYINQ_DATASIZE);
 191                 clen = cend - cbegin;
 192                 MPASS(clen >= flen);
 193                 rlen -= clen;
 194
 195                 /*
 196                  * Caller shouldn't request that we trim anything if we might be
 197                  * reading across blocks.  We could handle it, but today we do
 198                  * not.
 199                  */
 200                 if (flen > 0)
 201                         MPASS(rlen == 0);
 202
 203                 /*
 204                  * We can prevent buffering in some cases:
 205                  * - We need to read the block until the end.
 206                  * - We don't need to read the block until the end, but
 207                  *   there is no data beyond it, which allows us to move
 208                  *   the write pointer to a new block.
 209                  */
 210                 if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) {
 211                         /*
 212                          * Fast path: zero copy. Remove the first block,
 213                          * so we can unlock the TTY temporarily.
 214                          */
 215                         TTYINQ_REMOVE_HEAD(ti);
 216                         ti->ti_begin = 0;
 217
 218                         /*
 219                          * Because we remove the first block, we must
 220                          * fix up the block offsets.
 221                          */
 222 #define CORRECT_BLOCK(t) do {                   \
 223         if (t <= TTYINQ_DATASIZE)               \
 224                 t = 0;                          \
 225         else                                    \
 226                 t -= TTYINQ_DATASIZE;           \
 227 } while (0)
 228                         CORRECT_BLOCK(ti->ti_linestart);
 229                         CORRECT_BLOCK(ti->ti_reprint);
 230                         CORRECT_BLOCK(ti->ti_end);
 231 #undef CORRECT_BLOCK
 232
 233                         /*
 234                          * Temporary unlock and copy the data to
 235                          * userspace. We may need to flush trailing
 236                          * bytes, like EOF characters.
 237                          */
 238                         tty_unlock(tp);
 239                         error = uiomove(tib->tib_data + cbegin,
 240                             clen - flen, uio);
 241                         tty_lock(tp);
 242
 243                         /* Block can now be readded to the list. */
 244                         TTYINQ_RECYCLE(ti, tib);
 245                 } else {
 246                         char ob[TTYINQ_DATASIZE - 1];
 247
 248                         /*
 249                          * Slow path: store data in a temporary buffer.
 250                          */
 251                         memcpy(ob, tib->tib_data + cbegin, clen - flen);
 252                         ti->ti_begin += clen;
 253                         MPASS(ti->ti_begin < TTYINQ_DATASIZE);
 254
 255                         /* Temporary unlock and copy the data to userspace. */
 256                         tty_unlock(tp);
 257                         error = uiomove(ob, clen - flen, uio);
 258                         tty_lock(tp);
 259                 }
 260
 261                 if (error != 0)
 262                         return (error);
 263                 if (tty_gone(tp))
 264                         return (ENXIO);
 265         }
 266
 267         return (0);
 268 }
 269
 270 static __inline void
 271 ttyinq_set_quotes(struct ttyinq_block *tib, size_t offset,
 272     size_t length, int value)
 273 {
 274
 275         if (value) {
 276                 /* Set the bits. */
 277                 for (; length > 0; length--, offset++)
 278                         SETBIT(tib, offset);
 279         } else {
 280                 /* Unset the bits. */
 281                 for (; length > 0; length--, offset++)
 282                         CLRBIT(tib, offset);
 283         }
 284 }
 285
 286 size_t
 287 ttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote)
 288 {
 289         const char *cbuf = buf;
 290         struct ttyinq_block *tib;
 291         unsigned int boff;
 292         size_t l;
 293
 294         while (nbytes > 0) {
 295                 boff = ti->ti_end % TTYINQ_DATASIZE;
 296
 297                 if (ti->ti_end == 0) {
 298                         /* First time we're being used or drained. */
 299                         MPASS(ti->ti_begin == 0);
 300                         tib = ti->ti_firstblock;
 301                         if (tib == NULL) {
 302                                 /* Queue has no blocks. */
 303                                 break;
 304                         }
 305                         ti->ti_lastblock = tib;
 306                 } else if (boff == 0) {
 307                         /* We reached the end of this block on last write. */
 308                         tib = ti->ti_lastblock->tib_next;
 309                         if (tib == NULL) {
 310                                 /* We've reached the watermark. */
 311                                 break;
 312                         }
 313                         ti->ti_lastblock = tib;
 314                 } else {
 315                         tib = ti->ti_lastblock;
 316                 }
 317
 318                 /* Don't copy more than was requested. */
 319                 l = MIN(nbytes, TTYINQ_DATASIZE - boff);
 320                 MPASS(l > 0);
 321                 memcpy(tib->tib_data + boff, cbuf, l);
 322
 323                 /* Set the quoting bits for the proper region. */
 324                 ttyinq_set_quotes(tib, boff, l, quote);
 325
 326                 cbuf += l;
 327                 nbytes -= l;
 328                 ti->ti_end += l;
 329         }
 330
 331         return (cbuf - (const char *)buf);
 332 }
 333
 334 int
 335 ttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote)
 336 {
 337         size_t ret __unused;
 338
 339         if (ttyinq_bytesleft(ti) < nbytes)
 340                 return (-1);
 341
 342         /* We should always be able to write it back. */
 343         ret = ttyinq_write(ti, buf, nbytes, quote);
 344         MPASS(ret == nbytes);
 345
 346         return (0);
 347 }
 348
 349 void
 350 ttyinq_canonicalize(struct ttyinq *ti)
 351 {
 352
 353         ti->ti_linestart = ti->ti_reprint = ti->ti_end;
 354         ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock;
 355 }
 356
 357 /*
 358  * Canonicalize at one of the break characters; we'll work backwards from the
 359  * lastblock to firstblock to try and find the latest one.
 360  */
 361 void
 362 ttyinq_canonicalize_break(struct ttyinq *ti, const char *breakc)
 363 {
 364         struct ttyinq_block *tib = ti->ti_lastblock;
 365         unsigned int canon, off;
 366         unsigned int boff;
 367
 368         /* No block, no change needed. */
 369         if (tib == NULL || ti->ti_end == 0)
 370                 return;
 371
 372         /* Start just past the end... */
 373         off = ti->ti_end;
 374         canon = ti->ti_begin;
 375
 376         while (off > ti->ti_begin) {
 377                 off--;
 378                 boff = off % TTYINQ_DATASIZE;
 379
 380                 if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) {
 381                         canon = off + 1;
 382                         break;
 383                 }
 384
 385                 if (off != ti->ti_begin && boff == 0)
 386                         tib = tib->tib_prev;
 387         }
 388
 389         MPASS(canon > ti->ti_begin || off == ti->ti_begin);
 390
 391         /*
 392          * We should only be able to hit canon == ti_begin if we walked
 393          * everything we have and didn't find any of the break characters, so
 394          * if canon == ti_begin then tib is already the correct block and we
 395          * should avoid touching it.
 396          *
 397          * For all other scenarios, if canon lies on a block boundary then tib
 398          * has already advanced to the previous block.
 399          */
 400         if (canon != ti->ti_begin && (canon % TTYINQ_DATASIZE) == 0)
 401                 tib = tib->tib_next;
 402         ti->ti_linestart = ti->ti_reprint = canon;
 403         ti->ti_startblock = ti->ti_reprintblock = tib;
 404 }
 405
 406 size_t
 407 ttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen,
 408     char *lastc)
 409 {
 410         struct ttyinq_block *tib = ti->ti_firstblock;
 411         unsigned int boff = ti->ti_begin;
 412         unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart),
 413             ti->ti_begin + maxlen);
 414
 415         MPASS(maxlen > 0);
 416
 417         if (tib == NULL)
 418                 return (0);
 419
 420         while (boff < bend) {
 421                 if (strchr(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) {
 422                         *lastc = tib->tib_data[boff];
 423                         return (boff - ti->ti_begin + 1);
 424                 }
 425                 boff++;
 426         }
 427
 428         /* Not found - just process the entire block. */
 429         return (bend - ti->ti_begin);
 430 }
 431
 432 void
 433 ttyinq_flush(struct ttyinq *ti)
 434 {
 435         struct ttyinq_block *tib;
 436
 437         ti->ti_begin = 0;
 438         ti->ti_linestart = 0;
 439         ti->ti_reprint = 0;
 440         ti->ti_end = 0;
 441
 442         /* Zero all data in the input queue to get rid of passwords. */
 443         if (ttyinq_flush_secure) {
 444                 for (tib = ti->ti_firstblock; tib != NULL; tib = tib->tib_next)
 445                         bzero(&tib->tib_data, sizeof tib->tib_data);
 446         }
 447 }
 448
 449 int
 450 ttyinq_peekchar(struct ttyinq *ti, char *c, int *quote)
 451 {
 452         unsigned int boff;
 453         struct ttyinq_block *tib = ti->ti_lastblock;
 454
 455         if (ti->ti_linestart == ti->ti_end)
 456                 return (-1);
 457
 458         MPASS(ti->ti_end > 0);
 459         boff = (ti->ti_end - 1) % TTYINQ_DATASIZE;
 460
 461         *c = tib->tib_data[boff];
 462         *quote = GETBIT(tib, boff);
 463
 464         return (0);
 465 }
 466
 467 void
 468 ttyinq_unputchar(struct ttyinq *ti)
 469 {
 470
 471         MPASS(ti->ti_linestart < ti->ti_end);
 472
 473         if (--ti->ti_end % TTYINQ_DATASIZE == 0) {
 474                 /* Roll back to the previous block. */
 475                 ti->ti_lastblock = ti->ti_lastblock->tib_prev;
 476                 /*
 477                  * This can only fail if we are unputchar()'ing the
 478                  * first character in the queue.
 479                  */
 480                 MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0));
 481         }
 482 }
 483
 484 void
 485 ttyinq_reprintpos_set(struct ttyinq *ti)
 486 {
 487
 488         ti->ti_reprint = ti->ti_end;
 489         ti->ti_reprintblock = ti->ti_lastblock;
 490 }
 491
 492 void
 493 ttyinq_reprintpos_reset(struct ttyinq *ti)
 494 {
 495
 496         ti->ti_reprint = ti->ti_linestart;
 497         ti->ti_reprintblock = ti->ti_startblock;
 498 }
 499
 500 static void
 501 ttyinq_line_iterate(struct ttyinq *ti,
 502     ttyinq_line_iterator_t *iterator, void *data,
 503     unsigned int offset, struct ttyinq_block *tib)
 504 {
 505         unsigned int boff;
 506
 507         /* Use the proper block when we're at the queue head. */
 508         if (offset == 0)
 509                 tib = ti->ti_firstblock;
 510
 511         /* Iterate all characters and call the iterator function. */
 512         for (; offset < ti->ti_end; offset++) {
 513                 boff = offset % TTYINQ_DATASIZE;
 514                 MPASS(tib != NULL);
 515
 516                 /* Call back the iterator function. */
 517                 iterator(data, tib->tib_data[boff], GETBIT(tib, boff));
 518
 519                 /* Last byte iterated - go to the next block. */
 520                 if (boff == TTYINQ_DATASIZE - 1)
 521                         tib = tib->tib_next;
 522         }
 523 }
 524
 525 void
 526 ttyinq_line_iterate_from_linestart(struct ttyinq *ti,
 527     ttyinq_line_iterator_t *iterator, void *data)
 528 {
 529
 530         ttyinq_line_iterate(ti, iterator, data,
 531             ti->ti_linestart, ti->ti_startblock);
 532 }
 533
 534 void
 535 ttyinq_line_iterate_from_reprintpos(struct ttyinq *ti,
 536     ttyinq_line_iterator_t *iterator, void *data)
 537 {
 538
 539         ttyinq_line_iterate(ti, iterator, data,
 540             ti->ti_reprint, ti->ti_reprintblock);
 541 }
 542
 543 static void
 544 ttyinq_startup(void *dummy)
 545 {
 546
 547         ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block),
 548             NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
 549 }
 550
 551 SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL);