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>
39 #include <sys/clist.h>
41 static void clist_init(void *);
42 SYSINIT(clist
, SI_SUB_CLIST
, SI_ORDER_FIRST
, clist_init
, NULL
);
44 static MALLOC_DEFINE(M_CLIST
, "clist", "clist queue blocks");
46 static struct cblock
*cfreelist
= 0;
48 static int cslushcount
;
51 #ifndef INITIAL_CBLOCKS
52 #define INITIAL_CBLOCKS 50
55 #define QUOTEMASK 0x100
57 static struct cblock
*cblock_alloc(void);
58 static void cblock_alloc_cblocks(int number
);
59 static void cblock_free(struct cblock
*cblockp
);
60 static void cblock_free_cblocks(int number
);
66 DB_SHOW_COMMAND(cbstat
, cbstat
)
71 "tot = %d (active = %d, free = %d (reserved = %d, slush = %d))\n",
72 ctotcount
* cbsize
, ctotcount
* cbsize
- cfreecount
, cfreecount
,
73 cfreecount
- cslushcount
* cbsize
, cslushcount
* cbsize
);
78 * Called from init_main.c
86 * Allocate an initial base set of cblocks as a 'slush'.
87 * We allocate non-slush cblocks with each initial tty_open() and
88 * deallocate them with each tty_close().
89 * We should adjust the slush allocation. This can't be done in
90 * the i/o routines because they are sometimes called from
91 * interrupt handlers when it may be unsafe to call malloc().
93 cblock_alloc_cblocks(cslushcount
= INITIAL_CBLOCKS
);
97 * Remove a cblock from the cfreelist queue and return a pointer
100 static __inline
struct cblock
*
103 struct cblock
*cblockp
;
107 panic("clist reservation botch");
108 cfreelist
= cblockp
->c_next
;
109 cblockp
->c_next
= NULL
;
110 cfreecount
-= CBSIZE
;
115 * Add a cblock to the cfreelist queue.
119 struct cblock
*cblockp
;
121 if (isset(cblockp
->c_quote
, CBQSIZE
* NBBY
- 1))
122 bzero(cblockp
->c_quote
, sizeof cblockp
->c_quote
);
123 cblockp
->c_next
= cfreelist
;
125 cfreecount
+= CBSIZE
;
129 * Allocate some cblocks for the cfreelist queue.
132 cblock_alloc_cblocks(number
)
138 for (i
= 0; i
< number
; ++i
) {
139 cbp
= malloc(sizeof *cbp
, M_CLIST
, M_NOWAIT
);
142 "cblock_alloc_cblocks: M_NOWAIT malloc failed, trying M_WAITOK\n");
143 cbp
= malloc(sizeof *cbp
, M_CLIST
, M_WAITOK
);
146 * Freed cblocks have zero quotes and garbage elsewhere.
147 * Set the may-have-quote bit to force zeroing the quotes.
149 setbit(cbp
->c_quote
, CBQSIZE
* NBBY
- 1);
156 * Set the cblock allocation policy for a clist.
157 * Must be called in process context at spltty().
160 clist_alloc_cblocks(clistp
, ccmax
, ccreserved
)
161 struct clist
*clistp
;
168 * Allow for wasted space at the head.
173 ccreserved
+= CBSIZE
- 1;
175 clistp
->c_cbmax
= roundup(ccmax
, CBSIZE
) / CBSIZE
;
176 dcbr
= roundup(ccreserved
, CBSIZE
) / CBSIZE
- clistp
->c_cbreserved
;
178 cblock_alloc_cblocks(dcbr
);
180 if (clistp
->c_cbreserved
+ dcbr
< clistp
->c_cbcount
)
181 dcbr
= clistp
->c_cbcount
- clistp
->c_cbreserved
;
182 cblock_free_cblocks(-dcbr
);
184 clistp
->c_cbreserved
+= dcbr
;
188 * Free some cblocks from the cfreelist queue back to the
189 * system malloc pool.
192 cblock_free_cblocks(number
)
197 for (i
= 0; i
< number
; ++i
)
198 free(cblock_alloc(), M_CLIST
);
203 * Free the cblocks reserved for a clist.
204 * Must be called at spltty().
207 clist_free_cblocks(clistp
)
208 struct clist
*clistp
;
210 if (clistp
->c_cbcount
!= 0)
211 panic("freeing active clist cblocks");
212 cblock_free_cblocks(clistp
->c_cbreserved
);
214 clistp
->c_cbreserved
= 0;
218 * Get a character from the head of a clist.
222 struct clist
*clistp
;
226 struct cblock
*cblockp
;
230 /* If there are characters in the list, get one */
232 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cf
& ~CROUND
);
233 chr
= (u_char
)*clistp
->c_cf
;
236 * If this char is quoted, set the flag.
238 if (isset(cblockp
->c_quote
, clistp
->c_cf
- (char *)cblockp
->c_info
))
242 * Advance to next character.
247 * If we have advanced the 'first' character pointer
248 * past the end of this cblock, advance to the next one.
249 * If there are no more characters, set the first and
250 * last pointers to NULL. In either case, free the
253 if ((clistp
->c_cf
>= (char *)(cblockp
+1)) || (clistp
->c_cc
== 0)) {
254 if (clistp
->c_cc
> 0) {
255 clistp
->c_cf
= cblockp
->c_next
->c_info
;
257 clistp
->c_cf
= clistp
->c_cl
= NULL
;
259 cblock_free(cblockp
);
260 if (--clistp
->c_cbcount
>= clistp
->c_cbreserved
)
270 * Copy 'amount' of chars, beginning at head of clist 'clistp' to
271 * destination linear buffer 'dest'. Return number of characters
275 q_to_b(clistp
, dest
, amount
)
276 struct clist
*clistp
;
280 struct cblock
*cblockp
;
281 struct cblock
*cblockn
;
282 char *dest_orig
= dest
;
288 while (clistp
&& amount
&& (clistp
->c_cc
> 0)) {
289 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cf
& ~CROUND
);
290 cblockn
= cblockp
+ 1; /* pointer arithmetic! */
291 numc
= min(amount
, (char *)cblockn
- clistp
->c_cf
);
292 numc
= min(numc
, clistp
->c_cc
);
293 bcopy(clistp
->c_cf
, dest
, numc
);
295 clistp
->c_cf
+= numc
;
296 clistp
->c_cc
-= numc
;
299 * If this cblock has been emptied, advance to the next
300 * one. If there are no more characters, set the first
301 * and last pointer to NULL. In either case, free the
304 if ((clistp
->c_cf
>= (char *)cblockn
) || (clistp
->c_cc
== 0)) {
305 if (clistp
->c_cc
> 0) {
306 clistp
->c_cf
= cblockp
->c_next
->c_info
;
308 clistp
->c_cf
= clistp
->c_cl
= NULL
;
310 cblock_free(cblockp
);
311 if (--clistp
->c_cbcount
>= clistp
->c_cbreserved
)
317 return (dest
- dest_orig
);
321 * Flush 'amount' of chars, beginning at head of clist 'clistp'.
324 ndflush(clistp
, amount
)
325 struct clist
*clistp
;
328 struct cblock
*cblockp
;
329 struct cblock
*cblockn
;
335 while (amount
&& (clistp
->c_cc
> 0)) {
336 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cf
& ~CROUND
);
337 cblockn
= cblockp
+ 1; /* pointer arithmetic! */
338 numc
= min(amount
, (char *)cblockn
- clistp
->c_cf
);
339 numc
= min(numc
, clistp
->c_cc
);
341 clistp
->c_cf
+= numc
;
342 clistp
->c_cc
-= numc
;
344 * If this cblock has been emptied, advance to the next
345 * one. If there are no more characters, set the first
346 * and last pointer to NULL. In either case, free the
349 if ((clistp
->c_cf
>= (char *)cblockn
) || (clistp
->c_cc
== 0)) {
350 if (clistp
->c_cc
> 0) {
351 clistp
->c_cf
= cblockp
->c_next
->c_info
;
353 clistp
->c_cf
= clistp
->c_cl
= NULL
;
355 cblock_free(cblockp
);
356 if (--clistp
->c_cbcount
>= clistp
->c_cbreserved
)
365 * Add a character to the end of a clist. Return -1 is no
366 * more clists, or 0 for success.
371 struct clist
*clistp
;
373 struct cblock
*cblockp
;
378 if (clistp
->c_cl
== NULL
) {
379 if (clistp
->c_cbreserved
< 1) {
381 printf("putc to a clist with no reserved cblocks\n");
382 return (-1); /* nothing done */
384 cblockp
= cblock_alloc();
385 clistp
->c_cbcount
= 1;
386 clistp
->c_cf
= clistp
->c_cl
= cblockp
->c_info
;
389 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cl
& ~CROUND
);
390 if (((intptr_t)clistp
->c_cl
& CROUND
) == 0) {
391 struct cblock
*prev
= (cblockp
- 1);
393 if (clistp
->c_cbcount
>= clistp
->c_cbreserved
) {
394 if (clistp
->c_cbcount
>= clistp
->c_cbmax
395 || cslushcount
<= 0) {
401 cblockp
= cblock_alloc();
403 prev
->c_next
= cblockp
;
404 clistp
->c_cl
= cblockp
->c_info
;
409 * If this character is quoted, set the quote bit, if not, clear it.
411 if (chr
& QUOTEMASK
) {
412 setbit(cblockp
->c_quote
, clistp
->c_cl
- (char *)cblockp
->c_info
);
414 * Use one of the spare quote bits to record that something
417 setbit(cblockp
->c_quote
, CBQSIZE
* NBBY
- 1);
419 clrbit(cblockp
->c_quote
, clistp
->c_cl
- (char *)cblockp
->c_info
);
421 *clistp
->c_cl
++ = chr
;
429 * Copy data from linear buffer to clist chain. Return the
430 * number of characters not copied.
433 b_to_q(src
, amount
, clistp
)
436 struct clist
*clistp
;
438 struct cblock
*cblockp
;
439 char *firstbyte
, *lastbyte
;
440 u_char startmask
, endmask
;
441 int startbit
, endbit
, num_between
, numc
;
445 * Avoid allocating an initial cblock and then not using it.
446 * c_cc == 0 must imply c_cbount == 0.
454 * If there are no cblocks assigned to this clist yet,
457 if (clistp
->c_cl
== NULL
) {
458 if (clistp
->c_cbreserved
< 1) {
460 printf("b_to_q to a clist with no reserved cblocks.\n");
461 return (amount
); /* nothing done */
463 cblockp
= cblock_alloc();
464 clistp
->c_cbcount
= 1;
465 clistp
->c_cf
= clistp
->c_cl
= cblockp
->c_info
;
468 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cl
& ~CROUND
);
473 * Get another cblock if needed.
475 if (((intptr_t)clistp
->c_cl
& CROUND
) == 0) {
476 struct cblock
*prev
= cblockp
- 1;
478 if (clistp
->c_cbcount
>= clistp
->c_cbreserved
) {
479 if (clistp
->c_cbcount
>= clistp
->c_cbmax
480 || cslushcount
<= 0) {
486 cblockp
= cblock_alloc();
488 prev
->c_next
= cblockp
;
489 clistp
->c_cl
= cblockp
->c_info
;
493 * Copy a chunk of the linear buffer up to the end
496 numc
= min(amount
, (char *)(cblockp
+ 1) - clistp
->c_cl
);
497 bcopy(src
, clistp
->c_cl
, numc
);
500 * Clear quote bits if they aren't known to be clear.
501 * The following could probably be made into a separate
502 * "bitzero()" routine, but why bother?
504 if (isset(cblockp
->c_quote
, CBQSIZE
* NBBY
- 1)) {
505 startbit
= clistp
->c_cl
- (char *)cblockp
->c_info
;
506 endbit
= startbit
+ numc
- 1;
508 firstbyte
= (u_char
*)cblockp
->c_quote
+ (startbit
/ NBBY
);
509 lastbyte
= (u_char
*)cblockp
->c_quote
+ (endbit
/ NBBY
);
512 * Calculate mask of bits to preserve in first and
515 startmask
= NBBY
- (startbit
% NBBY
);
516 startmask
= 0xff >> startmask
;
517 endmask
= (endbit
% NBBY
);
518 endmask
= 0xff << (endmask
+ 1);
520 if (firstbyte
!= lastbyte
) {
521 *firstbyte
&= startmask
;
522 *lastbyte
&= endmask
;
524 num_between
= lastbyte
- firstbyte
- 1;
526 bzero(firstbyte
+ 1, num_between
);
528 *firstbyte
&= (startmask
| endmask
);
533 * ...and update pointer for the next chunk.
536 clistp
->c_cl
+= numc
;
537 clistp
->c_cc
+= numc
;
540 * If we go through the loop again, it's always
541 * for data in the next cblock, so by adding one (cblock),
542 * (which makes the pointer 1 beyond the end of this
543 * cblock) we prepare for the assignment of 'prev'
555 * Get the next character in the clist. Store it at dst. Don't
556 * advance any clist pointers, but return a pointer to the next
557 * character position.
560 nextc(clistp
, cp
, dst
)
561 struct clist
*clistp
;
565 struct cblock
*cblockp
;
569 * See if the next character is beyond the end of
572 if (clistp
->c_cc
&& (cp
!= clistp
->c_cl
)) {
574 * If the next character is beyond the end of this
575 * cblock, advance to the next cblock.
577 if (((intptr_t)cp
& CROUND
) == 0)
578 cp
= ((struct cblock
*)cp
- 1)->c_next
->c_info
;
579 cblockp
= (struct cblock
*)((intptr_t)cp
& ~CROUND
);
582 * Get the character. Set the quote flag if this character
585 *dst
= (u_char
)*cp
| (isset(cblockp
->c_quote
, cp
- (char *)cblockp
->c_info
) ? QUOTEMASK
: 0);
594 * "Unput" a character from a clist.
598 struct clist
*clistp
;
600 struct cblock
*cblockp
= 0, *cbp
= 0;
611 chr
= (u_char
)*clistp
->c_cl
;
613 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cl
& ~CROUND
);
616 * Set quote flag if this character was quoted.
618 if (isset(cblockp
->c_quote
, (u_char
*)clistp
->c_cl
- cblockp
->c_info
))
622 * If all of the characters have been unput in this
623 * cblock, then find the previous one and free this
626 if (clistp
->c_cc
&& (clistp
->c_cl
<= (char *)cblockp
->c_info
)) {
627 cbp
= (struct cblock
*)((intptr_t)clistp
->c_cf
& ~CROUND
);
629 while (cbp
->c_next
!= cblockp
)
633 * When the previous cblock is at the end, the 'last'
634 * pointer always points (invalidly) one past.
636 clistp
->c_cl
= (char *)(cbp
+1);
637 cblock_free(cblockp
);
638 if (--clistp
->c_cbcount
>= clistp
->c_cbreserved
)
645 * If there are no more characters on the list, then
646 * free the last cblock.
648 if ((clistp
->c_cc
== 0) && clistp
->c_cl
) {
649 cblockp
= (struct cblock
*)((intptr_t)clistp
->c_cl
& ~CROUND
);
650 cblock_free(cblockp
);
651 if (--clistp
->c_cbcount
>= clistp
->c_cbreserved
)
653 clistp
->c_cf
= clistp
->c_cl
= NULL
;
661 * Move characters in source clist to destination clist,
662 * preserving quote bits.
665 catq(src_clistp
, dest_clistp
)
666 struct clist
*src_clistp
, *dest_clistp
;
672 * If the destination clist is empty (has no cblocks atttached),
673 * and there are no possible complications with the resource counters,
674 * then we simply assign the current clist to the destination.
676 if (!dest_clistp
->c_cf
677 && src_clistp
->c_cbcount
<= src_clistp
->c_cbmax
678 && src_clistp
->c_cbcount
<= dest_clistp
->c_cbmax
) {
679 dest_clistp
->c_cf
= src_clistp
->c_cf
;
680 dest_clistp
->c_cl
= src_clistp
->c_cl
;
681 src_clistp
->c_cf
= src_clistp
->c_cl
= NULL
;
683 dest_clistp
->c_cc
= src_clistp
->c_cc
;
684 src_clistp
->c_cc
= 0;
685 dest_clistp
->c_cbcount
= src_clistp
->c_cbcount
;
686 src_clistp
->c_cbcount
= 0;
695 * XXX This should probably be optimized to more than one
696 * character at a time.
698 while ((chr
= getc(src_clistp
)) != -1)
699 putc(chr
, dest_clistp
);