1 /*
2 * Copyright (c) 2000-2006 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 */
28 /* Copyright (c) 1997 Apple Computer, Inc. All Rights Reserved */
29 /*
30 * Copyright (c) 1993, 1994 Theo de Raadt
31 * All rights reserved.
32 *
33 * Redistribution and use in source and binary forms, with or without
34 * modification, are permitted provided that the following conditions
35 * are met:
36 * 1. Redistributions of source code must retain the above copyright
37 * notice unmodified, this list of conditions, and the following
38 * disclaimer.
39 * 2. Redistributions in binary form must reproduce the above copyright
40 * notice, this list of conditions and the following disclaimer in the
41 * documentation and/or other materials provided with the distribution.
42 *
43 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
44 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
45 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
46 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
47 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
48 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
49 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
50 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
51 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
52 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
53 * SUCH DAMAGE.
54 *
55 */
56
57 /*
58 * We use the NetBSD based clist system, it is much more efficient than the
59 * old style clist stuff used by free bsd.
60 */
61
62 #include <sys/param.h>
63 #include <sys/systm.h>
64 #include <sys/ioctl.h>
65 #include <sys/tty.h>
66 #include <sys/malloc.h>
67
68
69 /*
70 * At compile time, choose:
71 * There are two ways the TTY_QUOTE bit can be stored. If QBITS is
72 * defined we allocate an array of bits -- 1/8th as much memory but
73 * setbit(), clrbit(), and isset() take more cpu. If QBITS is
74 * undefined, we just use an array of bytes.
75 *
76 * If TTY_QUOTE functionality isn't required by a line discipline,
77 * it can free c_cq and set it to NULL. This speeds things up,
78 * and also does not use any extra memory. This is useful for (say)
79 * a SLIP line discipline that wants a 32K ring buffer for data
80 * but doesn't need quoting.
81 */
82 #define QBITS
83
84 #ifdef QBITS
85 #define QMEM(n) ((((n)-1)/NBBY)+1)
86 #else
87 #define QMEM(n) (n)
88 #endif
89
90
91 /*
92 * Initialize clists.
93 */
94 void
cinit(void)95 cinit(void)
96 {
97 }
98
99 /*
100 * Initialize a particular clist. Ok, they are really ring buffers,
101 * of the specified length, with/without quoting support.
102 */
103 int
clalloc(struct clist * clp,int size,int quot)104 clalloc(struct clist *clp, int size, int quot)
105 {
106 clp->c_cs = kalloc_data(size, Z_WAITOK | Z_ZERO);
107 if (!clp->c_cs) {
108 return -1;
109 }
110
111 if (quot) {
112 clp->c_cq = kalloc_data(QMEM(size), Z_WAITOK | Z_ZERO);
113 if (!clp->c_cq) {
114 kfree_data(clp->c_cs, size);
115 return -1;
116 }
117 } else {
118 clp->c_cq = (u_char *)0;
119 }
120
121 clp->c_cf = clp->c_cl = (u_char *)0;
122 clp->c_ce = clp->c_cs + size;
123 clp->c_cn = size;
124 clp->c_cc = 0;
125 return 0;
126 }
127
128 void
clfree(struct clist * clp)129 clfree(struct clist *clp)
130 {
131 if (clp->c_cs) {
132 kfree_data(clp->c_cs, clp->c_cn);
133 }
134 if (clp->c_cq) {
135 kfree_data(clp->c_cq, QMEM(clp->c_cn));
136 }
137 clp->c_cs = clp->c_cq = (u_char *)0;
138 }
139
140
141 /*
142 * Get a character from a clist.
143 */
144 int
getc(struct clist * clp)145 getc(struct clist *clp)
146 {
147 int c = -1;
148
149 if (clp->c_cc == 0) {
150 goto out;
151 }
152
153 c = *clp->c_cf & 0xff;
154 if (clp->c_cq) {
155 #ifdef QBITS
156 if (isset(clp->c_cq, clp->c_cf - clp->c_cs)) {
157 c |= TTY_QUOTE;
158 }
159 #else
160 if (*(clp->c_cf - clp->c_cs + clp->c_cq)) {
161 c |= TTY_QUOTE;
162 }
163 #endif
164 }
165 if (++clp->c_cf == clp->c_ce) {
166 clp->c_cf = clp->c_cs;
167 }
168 if (--clp->c_cc == 0) {
169 clp->c_cf = clp->c_cl = (u_char *)0;
170 }
171 out:
172 return c;
173 }
174
175 /*
176 * Copy clist to buffer.
177 * Return number of bytes moved.
178 */
179 int
q_to_b(struct clist * clp,u_char * cp,int count)180 q_to_b(struct clist *clp, u_char *cp, int count)
181 {
182 size_t cc;
183 u_char *p = cp;
184
185 /* optimize this while loop */
186 while (count > 0 && clp->c_cc > 0) {
187 cc = clp->c_cl - clp->c_cf;
188 if (clp->c_cf >= clp->c_cl) {
189 cc = clp->c_ce - clp->c_cf;
190 }
191 if (cc > INT_MAX || (int)cc > count) {
192 cc = count;
193 }
194 bcopy(clp->c_cf, p, cc);
195 count -= cc;
196 p += cc;
197 clp->c_cc -= cc;
198 clp->c_cf += cc;
199 if (clp->c_cf == clp->c_ce) {
200 clp->c_cf = clp->c_cs;
201 }
202 }
203 if (clp->c_cc == 0) {
204 clp->c_cf = clp->c_cl = (u_char *)0;
205 }
206 return (int)MIN(INT32_MAX, p - cp);
207 }
208
209 /*
210 * Return count of contiguous characters in clist.
211 * Stop counting if flag&character is non-null.
212 */
213 int
ndqb(struct clist * clp,int flag)214 ndqb(struct clist *clp, int flag)
215 {
216 size_t count = 0;
217 size_t i;
218 int cc;
219
220 if ((cc = clp->c_cc) == 0) {
221 goto out;
222 }
223
224 if (flag == 0) {
225 count = clp->c_cl - clp->c_cf;
226 if (count <= 0) {
227 count = clp->c_ce - clp->c_cf;
228 }
229 goto out;
230 }
231
232 i = clp->c_cf - clp->c_cs;
233 if (i > INT_MAX) {
234 return 0;
235 }
236 if (flag & TTY_QUOTE) {
237 while (cc-- > 0 && !(clp->c_cs[i++] & (flag & ~TTY_QUOTE) ||
238 isset(clp->c_cq, i))) {
239 count++;
240 if ((int)i == clp->c_cn) {
241 break;
242 }
243 }
244 } else {
245 while (cc-- > 0 && !(clp->c_cs[i++] & flag)) {
246 count++;
247 if ((int)i == clp->c_cn) {
248 break;
249 }
250 }
251 }
252 out:
253 if (count > INT_MAX) {
254 return 0;
255 }
256 return (int)count;
257 }
258
259 /*
260 * Flush count bytes from clist.
261 */
262 void
ndflush(struct clist * clp,int count)263 ndflush(struct clist *clp, int count)
264 {
265 size_t cc;
266
267 if (count == clp->c_cc) {
268 clp->c_cc = 0;
269 clp->c_cf = clp->c_cl = (u_char *)0;
270 return;
271 }
272 /* optimize this while loop */
273 while (count > 0 && clp->c_cc > 0) {
274 cc = clp->c_cl - clp->c_cf;
275 if (clp->c_cf >= clp->c_cl) {
276 cc = clp->c_ce - clp->c_cf;
277 }
278 if (cc > INT_MAX || (int)cc > count) {
279 cc = count;
280 }
281 count -= cc;
282 clp->c_cc -= cc;
283 clp->c_cf += cc;
284 if (clp->c_cf == clp->c_ce) {
285 clp->c_cf = clp->c_cs;
286 }
287 }
288 if (clp->c_cc == 0) {
289 clp->c_cf = clp->c_cl = (u_char *)0;
290 }
291 }
292
293 /*
294 * Put a character into the output queue.
295 */
296 int
putc(int c,struct clist * clp)297 putc(int c, struct clist *clp)
298 {
299 size_t i;
300
301 if (clp->c_cc == 0) {
302 if (!clp->c_cs) {
303 #if DIAGNOSTIC
304 //printf("putc: required clalloc\n");
305 #endif
306 if (clalloc(clp, 1024, 1)) {
307 return -1;
308 }
309 }
310 clp->c_cf = clp->c_cl = clp->c_cs;
311 }
312
313 if (clp->c_cc == clp->c_cn) {
314 return -1;
315 }
316
317 *clp->c_cl = c & 0xff;
318 i = clp->c_cl - clp->c_cs;
319 if (i > INT_MAX) {
320 return -1;
321 }
322 if (clp->c_cq) {
323 #ifdef QBITS
324 if (c & TTY_QUOTE) {
325 setbit(clp->c_cq, i);
326 } else {
327 clrbit(clp->c_cq, i);
328 }
329 #else
330 q = clp->c_cq + i;
331 *q = (c & TTY_QUOTE) ? 1 : 0;
332 #endif
333 }
334 clp->c_cc++;
335 clp->c_cl++;
336 if (clp->c_cl == clp->c_ce) {
337 clp->c_cl = clp->c_cs;
338 }
339 return 0;
340 }
341
342 #ifdef QBITS
343 /*
344 * optimized version of
345 *
346 * for (i = 0; i < len; i++)
347 * clrbit(cp, off + len);
348 */
349 void
clrbits(u_char * cp,int off,int len)350 clrbits(u_char *cp, int off, int len)
351 {
352 int sby, sbi, eby, ebi;
353 int i;
354 u_char mask;
355
356 if (len == 1) {
357 clrbit(cp, off);
358 return;
359 }
360
361 sby = off / NBBY;
362 sbi = off % NBBY;
363 eby = (off + len) / NBBY;
364 ebi = (off + len) % NBBY;
365 if (sby == eby) {
366 mask = (u_char)(((1 << (ebi - sbi)) - 1) << sbi);
367 cp[sby] &= ~mask;
368 } else {
369 mask = (u_char)((1 << sbi) - 1);
370 cp[sby++] &= mask;
371
372 mask = (u_char)((1 << ebi) - 1);
373 /* handle remainder bits, if any, for a non-0 ebi value */
374 if (mask) {
375 cp[eby] &= ~mask;
376 }
377
378 for (i = sby; i < eby; i++) {
379 cp[i] = 0x00;
380 }
381 }
382 }
383 #endif
384
385 /*
386 * Copy buffer to clist.
387 * Return number of bytes not transfered.
388 */
389 int
b_to_q(const u_char * cp,int count,struct clist * clp)390 b_to_q(const u_char *cp, int count, struct clist *clp)
391 {
392 size_t cc;
393 const u_char *p = cp;
394
395 if (count <= 0) {
396 return 0;
397 }
398
399
400 if (clp->c_cc == 0) {
401 if (!clp->c_cs) {
402 #if DIAGNOSTIC
403 printf("b_to_q: required clalloc\n");
404 #endif
405 if (clalloc(clp, 1024, 1)) {
406 goto out;
407 }
408 }
409 clp->c_cf = clp->c_cl = clp->c_cs;
410 }
411
412 if (clp->c_cc == clp->c_cn) {
413 goto out;
414 }
415
416 /* optimize this while loop */
417 while (count > 0 && clp->c_cc < clp->c_cn) {
418 cc = clp->c_ce - clp->c_cl;
419 if (clp->c_cf > clp->c_cl) {
420 cc = clp->c_cf - clp->c_cl;
421 }
422 if (cc > INT_MAX || (int)cc > count) {
423 cc = count;
424 }
425 bcopy(p, clp->c_cl, cc);
426 if (clp->c_cq) {
427 #ifdef QBITS
428 if (clp->c_cl - clp->c_cs > INT_MAX || cc > INT_MAX) {
429 count = 0;
430 goto out;
431 }
432 clrbits(clp->c_cq, (int)(clp->c_cl - clp->c_cs), (int)cc);
433 #else
434 bzero(clp->c_cl - clp->c_cs + clp->c_cq, cc);
435 #endif
436 }
437 p += cc;
438 count -= cc;
439 clp->c_cc += cc;
440 clp->c_cl += cc;
441 if (clp->c_cl == clp->c_ce) {
442 clp->c_cl = clp->c_cs;
443 }
444 }
445 out:
446 return count;
447 }
448
449 static int cc;
450
451 /*
452 * Given a non-NULL pointer into the clist return the pointer
453 * to the next character in the list or return NULL if no more chars.
454 *
455 * Callers must not allow getc's to happen between firstc's and getc's
456 * so that the pointer becomes invalid. Note that interrupts are NOT
457 * masked.
458 */
459 u_char *
nextc(struct clist * clp,u_char * cp,int * c)460 nextc(struct clist *clp, u_char *cp, int *c)
461 {
462 if (clp->c_cf == cp) {
463 /*
464 * First time initialization.
465 */
466 cc = clp->c_cc;
467 }
468 if (cc == 0 || cp == NULL) {
469 return NULL;
470 }
471 if (--cc == 0) {
472 return NULL;
473 }
474 if (++cp == clp->c_ce) {
475 cp = clp->c_cs;
476 }
477 *c = *cp & 0xff;
478 if (clp->c_cq) {
479 #ifdef QBITS
480 if (isset(clp->c_cq, cp - clp->c_cs)) {
481 *c |= TTY_QUOTE;
482 }
483 #else
484 if (*(clp->c_cf - clp->c_cs + clp->c_cq)) {
485 *c |= TTY_QUOTE;
486 }
487 #endif
488 }
489 return cp;
490 }
491
492 /*
493 * Given a non-NULL pointer into the clist return the pointer
494 * to the first character in the list or return NULL if no more chars.
495 *
496 * Callers must not allow getc's to happen between firstc's and getc's
497 * so that the pointer becomes invalid. Note that interrupts are NOT
498 * masked.
499 *
500 * *c is set to the NEXT character
501 */
502 u_char *
firstc(struct clist * clp,int * c)503 firstc(struct clist *clp, int *c)
504 {
505 u_char *cp;
506
507 cc = clp->c_cc;
508 if (cc == 0) {
509 return NULL;
510 }
511 cp = clp->c_cf;
512 *c = *cp & 0xff;
513 if (clp->c_cq) {
514 #ifdef QBITS
515 if (isset(clp->c_cq, cp - clp->c_cs)) {
516 *c |= TTY_QUOTE;
517 }
518 #else
519 if (*(cp - clp->c_cs + clp->c_cq)) {
520 *c |= TTY_QUOTE;
521 }
522 #endif
523 }
524 return clp->c_cf;
525 }
526
527 /*
528 * Remove the last character in the clist and return it.
529 */
530 int
unputc(struct clist * clp)531 unputc(struct clist *clp)
532 {
533 unsigned int c = -1;
534
535 if (clp->c_cc == 0) {
536 goto out;
537 }
538
539 if (clp->c_cl == clp->c_cs) {
540 clp->c_cl = clp->c_ce - 1;
541 } else {
542 --clp->c_cl;
543 }
544 clp->c_cc--;
545
546 c = *clp->c_cl & 0xff;
547 if (clp->c_cq) {
548 #ifdef QBITS
549 if (isset(clp->c_cq, clp->c_cl - clp->c_cs)) {
550 c |= TTY_QUOTE;
551 }
552 #else
553 if (*(clp->c_cf - clp->c_cs + clp->c_cq)) {
554 c |= TTY_QUOTE;
555 }
556 #endif
557 }
558 if (clp->c_cc == 0) {
559 clp->c_cf = clp->c_cl = (u_char *)0;
560 }
561 out:
562 return c;
563 }
564
565 /*
566 * Put the chars in the from queue on the end of the to queue.
567 */
568 void
catq(struct clist * from,struct clist * to)569 catq(struct clist *from, struct clist *to)
570 {
571 int c;
572
573 while ((c = getc(from)) != -1) {
574 putc(c, to);
575 }
576 }
577