2 * Copyright (c) 1994, David Greenman
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
16 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
18 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
19 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
20 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
21 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
22 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
23 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
24 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
29 * clist support routines
32 #include <sys/cdefs.h>
33 __FBSDID("$FreeBSD$");
35 #include <sys/param.h>
36 #include <sys/kernel.h>
37 #include <sys/systm.h>
38 #include <sys/malloc.h>
40 #include <sys/clist.h>
42 static void clist_init(void *);
43 SYSINIT(clist, SI_SUB_CLIST, SI_ORDER_FIRST, clist_init, NULL)
45 static struct cblock *cfreelist = 0;
47 static int cslushcount;
50 #ifndef INITIAL_CBLOCKS
51 #define INITIAL_CBLOCKS 50
54 static struct cblock *cblock_alloc(void);
55 static void cblock_alloc_cblocks(int number);
56 static void cblock_free(struct cblock *cblockp);
57 static void cblock_free_cblocks(int number);
63 DB_SHOW_COMMAND(cbstat, cbstat)
68 "tot = %d (active = %d, free = %d (reserved = %d, slush = %d))\n",
69 ctotcount * cbsize, ctotcount * cbsize - cfreecount, cfreecount,
70 cfreecount - cslushcount * cbsize, cslushcount * cbsize);
75 * Called from init_main.c
83 * Allocate an initial base set of cblocks as a 'slush'.
84 * We allocate non-slush cblocks with each initial tty_open() and
85 * deallocate them with each tty_close().
86 * We should adjust the slush allocation. This can't be done in
87 * the i/o routines because they are sometimes called from
88 * interrupt handlers when it may be unsafe to call malloc().
90 cblock_alloc_cblocks(cslushcount = INITIAL_CBLOCKS);
94 * Remove a cblock from the cfreelist queue and return a pointer
97 static __inline struct cblock *
100 struct cblock *cblockp;
104 panic("clist reservation botch");
105 cfreelist = cblockp->c_next;
106 cblockp->c_next = NULL;
107 cfreecount -= CBSIZE;
112 * Add a cblock to the cfreelist queue.
116 struct cblock *cblockp;
118 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1))
119 bzero(cblockp->c_quote, sizeof cblockp->c_quote);
120 cblockp->c_next = cfreelist;
122 cfreecount += CBSIZE;
126 * Allocate some cblocks for the cfreelist queue.
129 cblock_alloc_cblocks(number)
135 for (i = 0; i < number; ++i) {
136 cbp = malloc(sizeof *cbp, M_TTYS, M_NOWAIT);
139 "cblock_alloc_cblocks: M_NOWAIT malloc failed, trying M_WAITOK\n");
140 cbp = malloc(sizeof *cbp, M_TTYS, M_WAITOK);
143 * Freed cblocks have zero quotes and garbage elsewhere.
144 * Set the may-have-quote bit to force zeroing the quotes.
146 setbit(cbp->c_quote, CBQSIZE * NBBY - 1);
153 * Set the cblock allocation policy for a clist.
154 * Must be called in process context at spltty().
157 clist_alloc_cblocks(clistp, ccmax, ccreserved)
158 struct clist *clistp;
165 * Allow for wasted space at the head.
170 ccreserved += CBSIZE - 1;
172 clistp->c_cbmax = roundup(ccmax, CBSIZE) / CBSIZE;
173 dcbr = roundup(ccreserved, CBSIZE) / CBSIZE - clistp->c_cbreserved;
175 cblock_alloc_cblocks(dcbr);
177 if (clistp->c_cbreserved + dcbr < clistp->c_cbcount)
178 dcbr = clistp->c_cbcount - clistp->c_cbreserved;
179 cblock_free_cblocks(-dcbr);
181 clistp->c_cbreserved += dcbr;
185 * Free some cblocks from the cfreelist queue back to the
186 * system malloc pool.
189 cblock_free_cblocks(number)
194 for (i = 0; i < number; ++i)
195 free(cblock_alloc(), M_TTYS);
200 * Free the cblocks reserved for a clist.
201 * Must be called at spltty().
204 clist_free_cblocks(clistp)
205 struct clist *clistp;
207 if (clistp->c_cbcount != 0)
208 panic("freeing active clist cblocks");
209 cblock_free_cblocks(clistp->c_cbreserved);
211 clistp->c_cbreserved = 0;
215 * Get a character from the head of a clist.
219 struct clist *clistp;
223 struct cblock *cblockp;
227 /* If there are characters in the list, get one */
229 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
230 chr = (u_char)*clistp->c_cf;
233 * If this char is quoted, set the flag.
235 if (isset(cblockp->c_quote, clistp->c_cf - (char *)cblockp->c_info))
239 * Advance to next character.
244 * If we have advanced the 'first' character pointer
245 * past the end of this cblock, advance to the next one.
246 * If there are no more characters, set the first and
247 * last pointers to NULL. In either case, free the
250 if ((clistp->c_cf >= (char *)(cblockp+1)) || (clistp->c_cc == 0)) {
251 if (clistp->c_cc > 0) {
252 clistp->c_cf = cblockp->c_next->c_info;
254 clistp->c_cf = clistp->c_cl = NULL;
256 cblock_free(cblockp);
257 if (--clistp->c_cbcount >= clistp->c_cbreserved)
267 * Copy 'amount' of chars, beginning at head of clist 'clistp' to
268 * destination linear buffer 'dest'. Return number of characters
272 q_to_b(clistp, dest, amount)
273 struct clist *clistp;
277 struct cblock *cblockp;
278 struct cblock *cblockn;
279 char *dest_orig = dest;
285 while (clistp && amount && (clistp->c_cc > 0)) {
286 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
287 cblockn = cblockp + 1; /* pointer arithmetic! */
288 numc = min(amount, (char *)cblockn - clistp->c_cf);
289 numc = min(numc, clistp->c_cc);
290 bcopy(clistp->c_cf, dest, numc);
292 clistp->c_cf += numc;
293 clistp->c_cc -= numc;
296 * If this cblock has been emptied, advance to the next
297 * one. If there are no more characters, set the first
298 * and last pointer to NULL. In either case, free the
301 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) {
302 if (clistp->c_cc > 0) {
303 clistp->c_cf = cblockp->c_next->c_info;
305 clistp->c_cf = clistp->c_cl = NULL;
307 cblock_free(cblockp);
308 if (--clistp->c_cbcount >= clistp->c_cbreserved)
314 return (dest - dest_orig);
318 * Flush 'amount' of chars, beginning at head of clist 'clistp'.
321 ndflush(clistp, amount)
322 struct clist *clistp;
325 struct cblock *cblockp;
326 struct cblock *cblockn;
332 while (amount && (clistp->c_cc > 0)) {
333 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
334 cblockn = cblockp + 1; /* pointer arithmetic! */
335 numc = min(amount, (char *)cblockn - clistp->c_cf);
336 numc = min(numc, clistp->c_cc);
338 clistp->c_cf += numc;
339 clistp->c_cc -= numc;
341 * If this cblock has been emptied, advance to the next
342 * one. If there are no more characters, set the first
343 * and last pointer to NULL. In either case, free the
346 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) {
347 if (clistp->c_cc > 0) {
348 clistp->c_cf = cblockp->c_next->c_info;
350 clistp->c_cf = clistp->c_cl = NULL;
352 cblock_free(cblockp);
353 if (--clistp->c_cbcount >= clistp->c_cbreserved)
362 * Add a character to the end of a clist. Return -1 is no
363 * more clists, or 0 for success.
368 struct clist *clistp;
370 struct cblock *cblockp;
375 if (clistp->c_cl == NULL) {
376 if (clistp->c_cbreserved < 1) {
378 printf("putc to a clist with no reserved cblocks\n");
379 return (-1); /* nothing done */
381 cblockp = cblock_alloc();
382 clistp->c_cbcount = 1;
383 clistp->c_cf = clistp->c_cl = cblockp->c_info;
386 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
387 if (((intptr_t)clistp->c_cl & CROUND) == 0) {
388 struct cblock *prev = (cblockp - 1);
390 if (clistp->c_cbcount >= clistp->c_cbreserved) {
391 if (clistp->c_cbcount >= clistp->c_cbmax
392 || cslushcount <= 0) {
398 cblockp = cblock_alloc();
400 prev->c_next = cblockp;
401 clistp->c_cl = cblockp->c_info;
406 * If this character is quoted, set the quote bit, if not, clear it.
408 if (chr & TTY_QUOTE) {
409 setbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info);
411 * Use one of the spare quote bits to record that something
414 setbit(cblockp->c_quote, CBQSIZE * NBBY - 1);
416 clrbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info);
418 *clistp->c_cl++ = chr;
426 * Copy data from linear buffer to clist chain. Return the
427 * number of characters not copied.
430 b_to_q(src, amount, clistp)
433 struct clist *clistp;
435 struct cblock *cblockp;
436 char *firstbyte, *lastbyte;
437 u_char startmask, endmask;
438 int startbit, endbit, num_between, numc;
442 * Avoid allocating an initial cblock and then not using it.
443 * c_cc == 0 must imply c_cbount == 0.
451 * If there are no cblocks assigned to this clist yet,
454 if (clistp->c_cl == NULL) {
455 if (clistp->c_cbreserved < 1) {
457 printf("b_to_q to a clist with no reserved cblocks.\n");
458 return (amount); /* nothing done */
460 cblockp = cblock_alloc();
461 clistp->c_cbcount = 1;
462 clistp->c_cf = clistp->c_cl = cblockp->c_info;
465 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
470 * Get another cblock if needed.
472 if (((intptr_t)clistp->c_cl & CROUND) == 0) {
473 struct cblock *prev = cblockp - 1;
475 if (clistp->c_cbcount >= clistp->c_cbreserved) {
476 if (clistp->c_cbcount >= clistp->c_cbmax
477 || cslushcount <= 0) {
483 cblockp = cblock_alloc();
485 prev->c_next = cblockp;
486 clistp->c_cl = cblockp->c_info;
490 * Copy a chunk of the linear buffer up to the end
493 numc = min(amount, (char *)(cblockp + 1) - clistp->c_cl);
494 bcopy(src, clistp->c_cl, numc);
497 * Clear quote bits if they aren't known to be clear.
498 * The following could probably be made into a separate
499 * "bitzero()" routine, but why bother?
501 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1)) {
502 startbit = clistp->c_cl - (char *)cblockp->c_info;
503 endbit = startbit + numc - 1;
505 firstbyte = (u_char *)cblockp->c_quote + (startbit / NBBY);
506 lastbyte = (u_char *)cblockp->c_quote + (endbit / NBBY);
509 * Calculate mask of bits to preserve in first and
512 startmask = NBBY - (startbit % NBBY);
513 startmask = 0xff >> startmask;
514 endmask = (endbit % NBBY);
515 endmask = 0xff << (endmask + 1);
517 if (firstbyte != lastbyte) {
518 *firstbyte &= startmask;
519 *lastbyte &= endmask;
521 num_between = lastbyte - firstbyte - 1;
523 bzero(firstbyte + 1, num_between);
525 *firstbyte &= (startmask | endmask);
530 * ...and update pointer for the next chunk.
533 clistp->c_cl += numc;
534 clistp->c_cc += numc;
537 * If we go through the loop again, it's always
538 * for data in the next cblock, so by adding one (cblock),
539 * (which makes the pointer 1 beyond the end of this
540 * cblock) we prepare for the assignment of 'prev'
552 * Get the next character in the clist. Store it at dst. Don't
553 * advance any clist pointers, but return a pointer to the next
554 * character position.
557 nextc(clistp, cp, dst)
558 struct clist *clistp;
562 struct cblock *cblockp;
566 * See if the next character is beyond the end of
569 if (clistp->c_cc && (cp != clistp->c_cl)) {
571 * If the next character is beyond the end of this
572 * cblock, advance to the next cblock.
574 if (((intptr_t)cp & CROUND) == 0)
575 cp = ((struct cblock *)cp - 1)->c_next->c_info;
576 cblockp = (struct cblock *)((intptr_t)cp & ~CROUND);
579 * Get the character. Set the quote flag if this character
582 *dst = (u_char)*cp | (isset(cblockp->c_quote, cp - (char *)cblockp->c_info) ? TTY_QUOTE : 0);
591 * "Unput" a character from a clist.
595 struct clist *clistp;
597 struct cblock *cblockp = 0, *cbp = 0;
608 chr = (u_char)*clistp->c_cl;
610 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
613 * Set quote flag if this character was quoted.
615 if (isset(cblockp->c_quote, (u_char *)clistp->c_cl - cblockp->c_info))
619 * If all of the characters have been unput in this
620 * cblock, then find the previous one and free this
623 if (clistp->c_cc && (clistp->c_cl <= (char *)cblockp->c_info)) {
624 cbp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
626 while (cbp->c_next != cblockp)
630 * When the previous cblock is at the end, the 'last'
631 * pointer always points (invalidly) one past.
633 clistp->c_cl = (char *)(cbp+1);
634 cblock_free(cblockp);
635 if (--clistp->c_cbcount >= clistp->c_cbreserved)
642 * If there are no more characters on the list, then
643 * free the last cblock.
645 if ((clistp->c_cc == 0) && clistp->c_cl) {
646 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
647 cblock_free(cblockp);
648 if (--clistp->c_cbcount >= clistp->c_cbreserved)
650 clistp->c_cf = clistp->c_cl = NULL;
658 * Move characters in source clist to destination clist,
659 * preserving quote bits.
662 catq(src_clistp, dest_clistp)
663 struct clist *src_clistp, *dest_clistp;
669 * If the destination clist is empty (has no cblocks atttached),
670 * and there are no possible complications with the resource counters,
671 * then we simply assign the current clist to the destination.
673 if (!dest_clistp->c_cf
674 && src_clistp->c_cbcount <= src_clistp->c_cbmax
675 && src_clistp->c_cbcount <= dest_clistp->c_cbmax) {
676 dest_clistp->c_cf = src_clistp->c_cf;
677 dest_clistp->c_cl = src_clistp->c_cl;
678 src_clistp->c_cf = src_clistp->c_cl = NULL;
680 dest_clistp->c_cc = src_clistp->c_cc;
681 src_clistp->c_cc = 0;
682 dest_clistp->c_cbcount = src_clistp->c_cbcount;
683 src_clistp->c_cbcount = 0;
692 * XXX This should probably be optimized to more than one
693 * character at a time.
695 while ((chr = getc(src_clistp)) != -1)
696 putc(chr, dest_clistp);