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