2 * Copyright (c) 2008 Ed Schouten <ed@FreeBSD.org>
5 * Portions of this software were developed under sponsorship from Snow
6 * B.V., the Netherlands.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
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.
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
30 #include <sys/cdefs.h>
31 __FBSDID("$FreeBSD$");
33 #include <sys/param.h>
34 #include <sys/kernel.h>
36 #include <sys/queue.h>
37 #include <sys/sysctl.h>
38 #include <sys/systm.h>
45 * TTY input queue buffering.
47 * Unlike the output queue, the input queue has more features that are
48 * needed to properly implement various features offered by the TTY
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
60 * In most cases, there is probably less input than output, so unlike
61 * the outq, we'll stick to 128 byte blocks here.
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");
72 #define TTYINQ_QUOTESIZE (TTYINQ_DATASIZE / BMSIZE)
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)))
82 struct ttyinq_block *tib_prev;
83 struct ttyinq_block *tib_next;
84 uint32_t tib_quotes[TTYINQ_QUOTESIZE];
85 char tib_data[TTYINQ_DATASIZE];
88 static uma_zone_t ttyinq_zone;
90 #define TTYINQ_INSERT_TAIL(ti, tib) do { \
91 if (ti->ti_end == 0) { \
92 tib->tib_prev = NULL; \
93 tib->tib_next = ti->ti_firstblock; \
94 ti->ti_firstblock = tib; \
96 tib->tib_prev = ti->ti_lastblock; \
97 tib->tib_next = ti->ti_lastblock->tib_next; \
98 ti->ti_lastblock->tib_next = tib; \
100 if (tib->tib_next != NULL) \
101 tib->tib_next->tib_prev = tib; \
105 #define TTYINQ_REMOVE_HEAD(ti) do { \
106 ti->ti_firstblock = ti->ti_firstblock->tib_next; \
107 if (ti->ti_firstblock != NULL) \
108 ti->ti_firstblock->tib_prev = NULL; \
112 #define TTYINQ_RECYCLE(ti, tib) do { \
113 if (ti->ti_quota <= ti->ti_nblocks) \
114 uma_zfree(ttyinq_zone, tib); \
116 TTYINQ_INSERT_TAIL(ti, tib); \
120 ttyinq_setsize(struct ttyinq *ti, struct tty *tp, size_t size)
122 struct ttyinq_block *tib;
124 ti->ti_quota = howmany(size, TTYINQ_DATASIZE);
126 while (ti->ti_quota > ti->ti_nblocks) {
128 * List is getting bigger.
129 * Add new blocks to the tail of the list.
131 * We must unlock the TTY temporarily, because we need
132 * to allocate memory. This won't be a problem, because
133 * in the worst case, another thread ends up here, which
134 * may cause us to allocate too many blocks, but this
135 * will be caught by the loop below.
138 tib = uma_zalloc(ttyinq_zone, M_WAITOK);
141 TTYINQ_INSERT_TAIL(ti, tib);
146 ttyinq_free(struct ttyinq *ti)
148 struct ttyinq_block *tib;
153 while ((tib = ti->ti_firstblock) != NULL) {
154 TTYINQ_REMOVE_HEAD(ti);
155 uma_zfree(ttyinq_zone, tib);
158 MPASS(ti->ti_nblocks == 0);
162 ttyinq_read_uio(struct ttyinq *ti, struct tty *tp, struct uio *uio,
163 size_t rlen, size_t flen)
166 MPASS(rlen <= uio->uio_resid);
170 struct ttyinq_block *tib;
171 size_t cbegin, cend, clen;
173 /* See if there still is data. */
174 if (ti->ti_begin == ti->ti_linestart)
176 tib = ti->ti_firstblock;
181 * The end address should be the lowest of these three:
182 * - The write pointer
183 * - The blocksize - we can't read beyond the block
184 * - The end address if we could perform the full read
186 cbegin = ti->ti_begin;
187 cend = MIN(MIN(ti->ti_linestart, ti->ti_begin + rlen),
189 clen = cend - cbegin;
194 * We can prevent buffering in some cases:
195 * - We need to read the block until the end.
196 * - We don't need to read the block until the end, but
197 * there is no data beyond it, which allows us to move
198 * the write pointer to a new block.
200 if (cend == TTYINQ_DATASIZE || cend == ti->ti_end) {
201 atomic_add_long(&ttyinq_nfast, 1);
204 * Fast path: zero copy. Remove the first block,
205 * so we can unlock the TTY temporarily.
207 TTYINQ_REMOVE_HEAD(ti);
211 * Because we remove the first block, we must
212 * fix up the block offsets.
214 #define CORRECT_BLOCK(t) do { \
215 if (t <= TTYINQ_DATASIZE) \
218 t -= TTYINQ_DATASIZE; \
220 CORRECT_BLOCK(ti->ti_linestart);
221 CORRECT_BLOCK(ti->ti_reprint);
222 CORRECT_BLOCK(ti->ti_end);
226 * Temporary unlock and copy the data to
227 * userspace. We may need to flush trailing
228 * bytes, like EOF characters.
231 error = uiomove(tib->tib_data + cbegin,
235 /* Block can now be readded to the list. */
236 TTYINQ_RECYCLE(ti, tib);
238 char ob[TTYINQ_DATASIZE - 1];
239 atomic_add_long(&ttyinq_nslow, 1);
242 * Slow path: store data in a temporary buffer.
244 memcpy(ob, tib->tib_data + cbegin, clen - flen);
245 ti->ti_begin += clen;
246 MPASS(ti->ti_begin < TTYINQ_DATASIZE);
248 /* Temporary unlock and copy the data to userspace. */
250 error = uiomove(ob, clen - flen, uio);
264 ttyinq_set_quotes(struct ttyinq_block *tib, size_t offset,
265 size_t length, int value)
270 for (; length > 0; length--, offset++)
273 /* Unset the bits. */
274 for (; length > 0; length--, offset++)
280 ttyinq_write(struct ttyinq *ti, const void *buf, size_t nbytes, int quote)
282 const char *cbuf = buf;
283 struct ttyinq_block *tib;
288 boff = ti->ti_end % TTYINQ_DATASIZE;
290 if (ti->ti_end == 0) {
291 /* First time we're being used or drained. */
292 MPASS(ti->ti_begin == 0);
293 tib = ti->ti_firstblock;
295 /* Queue has no blocks. */
298 ti->ti_lastblock = tib;
299 } else if (boff == 0) {
300 /* We reached the end of this block on last write. */
301 tib = ti->ti_lastblock->tib_next;
303 /* We've reached the watermark. */
306 ti->ti_lastblock = tib;
308 tib = ti->ti_lastblock;
311 /* Don't copy more than was requested. */
312 l = MIN(nbytes, TTYINQ_DATASIZE - boff);
314 memcpy(tib->tib_data + boff, cbuf, l);
316 /* Set the quoting bits for the proper region. */
317 ttyinq_set_quotes(tib, boff, l, quote);
324 return (cbuf - (const char *)buf);
328 ttyinq_write_nofrag(struct ttyinq *ti, const void *buf, size_t nbytes, int quote)
332 if (ttyinq_bytesleft(ti) < nbytes)
335 /* We should always be able to write it back. */
336 ret = ttyinq_write(ti, buf, nbytes, quote);
337 MPASS(ret == nbytes);
343 ttyinq_canonicalize(struct ttyinq *ti)
346 ti->ti_linestart = ti->ti_reprint = ti->ti_end;
347 ti->ti_startblock = ti->ti_reprintblock = ti->ti_lastblock;
351 ttyinq_findchar(struct ttyinq *ti, const char *breakc, size_t maxlen,
354 struct ttyinq_block *tib = ti->ti_firstblock;
355 unsigned int boff = ti->ti_begin;
356 unsigned int bend = MIN(MIN(TTYINQ_DATASIZE, ti->ti_linestart),
357 ti->ti_begin + maxlen);
364 while (boff < bend) {
365 if (index(breakc, tib->tib_data[boff]) && !GETBIT(tib, boff)) {
366 *lastc = tib->tib_data[boff];
367 return (boff - ti->ti_begin + 1);
372 /* Not found - just process the entire block. */
373 return (bend - ti->ti_begin);
377 ttyinq_flush(struct ttyinq *ti)
381 ti->ti_linestart = 0;
388 ttyinq_flush_safe(struct ttyinq *ti)
390 struct ttyinq_block *tib;
394 /* Zero all data in the input queue to make it more safe */
395 TAILQ_FOREACH(tib, &ti->ti_list, tib_list) {
396 bzero(&tib->tib_quotes, sizeof tib->tib_quotes);
397 bzero(&tib->tib_data, sizeof tib->tib_data);
403 ttyinq_peekchar(struct ttyinq *ti, char *c, int *quote)
406 struct ttyinq_block *tib = ti->ti_lastblock;
408 if (ti->ti_linestart == ti->ti_end)
411 MPASS(ti->ti_end > 0);
412 boff = (ti->ti_end - 1) % TTYINQ_DATASIZE;
414 *c = tib->tib_data[boff];
415 *quote = GETBIT(tib, boff);
421 ttyinq_unputchar(struct ttyinq *ti)
424 MPASS(ti->ti_linestart < ti->ti_end);
426 if (--ti->ti_end % TTYINQ_DATASIZE == 0) {
427 /* Roll back to the previous block. */
428 ti->ti_lastblock = ti->ti_lastblock->tib_prev;
430 * This can only fail if we are unputchar()'ing the
431 * first character in the queue.
433 MPASS((ti->ti_lastblock == NULL) == (ti->ti_end == 0));
438 ttyinq_reprintpos_set(struct ttyinq *ti)
441 ti->ti_reprint = ti->ti_end;
442 ti->ti_reprintblock = ti->ti_lastblock;
446 ttyinq_reprintpos_reset(struct ttyinq *ti)
449 ti->ti_reprint = ti->ti_linestart;
450 ti->ti_reprintblock = ti->ti_startblock;
454 ttyinq_line_iterate(struct ttyinq *ti,
455 ttyinq_line_iterator_t *iterator, void *data,
456 unsigned int offset, struct ttyinq_block *tib)
460 /* Use the proper block when we're at the queue head. */
462 tib = ti->ti_firstblock;
464 /* Iterate all characters and call the iterator function. */
465 for (; offset < ti->ti_end; offset++) {
466 boff = offset % TTYINQ_DATASIZE;
469 /* Call back the iterator function. */
470 iterator(data, tib->tib_data[boff], GETBIT(tib, boff));
472 /* Last byte iterated - go to the next block. */
473 if (boff == TTYINQ_DATASIZE - 1)
480 ttyinq_line_iterate_from_linestart(struct ttyinq *ti,
481 ttyinq_line_iterator_t *iterator, void *data)
484 ttyinq_line_iterate(ti, iterator, data,
485 ti->ti_linestart, ti->ti_startblock);
489 ttyinq_line_iterate_from_reprintpos(struct ttyinq *ti,
490 ttyinq_line_iterator_t *iterator, void *data)
493 ttyinq_line_iterate(ti, iterator, data,
494 ti->ti_reprint, ti->ti_reprintblock);
498 ttyinq_startup(void *dummy)
501 ttyinq_zone = uma_zcreate("ttyinq", sizeof(struct ttyinq_block),
502 NULL, NULL, NULL, NULL, UMA_ALIGN_PTR, 0);
505 SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL);