Ignore machine-check MSRs
[freebsd-src/fkvm-freebsd.git] / sys / kern / subr_clist.c
blobf434a72bb2a3ae7fe455f6dcc5112b905dced35c
1 /*-
2 * Copyright (c) 1994, David Greenman
3 * All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
10 * disclaimer.
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
25 * SUCH DAMAGE.
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;
47 int cfreecount = 0;
48 static int cslushcount;
49 static int ctotcount;
51 #ifndef INITIAL_CBLOCKS
52 #define INITIAL_CBLOCKS 50
53 #endif
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);
62 #include "opt_ddb.h"
63 #ifdef DDB
64 #include <ddb/ddb.h>
66 DB_SHOW_COMMAND(cbstat, cbstat)
68 int cbsize = CBSIZE;
70 printf(
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);
75 #endif /* DDB */
78 * Called from init_main.c
80 /* ARGSUSED*/
81 static void
82 clist_init(dummy)
83 void *dummy;
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
98 * to it.
100 static __inline struct cblock *
101 cblock_alloc()
103 struct cblock *cblockp;
105 cblockp = cfreelist;
106 if (cblockp == NULL)
107 panic("clist reservation botch");
108 cfreelist = cblockp->c_next;
109 cblockp->c_next = NULL;
110 cfreecount -= CBSIZE;
111 return (cblockp);
115 * Add a cblock to the cfreelist queue.
117 static __inline void
118 cblock_free(cblockp)
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;
124 cfreelist = cblockp;
125 cfreecount += CBSIZE;
129 * Allocate some cblocks for the cfreelist queue.
131 static void
132 cblock_alloc_cblocks(number)
133 int number;
135 int i;
136 struct cblock *cbp;
138 for (i = 0; i < number; ++i) {
139 cbp = malloc(sizeof *cbp, M_CLIST, M_NOWAIT);
140 if (cbp == NULL) {
141 printf(
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);
150 cblock_free(cbp);
152 ctotcount += number;
156 * Set the cblock allocation policy for a clist.
157 * Must be called in process context at spltty().
159 void
160 clist_alloc_cblocks(clistp, ccmax, ccreserved)
161 struct clist *clistp;
162 int ccmax;
163 int ccreserved;
165 int dcbr;
168 * Allow for wasted space at the head.
170 if (ccmax != 0)
171 ccmax += CBSIZE - 1;
172 if (ccreserved != 0)
173 ccreserved += CBSIZE - 1;
175 clistp->c_cbmax = roundup(ccmax, CBSIZE) / CBSIZE;
176 dcbr = roundup(ccreserved, CBSIZE) / CBSIZE - clistp->c_cbreserved;
177 if (dcbr >= 0)
178 cblock_alloc_cblocks(dcbr);
179 else {
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.
191 static void
192 cblock_free_cblocks(number)
193 int number;
195 int i;
197 for (i = 0; i < number; ++i)
198 free(cblock_alloc(), M_CLIST);
199 ctotcount -= number;
203 * Free the cblocks reserved for a clist.
204 * Must be called at spltty().
206 void
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);
213 clistp->c_cbmax = 0;
214 clistp->c_cbreserved = 0;
218 * Get a character from the head of a clist.
221 getc(clistp)
222 struct clist *clistp;
224 int chr = -1;
225 int s;
226 struct cblock *cblockp;
228 s = spltty();
230 /* If there are characters in the list, get one */
231 if (clistp->c_cc) {
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))
239 chr |= QUOTEMASK;
242 * Advance to next character.
244 clistp->c_cf++;
245 clistp->c_cc--;
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
251 * current cblock.
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;
256 } else {
257 clistp->c_cf = clistp->c_cl = NULL;
259 cblock_free(cblockp);
260 if (--clistp->c_cbcount >= clistp->c_cbreserved)
261 ++cslushcount;
265 splx(s);
266 return (chr);
270 * Copy 'amount' of chars, beginning at head of clist 'clistp' to
271 * destination linear buffer 'dest'. Return number of characters
272 * actually copied.
275 q_to_b(clistp, dest, amount)
276 struct clist *clistp;
277 char *dest;
278 int amount;
280 struct cblock *cblockp;
281 struct cblock *cblockn;
282 char *dest_orig = dest;
283 int numc;
284 int s;
286 s = spltty();
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);
294 amount -= numc;
295 clistp->c_cf += numc;
296 clistp->c_cc -= numc;
297 dest += 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
302 * current cblock.
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;
307 } else {
308 clistp->c_cf = clistp->c_cl = NULL;
310 cblock_free(cblockp);
311 if (--clistp->c_cbcount >= clistp->c_cbreserved)
312 ++cslushcount;
316 splx(s);
317 return (dest - dest_orig);
321 * Flush 'amount' of chars, beginning at head of clist 'clistp'.
323 void
324 ndflush(clistp, amount)
325 struct clist *clistp;
326 int amount;
328 struct cblock *cblockp;
329 struct cblock *cblockn;
330 int numc;
331 int s;
333 s = spltty();
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);
340 amount -= numc;
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
347 * current cblock.
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;
352 } else {
353 clistp->c_cf = clistp->c_cl = NULL;
355 cblock_free(cblockp);
356 if (--clistp->c_cbcount >= clistp->c_cbreserved)
357 ++cslushcount;
361 splx(s);
365 * Add a character to the end of a clist. Return -1 is no
366 * more clists, or 0 for success.
369 putc(chr, clistp)
370 int chr;
371 struct clist *clistp;
373 struct cblock *cblockp;
374 int s;
376 s = spltty();
378 if (clistp->c_cl == NULL) {
379 if (clistp->c_cbreserved < 1) {
380 splx(s);
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;
387 clistp->c_cc = 0;
388 } else {
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) {
396 splx(s);
397 return (-1);
399 --cslushcount;
401 cblockp = cblock_alloc();
402 clistp->c_cbcount++;
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
415 * may be quoted.
417 setbit(cblockp->c_quote, CBQSIZE * NBBY - 1);
418 } else
419 clrbit(cblockp->c_quote, clistp->c_cl - (char *)cblockp->c_info);
421 *clistp->c_cl++ = chr;
422 clistp->c_cc++;
424 splx(s);
425 return (0);
429 * Copy data from linear buffer to clist chain. Return the
430 * number of characters not copied.
433 b_to_q(src, amount, clistp)
434 char *src;
435 int amount;
436 struct clist *clistp;
438 struct cblock *cblockp;
439 char *firstbyte, *lastbyte;
440 u_char startmask, endmask;
441 int startbit, endbit, num_between, numc;
442 int s;
445 * Avoid allocating an initial cblock and then not using it.
446 * c_cc == 0 must imply c_cbount == 0.
448 if (amount <= 0)
449 return (amount);
451 s = spltty();
454 * If there are no cblocks assigned to this clist yet,
455 * then get one.
457 if (clistp->c_cl == NULL) {
458 if (clistp->c_cbreserved < 1) {
459 splx(s);
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;
466 clistp->c_cc = 0;
467 } else {
468 cblockp = (struct cblock *)((intptr_t)clistp->c_cl & ~CROUND);
471 while (amount) {
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) {
481 splx(s);
482 return (amount);
484 --cslushcount;
486 cblockp = cblock_alloc();
487 clistp->c_cbcount++;
488 prev->c_next = cblockp;
489 clistp->c_cl = cblockp->c_info;
493 * Copy a chunk of the linear buffer up to the end
494 * of this cblock.
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
513 * last bytes.
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;
525 if (num_between)
526 bzero(firstbyte + 1, num_between);
527 } else {
528 *firstbyte &= (startmask | endmask);
533 * ...and update pointer for the next chunk.
535 src += numc;
536 clistp->c_cl += numc;
537 clistp->c_cc += numc;
538 amount -= 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'
544 * above.
546 cblockp += 1;
550 splx(s);
551 return (amount);
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.
559 char *
560 nextc(clistp, cp, dst)
561 struct clist *clistp;
562 char *cp;
563 int *dst;
565 struct cblock *cblockp;
567 ++cp;
569 * See if the next character is beyond the end of
570 * the clist.
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
583 * is quoted.
585 *dst = (u_char)*cp | (isset(cblockp->c_quote, cp - (char *)cblockp->c_info) ? QUOTEMASK : 0);
587 return (cp);
590 return (NULL);
594 * "Unput" a character from a clist.
597 unputc(clistp)
598 struct clist *clistp;
600 struct cblock *cblockp = 0, *cbp = 0;
601 int s;
602 int chr = -1;
605 s = spltty();
607 if (clistp->c_cc) {
608 --clistp->c_cc;
609 --clistp->c_cl;
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))
619 chr |= QUOTEMASK;
622 * If all of the characters have been unput in this
623 * cblock, then find the previous one and free this
624 * one.
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)
630 cbp = cbp->c_next;
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)
639 ++cslushcount;
640 cbp->c_next = NULL;
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)
652 ++cslushcount;
653 clistp->c_cf = clistp->c_cl = NULL;
656 splx(s);
657 return (chr);
661 * Move characters in source clist to destination clist,
662 * preserving quote bits.
664 void
665 catq(src_clistp, dest_clistp)
666 struct clist *src_clistp, *dest_clistp;
668 int chr, s;
670 s = spltty();
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;
688 splx(s);
689 return;
692 splx(s);
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);