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