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 MALLOC_DEFINE(M_CLIST, "clist", "clist queue blocks");
47 static struct cblock *cfreelist = 0;
49 static int cslushcount;
52 #ifndef INITIAL_CBLOCKS
53 #define INITIAL_CBLOCKS 50
56 static struct cblock *cblock_alloc(void);
57 static void cblock_alloc_cblocks(int number);
58 static void cblock_free(struct cblock *cblockp);
59 static void cblock_free_cblocks(int number);
65 DB_SHOW_COMMAND(cbstat, cbstat)
70 "tot = %d (active = %d, free = %d (reserved = %d, slush = %d))\n",
71 ctotcount * cbsize, ctotcount * cbsize - cfreecount, cfreecount,
72 cfreecount - cslushcount * cbsize, cslushcount * cbsize);
77 * Called from init_main.c
85 * Allocate an initial base set of cblocks as a 'slush'.
86 * We allocate non-slush cblocks with each initial tty_open() and
87 * deallocate them with each tty_close().
88 * We should adjust the slush allocation. This can't be done in
89 * the i/o routines because they are sometimes called from
90 * interrupt handlers when it may be unsafe to call malloc().
92 cblock_alloc_cblocks(cslushcount = INITIAL_CBLOCKS);
96 * Remove a cblock from the cfreelist queue and return a pointer
99 static __inline struct cblock *
102 struct cblock *cblockp;
106 panic("clist reservation botch");
107 cfreelist = cblockp->c_next;
108 cblockp->c_next = NULL;
109 cfreecount -= CBSIZE;
114 * Add a cblock to the cfreelist queue.
118 struct cblock *cblockp;
120 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1))
121 bzero(cblockp->c_quote, sizeof cblockp->c_quote);
122 cblockp->c_next = cfreelist;
124 cfreecount += CBSIZE;
128 * Allocate some cblocks for the cfreelist queue.
131 cblock_alloc_cblocks(number)
137 for (i = 0; i < number; ++i) {
138 cbp = malloc(sizeof *cbp, M_CLIST, M_NOWAIT);
141 "cblock_alloc_cblocks: M_NOWAIT malloc failed, trying M_WAITOK\n");
142 cbp = malloc(sizeof *cbp, M_CLIST, M_WAITOK);
145 * Freed cblocks have zero quotes and garbage elsewhere.
146 * Set the may-have-quote bit to force zeroing the quotes.
148 setbit(cbp->c_quote, CBQSIZE * NBBY - 1);
155 * Set the cblock allocation policy for a clist.
156 * Must be called in process context at spltty().
159 clist_alloc_cblocks(clistp, ccmax, ccreserved)
160 struct clist *clistp;
167 * Allow for wasted space at the head.
172 ccreserved += CBSIZE - 1;
174 clistp->c_cbmax = roundup(ccmax, CBSIZE) / CBSIZE;
175 dcbr = roundup(ccreserved, CBSIZE) / CBSIZE - clistp->c_cbreserved;
177 cblock_alloc_cblocks(dcbr);
179 if (clistp->c_cbreserved + dcbr < clistp->c_cbcount)
180 dcbr = clistp->c_cbcount - clistp->c_cbreserved;
181 cblock_free_cblocks(-dcbr);
183 clistp->c_cbreserved += dcbr;
187 * Free some cblocks from the cfreelist queue back to the
188 * system malloc pool.
191 cblock_free_cblocks(number)
196 for (i = 0; i < number; ++i)
197 free(cblock_alloc(), M_CLIST);
202 * Free the cblocks reserved for a clist.
203 * Must be called at spltty().
206 clist_free_cblocks(clistp)
207 struct clist *clistp;
209 if (clistp->c_cbcount != 0)
210 panic("freeing active clist cblocks");
211 cblock_free_cblocks(clistp->c_cbreserved);
213 clistp->c_cbreserved = 0;
217 * Get a character from the head of a clist.
221 struct clist *clistp;
225 struct cblock *cblockp;
229 /* If there are characters in the list, get one */
231 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
232 chr = (u_char)*clistp->c_cf;
235 * If this char is quoted, set the flag.
237 if (isset(cblockp->c_quote, clistp->c_cf - (char *)cblockp->c_info))
241 * Advance to next character.
246 * If we have advanced the 'first' character pointer
247 * past the end of this cblock, advance to the next one.
248 * If there are no more characters, set the first and
249 * last pointers to NULL. In either case, free the
252 if ((clistp->c_cf >= (char *)(cblockp+1)) || (clistp->c_cc == 0)) {
253 if (clistp->c_cc > 0) {
254 clistp->c_cf = cblockp->c_next->c_info;
256 clistp->c_cf = clistp->c_cl = NULL;
258 cblock_free(cblockp);
259 if (--clistp->c_cbcount >= clistp->c_cbreserved)
269 * Copy 'amount' of chars, beginning at head of clist 'clistp' to
270 * destination linear buffer 'dest'. Return number of characters
274 q_to_b(clistp, dest, amount)
275 struct clist *clistp;
279 struct cblock *cblockp;
280 struct cblock *cblockn;
281 char *dest_orig = dest;
287 while (clistp && amount && (clistp->c_cc > 0)) {
288 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
289 cblockn = cblockp + 1; /* pointer arithmetic! */
290 numc = min(amount, (char *)cblockn - clistp->c_cf);
291 numc = min(numc, clistp->c_cc);
292 bcopy(clistp->c_cf, dest, numc);
294 clistp->c_cf += numc;
295 clistp->c_cc -= numc;
298 * If this cblock has been emptied, advance to the next
299 * one. If there are no more characters, set the first
300 * and last pointer to NULL. In either case, free the
303 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) {
304 if (clistp->c_cc > 0) {
305 clistp->c_cf = cblockp->c_next->c_info;
307 clistp->c_cf = clistp->c_cl = NULL;
309 cblock_free(cblockp);
310 if (--clistp->c_cbcount >= clistp->c_cbreserved)
316 return (dest - dest_orig);
320 * Flush 'amount' of chars, beginning at head of clist 'clistp'.
323 ndflush(clistp, amount)
324 struct clist *clistp;
327 struct cblock *cblockp;
328 struct cblock *cblockn;
334 while (amount && (clistp->c_cc > 0)) {
335 cblockp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
336 cblockn = cblockp + 1; /* pointer arithmetic! */
337 numc = min(amount, (char *)cblockn - clistp->c_cf);
338 numc = min(numc, clistp->c_cc);
340 clistp->c_cf += numc;
341 clistp->c_cc -= numc;
343 * If this cblock has been emptied, advance to the next
344 * one. If there are no more characters, set the first
345 * and last pointer to NULL. In either case, free the
348 if ((clistp->c_cf >= (char *)cblockn) || (clistp->c_cc == 0)) {
349 if (clistp->c_cc > 0) {
350 clistp->c_cf = cblockp->c_next->c_info;
352 clistp->c_cf = clistp->c_cl = NULL;
354 cblock_free(cblockp);
355 if (--clistp->c_cbcount >= clistp->c_cbreserved)
364 * Add a character to the end of a clist. Return -1 is no
365 * more clists, or 0 for success.
370 struct clist *clistp;
372 struct cblock *cblockp;
377 if (clistp->c_cl == NULL) {
378 if (clistp->c_cbreserved < 1) {
380 printf("putc to a clist with no reserved cblocks\n");
381 return (-1); /* nothing done */
383 cblockp = cblock_alloc();
384 clistp->c_cbcount = 1;
385 clistp->c_cf = clistp->c_cl = cblockp->c_info;
388 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
389 if (((intptr_t)clistp->c_cl & CROUND) == 0) {
390 struct cblock *prev = (cblockp - 1);
392 if (clistp->c_cbcount >= clistp->c_cbreserved) {
393 if (clistp->c_cbcount >= clistp->c_cbmax
394 || cslushcount <= 0) {
400 cblockp = cblock_alloc();
402 prev->c_next = cblockp;
403 clistp->c_cl = cblockp->c_info;
408 * If this character is quoted, set the quote bit, if not, clear it.
410 if (chr & TTY_QUOTE) {
411 setbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info);
413 * Use one of the spare quote bits to record that something
416 setbit(cblockp->c_quote, CBQSIZE * NBBY - 1);
418 clrbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info);
420 *clistp->c_cl++ = chr;
428 * Copy data from linear buffer to clist chain. Return the
429 * number of characters not copied.
432 b_to_q(src, amount, clistp)
435 struct clist *clistp;
437 struct cblock *cblockp;
438 char *firstbyte, *lastbyte;
439 u_char startmask, endmask;
440 int startbit, endbit, num_between, numc;
444 * Avoid allocating an initial cblock and then not using it.
445 * c_cc == 0 must imply c_cbount == 0.
453 * If there are no cblocks assigned to this clist yet,
456 if (clistp->c_cl == NULL) {
457 if (clistp->c_cbreserved < 1) {
459 printf("b_to_q to a clist with no reserved cblocks.\n");
460 return (amount); /* nothing done */
462 cblockp = cblock_alloc();
463 clistp->c_cbcount = 1;
464 clistp->c_cf = clistp->c_cl = cblockp->c_info;
467 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
472 * Get another cblock if needed.
474 if (((intptr_t)clistp->c_cl & CROUND) == 0) {
475 struct cblock *prev = cblockp - 1;
477 if (clistp->c_cbcount >= clistp->c_cbreserved) {
478 if (clistp->c_cbcount >= clistp->c_cbmax
479 || cslushcount <= 0) {
485 cblockp = cblock_alloc();
487 prev->c_next = cblockp;
488 clistp->c_cl = cblockp->c_info;
492 * Copy a chunk of the linear buffer up to the end
495 numc = min(amount, (char *)(cblockp + 1) - clistp->c_cl);
496 bcopy(src, clistp->c_cl, numc);
499 * Clear quote bits if they aren't known to be clear.
500 * The following could probably be made into a separate
501 * "bitzero()" routine, but why bother?
503 if (isset(cblockp->c_quote, CBQSIZE * NBBY - 1)) {
504 startbit = clistp->c_cl - (char *)cblockp->c_info;
505 endbit = startbit + numc - 1;
507 firstbyte = (u_char *)cblockp->c_quote + (startbit / NBBY);
508 lastbyte = (u_char *)cblockp->c_quote + (endbit / NBBY);
511 * Calculate mask of bits to preserve in first and
514 startmask = NBBY - (startbit % NBBY);
515 startmask = 0xff >> startmask;
516 endmask = (endbit % NBBY);
517 endmask = 0xff << (endmask + 1);
519 if (firstbyte != lastbyte) {
520 *firstbyte &= startmask;
521 *lastbyte &= endmask;
523 num_between = lastbyte - firstbyte - 1;
525 bzero(firstbyte + 1, num_between);
527 *firstbyte &= (startmask | endmask);
532 * ...and update pointer for the next chunk.
535 clistp->c_cl += numc;
536 clistp->c_cc += numc;
539 * If we go through the loop again, it's always
540 * for data in the next cblock, so by adding one (cblock),
541 * (which makes the pointer 1 beyond the end of this
542 * cblock) we prepare for the assignment of 'prev'
554 * Get the next character in the clist. Store it at dst. Don't
555 * advance any clist pointers, but return a pointer to the next
556 * character position.
559 nextc(clistp, cp, dst)
560 struct clist *clistp;
564 struct cblock *cblockp;
568 * See if the next character is beyond the end of
571 if (clistp->c_cc && (cp != clistp->c_cl)) {
573 * If the next character is beyond the end of this
574 * cblock, advance to the next cblock.
576 if (((intptr_t)cp & CROUND) == 0)
577 cp = ((struct cblock *)cp - 1)->c_next->c_info;
578 cblockp = (struct cblock *)((intptr_t)cp & ~CROUND);
581 * Get the character. Set the quote flag if this character
584 *dst = (u_char)*cp | (isset(cblockp->c_quote, cp - (char *)cblockp->c_info) ? TTY_QUOTE : 0);
593 * "Unput" a character from a clist.
597 struct clist *clistp;
599 struct cblock *cblockp = 0, *cbp = 0;
610 chr = (u_char)*clistp->c_cl;
612 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
615 * Set quote flag if this character was quoted.
617 if (isset(cblockp->c_quote, (u_char *)clistp->c_cl - cblockp->c_info))
621 * If all of the characters have been unput in this
622 * cblock, then find the previous one and free this
625 if (clistp->c_cc && (clistp->c_cl <= (char *)cblockp->c_info)) {
626 cbp = (struct cblock *)((intptr_t)clistp->c_cf & ~CROUND);
628 while (cbp->c_next != cblockp)
632 * When the previous cblock is at the end, the 'last'
633 * pointer always points (invalidly) one past.
635 clistp->c_cl = (char *)(cbp+1);
636 cblock_free(cblockp);
637 if (--clistp->c_cbcount >= clistp->c_cbreserved)
644 * If there are no more characters on the list, then
645 * free the last cblock.
647 if ((clistp->c_cc == 0) && clistp->c_cl) {
648 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
649 cblock_free(cblockp);
650 if (--clistp->c_cbcount >= clistp->c_cbreserved)
652 clistp->c_cf = clistp->c_cl = NULL;
660 * Move characters in source clist to destination clist,
661 * preserving quote bits.
664 catq(src_clistp, dest_clistp)
665 struct clist *src_clistp, *dest_clistp;
671 * If the destination clist is empty (has no cblocks atttached),
672 * and there are no possible complications with the resource counters,
673 * then we simply assign the current clist to the destination.
675 if (!dest_clistp->c_cf
676 && src_clistp->c_cbcount <= src_clistp->c_cbmax
677 && src_clistp->c_cbcount <= dest_clistp->c_cbmax) {
678 dest_clistp->c_cf = src_clistp->c_cf;
679 dest_clistp->c_cl = src_clistp->c_cl;
680 src_clistp->c_cf = src_clistp->c_cl = NULL;
682 dest_clistp->c_cc = src_clistp->c_cc;
683 src_clistp->c_cc = 0;
684 dest_clistp->c_cbcount = src_clistp->c_cbcount;
685 src_clistp->c_cbcount = 0;
694 * XXX This should probably be optimized to more than one
695 * character at a time.
697 while ((chr = getc(src_clistp)) != -1)
698 putc(chr, dest_clistp);