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
66static int ttyinq_flush_secure = 1;
67SYSCTL_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
79struct 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
86static 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
117int
118ttyinq_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
149void
150ttyinq_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
165int
166ttyinq_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
264static __inline void
265ttyinq_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
280size_t
281ttyinq_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
328int
329ttyinq_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
343void
344ttyinq_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
351size_t
352ttyinq_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
377void
378ttyinq_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
394int
395ttyinq_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
412void
413ttyinq_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
429void
430ttyinq_reprintpos_set(struct ttyinq *ti)
431{
432
433	ti->ti_reprint = ti->ti_end;
434	ti->ti_reprintblock = ti->ti_lastblock;
435}
436
437void
438ttyinq_reprintpos_reset(struct ttyinq *ti)
439{
440
441	ti->ti_reprint = ti->ti_linestart;
442	ti->ti_reprintblock = ti->ti_startblock;
443}
444
445static void
446ttyinq_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
471void
472ttyinq_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
480void
481ttyinq_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
489static void
490ttyinq_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
497SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL);
498