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 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");
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 TAILQ_ENTRY(ttyinq_block
) tib_list
;
83 uint32_t tib_quotes
[TTYINQ_QUOTESIZE
];
84 char tib_data
[TTYINQ_DATASIZE
];
87 static uma_zone_t ttyinq_zone
;
90 ttyinq_setsize(struct ttyinq
*ti
, struct tty
*tp
, size_t size
)
92 struct ttyinq_block
*tib
;
94 ti
->ti_quota
= howmany(size
, TTYINQ_DATASIZE
);
96 while (ti
->ti_quota
> ti
->ti_nblocks
) {
98 * List is getting bigger.
99 * Add new blocks to the tail of the list.
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.
108 tib
= uma_zalloc(ttyinq_zone
, M_WAITOK
);
111 TAILQ_INSERT_TAIL(&ti
->ti_list
, tib
, tib_list
);
117 ttyinq_free(struct ttyinq
*ti
)
119 struct ttyinq_block
*tib
;
124 while ((tib
= TAILQ_FIRST(&ti
->ti_list
)) != NULL
) {
125 TAILQ_REMOVE(&ti
->ti_list
, tib
, tib_list
);
126 uma_zfree(ttyinq_zone
, tib
);
130 MPASS(ti
->ti_nblocks
== 0);
134 ttyinq_read_uio(struct ttyinq
*ti
, struct tty
*tp
, struct uio
*uio
,
135 size_t rlen
, size_t flen
)
138 MPASS(rlen
<= uio
->uio_resid
);
142 struct ttyinq_block
*tib
;
143 size_t cbegin
, cend
, clen
;
145 /* See if there still is data. */
146 if (ti
->ti_begin
== ti
->ti_linestart
)
148 tib
= TAILQ_FIRST(&ti
->ti_list
);
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
158 cbegin
= ti
->ti_begin
;
159 cend
= MIN(MIN(ti
->ti_linestart
, ti
->ti_begin
+ rlen
),
161 clen
= cend
- cbegin
;
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.
172 if (cend
== TTYINQ_DATASIZE
|| cend
== ti
->ti_end
) {
173 atomic_add_long(&ttyinq_nfast
, 1);
176 * Fast path: zero copy. Remove the first block,
177 * so we can unlock the TTY temporarily.
179 TAILQ_REMOVE(&ti
->ti_list
, tib
, tib_list
);
184 * Because we remove the first block, we must
185 * fix up the block offsets.
187 #define CORRECT_BLOCK(t) do { \
188 if (t <= TTYINQ_DATASIZE) { \
191 t -= TTYINQ_DATASIZE; \
194 CORRECT_BLOCK(ti
->ti_linestart
);
195 CORRECT_BLOCK(ti
->ti_reprint
);
196 CORRECT_BLOCK(ti
->ti_end
);
200 * Temporary unlock and copy the data to
201 * userspace. We may need to flush trailing
202 * bytes, like EOF characters.
205 error
= uiomove(tib
->tib_data
+ cbegin
,
209 /* Block can now be readded to the list. */
210 if (ti
->ti_quota
<= ti
->ti_nblocks
) {
211 uma_zfree(ttyinq_zone
, tib
);
213 TAILQ_INSERT_TAIL(&ti
->ti_list
, tib
, tib_list
);
217 char ob
[TTYINQ_DATASIZE
- 1];
218 atomic_add_long(&ttyinq_nslow
, 1);
221 * Slow path: store data in a temporary buffer.
223 memcpy(ob
, tib
->tib_data
+ cbegin
, clen
- flen
);
224 ti
->ti_begin
+= clen
;
225 MPASS(ti
->ti_begin
< TTYINQ_DATASIZE
);
227 /* Temporary unlock and copy the data to userspace. */
229 error
= uiomove(ob
, clen
- flen
, uio
);
243 ttyinq_set_quotes(struct ttyinq_block
*tib
, size_t offset
,
244 size_t length
, int value
)
249 for (; length
> 0; length
--, offset
++)
252 /* Unset the bits. */
253 for (; length
> 0; length
--, offset
++)
259 ttyinq_write(struct ttyinq
*ti
, const void *buf
, size_t nbytes
, int quote
)
261 const char *cbuf
= buf
;
262 struct ttyinq_block
*tib
;
267 tib
= ti
->ti_lastblock
;
268 boff
= ti
->ti_end
% TTYINQ_DATASIZE
;
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
);
275 /* Queue has no blocks. */
278 } else if (boff
== 0) {
279 /* We reached the end of this block on last write. */
280 tib
= TAILQ_NEXT(tib
, tib_list
);
282 /* We've reached the watermark. */
285 ti
->ti_lastblock
= tib
;
288 /* Don't copy more than was requested. */
289 l
= MIN(nbytes
, TTYINQ_DATASIZE
- boff
);
291 memcpy(tib
->tib_data
+ boff
, cbuf
, l
);
293 /* Set the quoting bits for the proper region. */
294 ttyinq_set_quotes(tib
, boff
, l
, quote
);
301 return (cbuf
- (const char *)buf
);
305 ttyinq_write_nofrag(struct ttyinq
*ti
, const void *buf
, size_t nbytes
, int quote
)
309 if (ttyinq_bytesleft(ti
) < nbytes
)
312 /* We should always be able to write it back. */
313 ret
= ttyinq_write(ti
, buf
, nbytes
, quote
);
314 MPASS(ret
== nbytes
);
320 ttyinq_canonicalize(struct ttyinq
*ti
)
323 ti
->ti_linestart
= ti
->ti_reprint
= ti
->ti_end
;
324 ti
->ti_startblock
= ti
->ti_reprintblock
= ti
->ti_lastblock
;
328 ttyinq_findchar(struct ttyinq
*ti
, const char *breakc
, size_t maxlen
,
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
);
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);
349 /* Not found - just process the entire block. */
350 return (bend
- ti
->ti_begin
);
354 ttyinq_flush(struct ttyinq
*ti
)
358 ti
->ti_linestart
= 0;
365 ttyinq_flush_safe(struct ttyinq
*ti
)
367 struct ttyinq_block
*tib
;
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
);
380 ttyinq_peekchar(struct ttyinq
*ti
, char *c
, int *quote
)
383 struct ttyinq_block
*tib
= ti
->ti_lastblock
;
385 if (ti
->ti_linestart
== ti
->ti_end
)
388 MPASS(ti
->ti_end
> 0);
389 boff
= (ti
->ti_end
- 1) % TTYINQ_DATASIZE
;
391 *c
= tib
->tib_data
[boff
];
392 *quote
= GETBIT(tib
, boff
);
398 ttyinq_unputchar(struct ttyinq
*ti
)
401 MPASS(ti
->ti_linestart
< ti
->ti_end
);
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
);
408 * This can only fail if we are unputchar()'ing the
409 * first character in the queue.
411 MPASS((ti
->ti_lastblock
== NULL
) == (ti
->ti_end
== 0));
416 ttyinq_reprintpos_set(struct ttyinq
*ti
)
419 ti
->ti_reprint
= ti
->ti_end
;
420 ti
->ti_reprintblock
= ti
->ti_lastblock
;
424 ttyinq_reprintpos_reset(struct ttyinq
*ti
)
427 ti
->ti_reprint
= ti
->ti_linestart
;
428 ti
->ti_reprintblock
= ti
->ti_startblock
;
432 ttyinq_line_iterate(struct ttyinq
*ti
,
433 ttyinq_line_iterator_t
*iterator
, void *data
,
434 unsigned int offset
, struct ttyinq_block
*tib
)
438 /* Use the proper block when we're at the queue head. */
440 tib
= TAILQ_FIRST(&ti
->ti_list
);
442 /* Iterate all characters and call the iterator function. */
443 for (; offset
< ti
->ti_end
; offset
++) {
444 boff
= offset
% TTYINQ_DATASIZE
;
447 /* Call back the iterator function. */
448 iterator(data
, tib
->tib_data
[boff
], GETBIT(tib
, boff
));
450 /* Last byte iterated - go to the next block. */
451 if (boff
== TTYINQ_DATASIZE
- 1)
452 tib
= TAILQ_NEXT(tib
, tib_list
);
458 ttyinq_line_iterate_from_linestart(struct ttyinq
*ti
,
459 ttyinq_line_iterator_t
*iterator
, void *data
)
462 ttyinq_line_iterate(ti
, iterator
, data
,
463 ti
->ti_linestart
, ti
->ti_startblock
);
467 ttyinq_line_iterate_from_reprintpos(struct ttyinq
*ti
,
468 ttyinq_line_iterator_t
*iterator
, void *data
)
471 ttyinq_line_iterate(ti
, iterator
, data
,
472 ti
->ti_reprint
, ti
->ti_reprintblock
);
476 ttyinq_startup(void *dummy
)
479 ttyinq_zone
= uma_zcreate("ttyinq", sizeof(struct ttyinq_block
),
480 NULL
, NULL
, NULL
, NULL
, UMA_ALIGN_PTR
, 0);
483 SYSINIT(ttyinq
, SI_SUB_DRIVERS
, SI_ORDER_FIRST
, ttyinq_startup
, NULL
);