sys/kern/tty_inq.c

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