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
63 static int ttyinq_flush_secure = 1;
64 SYSCTL_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
76 struct 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
83 static 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
114 int
ttyinq_setsize(struct ttyinq * ti,struct tty * tp,size_t size)115 ttyinq_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
146 void
ttyinq_free(struct ttyinq * ti)147 ttyinq_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
162 int
ttyinq_read_uio(struct ttyinq * ti,struct tty * tp,struct uio * uio,size_t rlen,size_t flen)163 ttyinq_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
270 static __inline void
ttyinq_set_quotes(struct ttyinq_block * tib,size_t offset,size_t length,int value)271 ttyinq_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
286 size_t
ttyinq_write(struct ttyinq * ti,const void * buf,size_t nbytes,int quote)287 ttyinq_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
334 int
ttyinq_write_nofrag(struct ttyinq * ti,const void * buf,size_t nbytes,int quote)335 ttyinq_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
349 void
ttyinq_canonicalize(struct ttyinq * ti)350 ttyinq_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 */
361 void
ttyinq_canonicalize_break(struct ttyinq * ti,const char * breakc)362 ttyinq_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
406 size_t
ttyinq_findchar(struct ttyinq * ti,const char * breakc,size_t maxlen,char * lastc)407 ttyinq_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
432 void
ttyinq_flush(struct ttyinq * ti)433 ttyinq_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
449 int
ttyinq_peekchar(struct ttyinq * ti,char * c,int * quote)450 ttyinq_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
467 void
ttyinq_unputchar(struct ttyinq * ti)468 ttyinq_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
484 void
ttyinq_reprintpos_set(struct ttyinq * ti)485 ttyinq_reprintpos_set(struct ttyinq *ti)
486 {
487
488 ti->ti_reprint = ti->ti_end;
489 ti->ti_reprintblock = ti->ti_lastblock;
490 }
491
492 void
ttyinq_reprintpos_reset(struct ttyinq * ti)493 ttyinq_reprintpos_reset(struct ttyinq *ti)
494 {
495
496 ti->ti_reprint = ti->ti_linestart;
497 ti->ti_reprintblock = ti->ti_startblock;
498 }
499
500 static void
ttyinq_line_iterate(struct ttyinq * ti,ttyinq_line_iterator_t * iterator,void * data,unsigned int offset,struct ttyinq_block * tib)501 ttyinq_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
525 void
ttyinq_line_iterate_from_linestart(struct ttyinq * ti,ttyinq_line_iterator_t * iterator,void * data)526 ttyinq_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
534 void
ttyinq_line_iterate_from_reprintpos(struct ttyinq * ti,ttyinq_line_iterator_t * iterator,void * data)535 ttyinq_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
543 static void
ttyinq_startup(void * dummy)544 ttyinq_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
551 SYSINIT(ttyinq, SI_SUB_DRIVERS, SI_ORDER_FIRST, ttyinq_startup, NULL);
552