diff options
Diffstat (limited to 'contrib/bind/lib/isc')
23 files changed, 7697 insertions, 0 deletions
diff --git a/contrib/bind/lib/isc/Makefile b/contrib/bind/lib/isc/Makefile new file mode 100644 index 0000000..cdcac69 --- /dev/null +++ b/contrib/bind/lib/isc/Makefile @@ -0,0 +1,77 @@ +# Copyright (c) 1996 by Internet Software Consortium +# +# Permission to use, copy, modify, and distribute this software for any +# purpose with or without fee is hereby granted, provided that the above +# copyright notice and this permission notice appear in all copies. +# +# THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +# ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +# OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +# CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +# DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +# PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +# ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +# SOFTWARE. + +# $Id: Makefile,v 8.15 1997/12/03 22:36:08 halley Exp $ + +# these are only appropriate for BSD 4.4 or derivatives, and are used in +# development. normal builds will be done in the top level directory and +# this Makefile will be invoked with a lot of overrides for the following: +SYSTYPE= bsdos +DESTDIR = +DESTLIB = /usr/local/lib +O=o +A=a +CC= cc +LD= ld +SHELL= /bin/sh +CDEBUG= -g +TOP= ../.. +INCL = ${TOP}/include +PORTINCL = ${TOP}/port/${SYSTYPE}/include +LIBBIND = ${TOP}/lib/libbind.${A} +CFLAGS= ${CDEBUG} -I${PORTINCL} -I${INCL} +LD_LIBFLAGS= -x -r +AR= ar cruv +RANLIB= ranlib +INSTALL= install + +SRCS= tree.c base64.c bitncmp.c assertions.c \ + memcluster.c logging.c heap.c \ + eventlib.c ev_connects.c ev_files.c \ + ev_timers.c ev_streams.c ev_waits.c + +OBJS= tree.${O} base64.${O} bitncmp.${O} assertions.${O} \ + memcluster.${O} logging.${O} heap.${O} \ + eventlib.${O} ev_connects.${O} ev_files.${O} \ + ev_timers.${O} ev_streams.${O} ev_waits.${O} + +all: ${LIBBIND} + +${LIBBIND}: ${OBJS} + ${AR} ${LIBBIND} ${ARPREF} ${OBJS} ${ARSUFF} + ${RANLIB} ${LIBBIND} + +.c.${O}: + ${CC} ${CPPFLAGS} ${CFLAGS} -c $*.c + -${LDS} ${LD} ${LD_LIBFLAGS} $*.${O} && ${LDS} mv a.out $*.${O} + +distclean: clean + +clean: FRC + rm -f .depend a.out core ${LIB} tags + rm -f *.${O} *.BAK *.CKP *~ + +depend: FRC + mkdep -I${INCL} -I${PORTINCL} ${CPPFLAGS} ${SRCS} + +links: FRC + @set -e; ln -s SRC/*.[ch] . + +install: + +FRC: + +# DO NOT DELETE THIS LINE -- mkdep uses it. +# DO NOT PUT ANYTHING AFTER THIS LINE, IT WILL GO AWAY. diff --git a/contrib/bind/lib/isc/assertions.c b/contrib/bind/lib/isc/assertions.c new file mode 100644 index 0000000..949d4d2 --- /dev/null +++ b/contrib/bind/lib/isc/assertions.c @@ -0,0 +1,90 @@ +/* + * Copyright (c) 1997 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: assertions.c,v 8.2 1997/12/08 21:29:05 halley Exp $"; +#endif + +#include "port_before.h" + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <isc/assertions.h> + +#include "port_after.h" + +/* + * Forward. + */ + +static void default_assertion_failed(char *, int, assertion_type, char *, int); + +/* + * Public. + */ + +assertion_failure_callback __assertion_failed = default_assertion_failed; + +void +set_assertion_failure_callback(assertion_failure_callback f) { + if (f == NULL) + __assertion_failed = default_assertion_failed; + else + __assertion_failed = f; +} + +char * +assertion_type_to_text(assertion_type type) { + char *result; + + switch (type) { + case assert_require: + result = "REQUIRE"; + break; + case assert_ensure: + result = "ENSURE"; + break; + case assert_insist: + result = "INSIST"; + break; + case assert_invariant: + result = "INVARIANT"; + break; + default: + result = NULL; + } + return (result); +} + +/* + * Private. + */ + +static void +default_assertion_failed(char *file, int line, assertion_type type, char *cond, + int print_errno) +{ + fprintf(stderr, "%s:%d: %s(%s)%s%s failed.\n", + file, line, assertion_type_to_text(type), cond, + (print_errno) ? ": " : "", + (print_errno) ? strerror(errno) : ""); + abort(); + /* NOTREACHED */ +} diff --git a/contrib/bind/lib/isc/assertions.mdoc b/contrib/bind/lib/isc/assertions.mdoc new file mode 100644 index 0000000..e82d9f9 --- /dev/null +++ b/contrib/bind/lib/isc/assertions.mdoc @@ -0,0 +1,134 @@ +.\" $Id: assertions.mdoc,v 8.1 1997/12/03 22:33:30 halley Exp $ +.\" +.\"Copyright (c) 1997 by Internet Software Consortium. +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.Dd November 17, 1997 +.Dt ASSERTIONS 3 +.Os ISC +.Sh NAME +.Nm REQUIRE , +.Nm REQUIRE_ERR , +.Nm ENSURE , +.Nm ENSURE_ERR , +.Nm INSIST , +.Nm INSIST_ERR , +.Nm INVARIANT , +.Nm INVARIANT_ERR , +.Nm set_assertion_failure_callback +.Nd assertion system +.Sh SYNOPSIS +.Fd #include <isc/assertions.h> +.Fo "typedef void (*assertion_failure_callback)" +.Fa "char *filename" +.Fa "int line" +.Fa "assertion_type type" +.Fa "char *condition" +.Fa "int print_errno" +.Fc +.Fn REQUIRE "int boolean_expression" +.Fn REQUIRE_ERR "int boolean_expression" +.Fn ENSURE "int boolean_expression" +.Fn ENSURE_ERR "int boolean_expression" +.Fn INSIST "int boolean_expression" +.Fn INSIST_ERR "int boolean_expression" +.Fn INVARIANT "int boolean_expression" +.Fn INVARIANT_ERR "int boolean_expression" +.Ft void +.Fn set_assertion_failure_callback "assertion_failure_callback callback" +.Ft char * +.Fn assertion_type_to_text "assertion_type type" +.Sh DESCRIPTION +The +.Fn REQUIRE , +.Fn ENSURE , +.Fn INSIST , +and +.Fn INVARIANT +macros evaluate a boolean expression, and if it is false, they invoke the +current assertion failure callback. The default callback will print a message +to +.Li stderr +describing the failure, and then cause the program to dump core. +If the +.Dq Fn _ERR +variant of the assertion is used, the callback will include +.Fn strerror "errno" +in its message. +.Pp +Each assertion type has an associated +.Li CHECK +macro. If this macro's value is +.Dq 0 +when +.Dq "<isc/assertions.h>" +is included, then assertions of that type will not be checked. E.g. + +.Dl #define CHECK_ENSURE 0 + +will disable checking of +.Fn ENSURE +and +.Fn ENSURE_ERR . +The macros +.Li CHECK_ALL +and +.Li CHECK_NONE +may also be used, respectively specifying that either all or none of the +assertion types should be checked. +.Pp +.Fn set_assertion_failure_callback +specifies the function to call when an assertion fails. +.Pp +When an +.li +assertion_failure_callback +is called, the +.Fa filename +and +.Fa line +arguments specify the filename and line number of the failing assertion. +The +.Fa type +is one of: +.Bd -literal -offset indent +assert_require +assert_ensure +assert_insist +assert_invariant +.Ed + +and may be used by the callback to determine the type of the failing +assertion. +.Fa condition +is the literal text of the assertion that failed. +.Fa print_errno +will be non-zero if the callback should print +.Fa strerror "errno" +as part of its output. +.Pp +.Fn assertion_type_to_text +returns a textual representation of +.Fa type . +For example, +.Fn assertion_type_to_text "assert_require" +returns the string +.Dq REQUIRE . +.Sh SEE ALSO +Bertrand Meyer, +.Sy Object-Oriented Software Construction, +2nd edition, Prentice\-Hall, 1997, ISBN 0\-13\-629155\-4, chapter 11. +.Sh AUTHOR +Bob Halley (ISC). diff --git a/contrib/bind/lib/isc/base64.c b/contrib/bind/lib/isc/base64.c new file mode 100644 index 0000000..58e700e --- /dev/null +++ b/contrib/bind/lib/isc/base64.c @@ -0,0 +1,320 @@ +/* + * Copyright (c) 1996, 1998 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* + * Portions Copyright (c) 1995 by International Business Machines, Inc. + * + * International Business Machines, Inc. (hereinafter called IBM) grants + * permission under its copyrights to use, copy, modify, and distribute this + * Software with or without fee, provided that the above copyright notice and + * all paragraphs of this notice appear in all copies, and that the name of IBM + * not be used in connection with the marketing of any product incorporating + * the Software or modifications thereof, without specific, written prior + * permission. + * + * To the extent it has a right to do so, IBM grants an immunity from suit + * under its patents, if any, for the use, sale or manufacture of products to + * the extent that such products are used for performing Domain Name System + * dynamic updates in TCP/IP networks by means of the Software. No immunity is + * granted for any product per se or for any other function of any product. + * + * THE SOFTWARE IS PROVIDED "AS IS", AND IBM DISCLAIMS ALL WARRANTIES, + * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A + * PARTICULAR PURPOSE. IN NO EVENT SHALL IBM BE LIABLE FOR ANY SPECIAL, + * DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER ARISING + * OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE, EVEN + * IF IBM IS APPRISED OF THE POSSIBILITY OF SUCH DAMAGES. + */ + +#if !defined(LINT) && !defined(CODECENTER) +static char rcsid[] = "$Id: base64.c,v 8.5 1998/03/27 00:17:46 halley Exp $"; +#endif /* not lint */ + +#include "port_before.h" + +#include <sys/types.h> +#include <sys/param.h> +#include <sys/socket.h> + +#include <netinet/in.h> +#include <arpa/inet.h> +#include <arpa/nameser.h> + +#include <ctype.h> +#include <resolv.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include "port_after.h" + +#define Assert(Cond) if (!(Cond)) abort() + +static const char Base64[] = + "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"; +static const char Pad64 = '='; + +/* (From RFC1521 and draft-ietf-dnssec-secext-03.txt) + The following encoding technique is taken from RFC 1521 by Borenstein + and Freed. It is reproduced here in a slightly edited form for + convenience. + + A 65-character subset of US-ASCII is used, enabling 6 bits to be + represented per printable character. (The extra 65th character, "=", + is used to signify a special processing function.) + + The encoding process represents 24-bit groups of input bits as output + strings of 4 encoded characters. Proceeding from left to right, a + 24-bit input group is formed by concatenating 3 8-bit input groups. + These 24 bits are then treated as 4 concatenated 6-bit groups, each + of which is translated into a single digit in the base64 alphabet. + + Each 6-bit group is used as an index into an array of 64 printable + characters. The character referenced by the index is placed in the + output string. + + Table 1: The Base64 Alphabet + + Value Encoding Value Encoding Value Encoding Value Encoding + 0 A 17 R 34 i 51 z + 1 B 18 S 35 j 52 0 + 2 C 19 T 36 k 53 1 + 3 D 20 U 37 l 54 2 + 4 E 21 V 38 m 55 3 + 5 F 22 W 39 n 56 4 + 6 G 23 X 40 o 57 5 + 7 H 24 Y 41 p 58 6 + 8 I 25 Z 42 q 59 7 + 9 J 26 a 43 r 60 8 + 10 K 27 b 44 s 61 9 + 11 L 28 c 45 t 62 + + 12 M 29 d 46 u 63 / + 13 N 30 e 47 v + 14 O 31 f 48 w (pad) = + 15 P 32 g 49 x + 16 Q 33 h 50 y + + Special processing is performed if fewer than 24 bits are available + at the end of the data being encoded. A full encoding quantum is + always completed at the end of a quantity. When fewer than 24 input + bits are available in an input group, zero bits are added (on the + right) to form an integral number of 6-bit groups. Padding at the + end of the data is performed using the '=' character. + + Since all base64 input is an integral number of octets, only the + ------------------------------------------------- + following cases can arise: + + (1) the final quantum of encoding input is an integral + multiple of 24 bits; here, the final unit of encoded + output will be an integral multiple of 4 characters + with no "=" padding, + (2) the final quantum of encoding input is exactly 8 bits; + here, the final unit of encoded output will be two + characters followed by two "=" padding characters, or + (3) the final quantum of encoding input is exactly 16 bits; + here, the final unit of encoded output will be three + characters followed by one "=" padding character. + */ + +int +b64_ntop(u_char const *src, size_t srclength, char *target, size_t targsize) { + size_t datalength = 0; + u_char input[3]; + u_char output[4]; + size_t i; + + while (2 < srclength) { + input[0] = *src++; + input[1] = *src++; + input[2] = *src++; + srclength -= 3; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + output[3] = input[2] & 0x3f; + Assert(output[0] < 64); + Assert(output[1] < 64); + Assert(output[2] < 64); + Assert(output[3] < 64); + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + target[datalength++] = Base64[output[2]]; + target[datalength++] = Base64[output[3]]; + } + + /* Now we worry about padding. */ + if (0 != srclength) { + /* Get what's left. */ + input[0] = input[1] = input[2] = '\0'; + for (i = 0; i < srclength; i++) + input[i] = *src++; + + output[0] = input[0] >> 2; + output[1] = ((input[0] & 0x03) << 4) + (input[1] >> 4); + output[2] = ((input[1] & 0x0f) << 2) + (input[2] >> 6); + Assert(output[0] < 64); + Assert(output[1] < 64); + Assert(output[2] < 64); + + if (datalength + 4 > targsize) + return (-1); + target[datalength++] = Base64[output[0]]; + target[datalength++] = Base64[output[1]]; + if (srclength == 1) + target[datalength++] = Pad64; + else + target[datalength++] = Base64[output[2]]; + target[datalength++] = Pad64; + } + if (datalength >= targsize) + return (-1); + target[datalength] = '\0'; /* Returned value doesn't count \0. */ + return (datalength); +} + +/* skips all whitespace anywhere. + converts characters, four at a time, starting at (or after) + src from base - 64 numbers into three 8 bit bytes in the target area. + it returns the number of data bytes stored at the target, or -1 on error. + */ + +int +b64_pton(src, target, targsize) + char const *src; + u_char *target; + size_t targsize; +{ + int tarindex, state, ch; + char *pos; + + state = 0; + tarindex = 0; + + while ((ch = *src++) != '\0') { + if (isspace(ch)) /* Skip whitespace anywhere. */ + continue; + + if (ch == Pad64) + break; + + pos = strchr(Base64, ch); + if (pos == 0) /* A non-base64 character. */ + return (-1); + + switch (state) { + case 0: + if (target) { + if ((size_t)tarindex >= targsize) + return (-1); + target[tarindex] = (pos - Base64) << 2; + } + state = 1; + break; + case 1: + if (target) { + if ((size_t)tarindex + 1 >= targsize) + return (-1); + target[tarindex] |= (pos - Base64) >> 4; + target[tarindex+1] = ((pos - Base64) & 0x0f) + << 4 ; + } + tarindex++; + state = 2; + break; + case 2: + if (target) { + if ((size_t)tarindex + 1 >= targsize) + return (-1); + target[tarindex] |= (pos - Base64) >> 2; + target[tarindex+1] = ((pos - Base64) & 0x03) + << 6; + } + tarindex++; + state = 3; + break; + case 3: + if (target) { + if ((size_t)tarindex >= targsize) + return (-1); + target[tarindex] |= (pos - Base64); + } + tarindex++; + state = 0; + break; + default: + abort(); + } + } + + /* + * We are done decoding Base-64 chars. Let's see if we ended + * on a byte boundary, and/or with erroneous trailing characters. + */ + + if (ch == Pad64) { /* We got a pad char. */ + ch = *src++; /* Skip it, get next. */ + switch (state) { + case 0: /* Invalid = in first position */ + case 1: /* Invalid = in second position */ + return (-1); + + case 2: /* Valid, means one byte of info */ + /* Skip any number of spaces. */ + for ((void)NULL; ch != '\0'; ch = *src++) + if (!isspace(ch)) + break; + /* Make sure there is another trailing = sign. */ + if (ch != Pad64) + return (-1); + ch = *src++; /* Skip the = */ + /* Fall through to "single trailing =" case. */ + /* FALLTHROUGH */ + + case 3: /* Valid, means two bytes of info */ + /* + * We know this char is an =. Is there anything but + * whitespace after it? + */ + for ((void)NULL; ch != '\0'; ch = *src++) + if (!isspace(ch)) + return (-1); + + /* + * Now make sure for cases 2 and 3 that the "extra" + * bits that slopped past the last full byte were + * zeros. If we don't check them, they become a + * subliminal channel. + */ + if (target && target[tarindex] != 0) + return (-1); + } + } else { + /* + * We ended by seeing the end of the string. Make sure we + * have no partial bytes lying around. + */ + if (state != 0) + return (-1); + } + + return (tarindex); +} diff --git a/contrib/bind/lib/isc/bitncmp.c b/contrib/bind/lib/isc/bitncmp.c new file mode 100644 index 0000000..473f4f7 --- /dev/null +++ b/contrib/bind/lib/isc/bitncmp.c @@ -0,0 +1,66 @@ +/* + * Copyright (c) 1996 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static const char rcsid[] = "$Id: bitncmp.c,v 1.5 1996/11/18 09:09:48 vixie Exp $"; +#endif + +#include "port_before.h" + +#include <sys/types.h> + +#include <string.h> + +#include "port_after.h" + +#include <isc/misc.h> + +/* + * int + * bitncmp(l, r, n) + * compare bit masks l and r, for n bits. + * return: + * -1, 1, or 0 in the libc tradition. + * note: + * network byte order assumed. this means 192.5.5.240/28 has + * 0x11110000 in its fourth octet. + * author: + * Paul Vixie (ISC), June 1996 + */ +int +bitncmp(const void *l, const void *r, int n) { + u_int lb, rb; + int x, b; + + b = n / 8; + x = memcmp(l, r, b); + if (x) + return (x); + + lb = ((u_char *)l)[b]; + rb = ((u_char *)r)[b]; + for (b = n % 8; b > 0; b--) { + if ((lb & 0x80) != (rb & 0x80)) { + if (lb & 0x80) + return (1); + return (-1); + } + lb <<= 1; + rb <<= 1; + } + return (0); +} diff --git a/contrib/bind/lib/isc/bitncmp.mdoc b/contrib/bind/lib/isc/bitncmp.mdoc new file mode 100644 index 0000000..99c6c25 --- /dev/null +++ b/contrib/bind/lib/isc/bitncmp.mdoc @@ -0,0 +1,82 @@ +.\" $Id: bitncmp.mdoc,v 8.1 1997/01/30 20:27:23 vixie Exp $ +.\" +.\"Copyright (c) 1996 by Internet Software Consortium. +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.Dd June 1, 1996 +.Dt BITNCMP 3 +.Os BSD 4 +.Sh NAME +.Nm bitncmp +.Nd compare bit masks +.Sh SYNOPSIS +.Ft int +.Fn bitncmp "const void *l" "const void *r" "int n" +.Sh DESCRIPTION +The function +.Fn bitncmp +compares the +.Dq Fa n +most-significant bits of the two masks pointed to by +.Dq Fa l +and +.Dq Fa r , +and returns an integer less than, equal to, or greater than 0, according to +whether or not +.Dq Fa l +is lexicographically less than, equal to, or greater than +.Dq Fa r +when taken to be unsigned characters (this behaviour is just like that of +.Xr memcmp 3 ) . +.Pp +.Sy NOTE: +.Fn Bitncmp +assumes +.Sy network byte order ; +this means that the fourth octet of +.Li 192.5.5.240/28 +.Li 0x11110000 . +.Sh RETURN VALUES +.Fn Bitncmp +returns values in the manner of +.Xr memcmp 3 : +.Bd -filled -offset indent ++1 if +.Dq Fa 1 +is greater than +.Dq Fa r ; +.Pp +-1 if +.Dq Fa l +is less than +.Dq Fa r ; +and +.Pp +0 if +.Dq Fa l +is equal to +.Dq Fa r , +.Ed +.Pp +where +.Dq Fa l +and +.Dq Fa r +are both interpreted as strings of unsigned characters (through bit +.Dq Fa n .) +.Sh SEE ALSO +.Xr memcmp 3 . +.Sh AUTHOR +Paul Vixie (ISC). diff --git a/contrib/bind/lib/isc/ev_connects.c b/contrib/bind/lib/isc/ev_connects.c new file mode 100644 index 0000000..1cf7291 --- /dev/null +++ b/contrib/bind/lib/isc/ev_connects.c @@ -0,0 +1,316 @@ +/* + * Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* ev_connects.c - implement asynch connect/accept for the eventlib + * vix 16sep96 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: ev_connects.c,v 8.19 1998/03/20 23:26:22 halley Exp $"; +#endif + +/* Import. */ + +#include "port_before.h" +#include "fd_setsize.h" + +#include <sys/types.h> +#include <sys/socket.h> + +#include <unistd.h> + +#include <isc/eventlib.h> +#include <isc/assertions.h> +#include "eventlib_p.h" + +#include "port_after.h" + +/* Forward. */ + +static void listener(evContext ctx, void *uap, int fd, int evmask); +static void connector(evContext ctx, void *uap, int fd, int evmask); + +/* Public. */ + +int +evListen(evContext opaqueCtx, int fd, int maxconn, + evConnFunc func, void *uap, evConnID *id) +{ + evContext_p *ctx = opaqueCtx.opaque; + evConn *new; + int mode; + + OKNEW(new); + new->flags = EV_CONN_LISTEN; + OK(mode = fcntl(fd, F_GETFL, NULL)); /* side effect: validate fd. */ + /* + * Remember the nonblocking status. We assume that either evSelectFD + * has not been done to this fd, or that if it has then the caller + * will evCancelConn before they evDeselectFD. If our assumptions + * are not met, then we might restore the old nonblocking status + * incorrectly. + */ + if ((mode & O_NONBLOCK) == 0) { + OK(fcntl(fd, F_SETFL, mode | O_NONBLOCK)); + new->flags |= EV_CONN_BLOCK; + } + OK(listen(fd, maxconn)); + if (evSelectFD(opaqueCtx, fd, EV_READ, listener, new, &new->file) < 0){ + int save = errno; + + FREE(new); + errno = save; + return (-1); + } + new->flags |= EV_CONN_SELECTED; + new->func = func; + new->uap = uap; + new->fd = fd; + if (ctx->conns != NULL) + ctx->conns->prev = new; + new->prev = NULL; + new->next = ctx->conns; + ctx->conns = new; + if (id) + id->opaque = new; + return (0); +} + +int +evConnect(evContext opaqueCtx, int fd, void *ra, int ralen, + evConnFunc func, void *uap, evConnID *id) +{ + evContext_p *ctx = opaqueCtx.opaque; + evConn *new; + + OKNEW(new); + new->flags = 0; + /* Do the select() first to get the socket into nonblocking mode. */ + if (evSelectFD(opaqueCtx, fd, EV_MASK_ALL, + connector, new, &new->file) < 0) { + int save = errno; + + FREE(new); + errno = save; + return (-1); + } + new->flags |= EV_CONN_SELECTED; + if (connect(fd, ra, ralen) < 0 && + errno != EWOULDBLOCK && + errno != EAGAIN && + errno != EINPROGRESS) { + int save = errno; + + (void) evDeselectFD(opaqueCtx, new->file); + FREE(new); + errno = save; + return (-1); + } + /* No error, or EWOULDBLOCK. select() tells when it's ready. */ + new->func = func; + new->uap = uap; + new->fd = fd; + if (ctx->conns != NULL) + ctx->conns->prev = new; + new->prev = NULL; + new->next = ctx->conns; + ctx->conns = new; + if (id) + id->opaque = new; + return (0); +} + +int +evCancelConn(evContext opaqueCtx, evConnID id) { + evContext_p *ctx = opaqueCtx.opaque; + evConn *this = id.opaque; + evAccept *acc, *nxtacc; + int mode; + + if ((this->flags & EV_CONN_SELECTED) != 0) + (void) evDeselectFD(opaqueCtx, this->file); + if ((this->flags & EV_CONN_BLOCK) != 0) { + mode = fcntl(this->fd, F_GETFL, NULL); + if (mode == -1) { + if (errno != EBADF) + return (-1); + } else + OK(fcntl(this->fd, F_SETFL, mode | O_NONBLOCK)); + } + + /* Unlink from ctx->conns. */ + if (this->prev != NULL) + this->prev->next = this->next; + else + ctx->conns = this->next; + if (this->next != NULL) + this->next->prev = this->prev; + + /* + * Remove `this' from the ctx->accepts list (zero or more times). + */ + for (acc = HEAD(ctx->accepts), nxtacc = NULL; + acc != NULL; + acc = nxtacc) + { + nxtacc = NEXT(acc, link); + if (acc->conn == this) { + UNLINK(ctx->accepts, acc, link); + close(acc->fd); + FREE(acc); + } + } + + /* Wrap up and get out. */ + FREE(this); + return (0); +} + +int evHold(evContext opaqueCtx, evConnID id) { + evConn *this = id.opaque; + + if ((this->flags & EV_CONN_LISTEN) == 0) { + errno = EINVAL; + return (-1); + } + if ((this->flags & EV_CONN_SELECTED) == 0) + return (0); + this->flags &= ~EV_CONN_SELECTED; + return (evDeselectFD(opaqueCtx, this->file)); +} + +int evUnhold(evContext opaqueCtx, evConnID id) { + evConn *this = id.opaque; + int ret; + + if ((this->flags & EV_CONN_LISTEN) == 0) { + errno = EINVAL; + return (-1); + } + if ((this->flags & EV_CONN_SELECTED) != 0) + return (0); + ret = evSelectFD(opaqueCtx, this->fd, EV_READ, listener, this, + &this->file); + if (ret == 0) + this->flags |= EV_CONN_SELECTED; + return (ret); +} + +int +evTryAccept(evContext opaqueCtx, evConnID id, int *sys_errno) { + evContext_p *ctx = opaqueCtx.opaque; + evConn *conn = id.opaque; + evAccept *new; + + if ((conn->flags & EV_CONN_LISTEN) == 0) { + errno = EINVAL; + return (-1); + } + OKNEW(new); + new->conn = conn; + new->ralen = sizeof new->ra; + new->fd = accept(conn->fd, &new->ra, &new->ralen); + if (new->fd >= 0) { + new->lalen = sizeof new->la; + if (getsockname(new->fd, &new->la, &new->lalen) < 0) { + new->ioErrno = errno; + (void) close(new->fd); + new->fd = -1; + } else + new->ioErrno = 0; + } else { + new->ioErrno = errno; + if (errno == EAGAIN || errno == EWOULDBLOCK) { + FREE(new); + return (-1); + } + } + APPEND(ctx->accepts, new, link); + *sys_errno = new->ioErrno; + return (0); +} + +/* Private. */ + +static void +listener(evContext opaqueCtx, void *uap, int fd, int evmask) { + evContext_p *ctx = opaqueCtx.opaque; + evConn *conn = uap; + struct sockaddr la, ra; + int new, lalen, ralen; + + REQUIRE((evmask & EV_READ) != 0); + ralen = sizeof ra; + new = accept(fd, &ra, &ralen); + if (new >= 0) { + lalen = sizeof la; + if (getsockname(new, &la, &lalen) < 0) { + int save = errno; + + (void) close(new); + errno = save; + new = -1; + } + } else if (errno == EAGAIN || errno == EWOULDBLOCK) + return; + (*conn->func)(opaqueCtx, conn->uap, new, &la, lalen, &ra, ralen); +} + +static void +connector(evContext opaqueCtx, void *uap, int fd, int evmask) { + evContext_p *ctx = opaqueCtx.opaque; + evConn *conn = uap; + struct sockaddr la, ra; + int lalen, ralen; + char buf[1]; + void *conn_uap; + evConnFunc conn_func; + evConnID id; + int socket_errno = 0; + int optlen; + + lalen = sizeof la; + ralen = sizeof ra; + conn_uap = conn->uap; + conn_func = conn->func; + id.opaque = conn; +#ifdef SO_ERROR + optlen = sizeof socket_errno; + if (fd < 0 && + getsockopt(conn->fd, SOL_SOCKET, SO_ERROR, (char *)&socket_errno, + &optlen) < 0) + socket_errno = errno; + else + errno = socket_errno; +#endif + if (evCancelConn(opaqueCtx, id) < 0 || + socket_errno || +#ifdef NETREAD_BROKEN + 0 || +#else + read(fd, buf, 0) < 0 || +#endif + getsockname(fd, &la, &lalen) < 0 || + getpeername(fd, &ra, &ralen) < 0) { + int save = errno; + + (void) close(fd); /* XXX closing caller's fd */ + errno = save; + fd = -1; + } + (*conn_func)(opaqueCtx, conn_uap, fd, &la, lalen, &ra, ralen); +} diff --git a/contrib/bind/lib/isc/ev_files.c b/contrib/bind/lib/isc/ev_files.c new file mode 100644 index 0000000..6cd1d41 --- /dev/null +++ b/contrib/bind/lib/isc/ev_files.c @@ -0,0 +1,271 @@ +/* Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* ev_files.c - implement asynch file IO for the eventlib + * vix 11sep95 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: ev_files.c,v 1.15 1998/02/06 01:53:52 halley Exp $"; +#endif + +#include "port_before.h" +#include "fd_setsize.h" + +#include <sys/types.h> +#include <sys/time.h> + +#include <errno.h> +#include <fcntl.h> +#include <unistd.h> + +#include <isc/eventlib.h> +#include "eventlib_p.h" + +#include "port_after.h" + +static evFile *FindFD(const evContext_p *ctx, int fd, int eventmask); + +int +evSelectFD(evContext opaqueCtx, + int fd, + int eventmask, + evFileFunc func, + void *uap, + evFileID *opaqueID +) { + evContext_p *ctx = opaqueCtx.opaque; + evFile *id; + int mode; + + evPrintf(ctx, 1, + "evSelectFD(ctx %#x, fd %d, mask 0x%x, func %#x, uap %#x)\n", + ctx, fd, eventmask, func, uap); + if (eventmask == 0 || (eventmask & ~EV_MASK_ALL) != 0) + ERR(EINVAL); + if (fd >= FD_SETSIZE) + ERR(EINVAL); + OK(mode = fcntl(fd, F_GETFL, NULL)); /* side effect: validate fd. */ + + /* + * The first time we touch a file descriptor, we need to check to see + * if the application already had it in O_NONBLOCK mode and if so, all + * of our deselect()'s have to leave it in O_NONBLOCK. If not, then + * all but our last deselect() has to leave it in O_NONBLOCK. + */ + id = FindFD(ctx, fd, EV_MASK_ALL); + if (id == NULL) { + if (mode & O_NONBLOCK) + FD_SET(fd, &ctx->nonblockBefore); + else { + OK(fcntl(fd, F_SETFL, mode | O_NONBLOCK)); + FD_CLR(fd, &ctx->nonblockBefore); + } + } + + /* + * If this descriptor is already in use, search for it again to see + * if any of the eventmask bits we want to set are already captured. + * We cannot usefully capture the same fd event more than once in the + * same context. + */ + if (id != NULL && FindFD(ctx, fd, eventmask) != NULL) + ERR(ETOOMANYREFS); + + /* Allocate and fill. */ + OKNEW(id); + id->func = func; + id->uap = uap; + id->fd = fd; + id->eventmask = eventmask; + + /* + * Insert at head. Order could be important for performance if we + * believe that evGetNext()'s accesses to the fd_sets will be more + * serial and therefore more cache-lucky if the list is ordered by + * ``fd.'' We do not believe these things, so we don't do it. + * + * The interesting sequence is where GetNext() has cached a select() + * result and the caller decides to evSelectFD() on some descriptor. + * Since GetNext() starts at the head, it can miss new entries we add + * at the head. This is not a serious problem since the event being + * evSelectFD()'d for has to occur before evSelectFD() is called for + * the file event to be considered "missed" -- a real corner case. + * Maintaining a "tail" pointer for ctx->files would fix this, but I'm + * not sure it would be ``more correct.'' + */ + if (ctx->files != NULL) + ctx->files->prev = id; + id->prev = NULL; + id->next = ctx->files; + ctx->files = id; + + /* Insert into fd table. */ + if (ctx->fdTable[fd] != NULL) + ctx->fdTable[fd]->fdprev = id; + id->fdprev = NULL; + id->fdnext = ctx->fdTable[fd]; + ctx->fdTable[fd] = id; + + /* Turn on the appropriate bits in the {rd,wr,ex}Next fd_set's. */ + if (eventmask & EV_READ) + FD_SET(fd, &ctx->rdNext); + if (eventmask & EV_WRITE) + FD_SET(fd, &ctx->wrNext); + if (eventmask & EV_EXCEPT) + FD_SET(fd, &ctx->exNext); + + /* Update fdMax. */ + if (fd > ctx->fdMax) + ctx->fdMax = fd; + + /* Remember the ID if the caller provided us a place for it. */ + if (opaqueID) + opaqueID->opaque = id; + + evPrintf(ctx, 5, + "evSelectFD(fd %d, mask 0x%x): new masks: 0x%lx 0x%lx 0x%lx\n", + fd, eventmask, + (u_long)ctx->rdNext.fds_bits[0], + (u_long)ctx->wrNext.fds_bits[0], + (u_long)ctx->exNext.fds_bits[0]); + + return (0); +} + +int +evDeselectFD(evContext opaqueCtx, evFileID opaqueID) { + evContext_p *ctx = opaqueCtx.opaque; + evFile *del = opaqueID.opaque; + evFile *old, *cur; + int mode, eventmask; + + if (!del) { + evPrintf(ctx, 11, "evDeselectFD(NULL) ignored\n"); + errno = EINVAL; + return (-1); + } + + evPrintf(ctx, 1, "evDeselectFD(fd %d, mask 0x%x)\n", + del->fd, del->eventmask); + + /* Get the mode. Unless the file has been closed, errors are bad. */ + mode = fcntl(del->fd, F_GETFL, NULL); + if (mode == -1 && errno != EBADF) + ERR(errno); + + /* Remove from the list of files. */ + if (del->prev != NULL) + del->prev->next = del->next; + else + ctx->files = del->next; + if (del->next != NULL) + del->next->prev = del->prev; + + /* Remove from the fd table. */ + if (del->fdprev != NULL) + del->fdprev->fdnext = del->fdnext; + else + ctx->fdTable[del->fd] = del->fdnext; + if (del->fdnext != NULL) + del->fdnext->fdprev = del->fdprev; + + /* + * If the file descriptor does not appear in any other select() entry, + * and if !EV_WASNONBLOCK, and if we got no EBADF when we got the mode + * earlier, then: restore the fd to blocking status. + */ + if (!(cur = FindFD(ctx, del->fd, EV_MASK_ALL)) && + !FD_ISSET(del->fd, &ctx->nonblockBefore) && + mode != -1) { + /* + * Note that we won't return an error status to the caller if + * this fcntl() fails since (a) we've already done the work + * and (b) the caller didn't ask us anything about O_NONBLOCK. + */ + (void) fcntl(del->fd, F_SETFL, mode & ~O_NONBLOCK); + } + + /* + * Now find all other uses of this descriptor and OR together an event + * mask so that we don't turn off {rd,wr,ex}Next bits that some other + * file event is using. As an optimization, stop if the event mask + * fills. + */ + eventmask = 0; + for ((void)NULL; + cur != NULL && eventmask != EV_MASK_ALL; + cur = cur->next) + if (cur->fd == del->fd) + eventmask |= cur->eventmask; + + /* OK, now we know which bits we can clear out. */ + if (!(eventmask & EV_READ)) { + FD_CLR(del->fd, &ctx->rdNext); + if (FD_ISSET(del->fd, &ctx->rdLast)) { + FD_CLR(del->fd, &ctx->rdLast); + ctx->fdCount--; + } + } + if (!(eventmask & EV_WRITE)) { + FD_CLR(del->fd, &ctx->wrNext); + if (FD_ISSET(del->fd, &ctx->wrLast)) { + FD_CLR(del->fd, &ctx->wrLast); + ctx->fdCount--; + } + } + if (!(eventmask & EV_EXCEPT)) { + FD_CLR(del->fd, &ctx->exNext); + if (FD_ISSET(del->fd, &ctx->exLast)) { + FD_CLR(del->fd, &ctx->exLast); + ctx->fdCount--; + } + } + + /* If this was the maxFD, find the new one. */ + if (del->fd == ctx->fdMax) { + ctx->fdMax = -1; + for (cur = ctx->files; cur; cur = cur->next) + if (cur->fd > ctx->fdMax) + ctx->fdMax = cur->fd; + } + + /* If this was the fdNext, cycle that to the next entry. */ + if (del == ctx->fdNext) + ctx->fdNext = del->next; + + evPrintf(ctx, 5, + "evDeselectFD(fd %d, mask 0x%x): new masks: 0x%lx 0x%lx 0x%lx\n", + del->fd, eventmask, + (u_long)ctx->rdNext.fds_bits[0], + (u_long)ctx->wrNext.fds_bits[0], + (u_long)ctx->exNext.fds_bits[0]); + + /* Couldn't free it before now since we were using fields out of it. */ + FREE(del); + + return (0); +} + +static evFile * +FindFD(const evContext_p *ctx, int fd, int eventmask) { + evFile *id; + + for (id = ctx->fdTable[fd]; id != NULL; id = id->fdnext) + if (id->fd == fd && (id->eventmask & eventmask) != 0) + break; + return (id); +} diff --git a/contrib/bind/lib/isc/ev_streams.c b/contrib/bind/lib/isc/ev_streams.c new file mode 100644 index 0000000..aa4270b --- /dev/null +++ b/contrib/bind/lib/isc/ev_streams.c @@ -0,0 +1,301 @@ +/* Copyright (c) 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* ev_streams.c - implement asynch stream file IO for the eventlib + * vix 04mar96 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: ev_streams.c,v 8.18 1998/03/20 23:26:22 halley Exp $"; +#endif + +#include "port_before.h" +#include "fd_setsize.h" + +#include <sys/types.h> +#include <sys/uio.h> + +#include <errno.h> + +#include <isc/eventlib.h> +#include <isc/assertions.h> +#include "eventlib_p.h" + +#include "port_after.h" + +static int copyvec(evStream *str, const struct iovec *iov, int iocnt); +static void consume(evStream *str, size_t bytes); +static void done(evContext opaqueCtx, evStream *str); +static void writable(evContext opaqueCtx, void *uap, int fd, int evmask); +static void readable(evContext opaqueCtx, void *uap, int fd, int evmask); + +struct iovec +evConsIovec(void *buf, size_t cnt) { + struct iovec ret; + + memset(&ret, 0xf5, sizeof ret); + ret.iov_base = buf; + ret.iov_len = cnt; + return (ret); +} + +int +evWrite(evContext opaqueCtx, int fd, const struct iovec *iov, int iocnt, + evStreamFunc func, void *uap, evStreamID *id) +{ + evContext_p *ctx = opaqueCtx.opaque; + evStream *new; + int save; + + OKNEW(new); + new->func = func; + new->uap = uap; + new->fd = fd; + new->flags = 0; + if (evSelectFD(opaqueCtx, fd, EV_WRITE, writable, new, &new->file) < 0) + goto free; + if (copyvec(new, iov, iocnt) < 0) + goto free; + new->prevDone = NULL; + new->nextDone = NULL; + if (ctx->streams != NULL) + ctx->streams->prev = new; + new->prev = NULL; + new->next = ctx->streams; + ctx->streams = new; + if (id != NULL) + id->opaque = new; + return (0); + free: + save = errno; + FREE(new); + errno = save; + err: + return (-1); +} + +int +evRead(evContext opaqueCtx, int fd, const struct iovec *iov, int iocnt, + evStreamFunc func, void *uap, evStreamID *id) +{ + evContext_p *ctx = opaqueCtx.opaque; + evStream *new; + int save; + + OKNEW(new); + new->func = func; + new->uap = uap; + new->fd = fd; + new->flags = 0; + if (evSelectFD(opaqueCtx, fd, EV_READ, readable, new, &new->file) < 0) + goto free; + if (copyvec(new, iov, iocnt) < 0) + goto free; + new->prevDone = NULL; + new->nextDone = NULL; + if (ctx->streams != NULL) + ctx->streams->prev = new; + new->prev = NULL; + new->next = ctx->streams; + ctx->streams = new; + if (id) + id->opaque = new; + return (0); + free: + save = errno; + FREE(new); + errno = save; + err: + return (-1); +} + +int +evTimeRW(evContext opaqueCtx, evStreamID id, evTimerID timer) /*ARGSUSED*/ { + evContext_p *ctx = opaqueCtx.opaque; + evStream *str = id.opaque; + + str->timer = timer; + str->flags |= EV_STR_TIMEROK; + return (0); +} + +int +evUntimeRW(evContext opaqueCtx, evStreamID id) /*ARGSUSED*/ { + evContext_p *ctx = opaqueCtx.opaque; + evStream *str = id.opaque; + + str->flags &= ~EV_STR_TIMEROK; + return (0); +} + +int +evCancelRW(evContext opaqueCtx, evStreamID id) { + evContext_p *ctx = opaqueCtx.opaque; + evStream *old = id.opaque; + + /* + * The streams list is doubly threaded. First, there's ctx->streams + * that's used by evDestroy() to find and cancel all streams. Second, + * there's ctx->strDone (head) and ctx->strLast (tail) which thread + * through the potentially smaller number of "IO completed" streams, + * used in evGetNext() to avoid scanning the entire list. + */ + + /* Unlink from ctx->streams. */ + if (old->prev != NULL) + old->prev->next = old->next; + else + ctx->streams = old->next; + if (old->next != NULL) + old->next->prev = old->prev; + + /* + * If 'old' is on the ctx->strDone list, remove it. Update + * ctx->strLast if necessary. + */ + if (old->prevDone == NULL && old->nextDone == NULL) { + /* + * Either 'old' is the only item on the done list, or it's + * not on the done list. If the former, then we unlink it + * from the list. If the latter, we leave the list alone. + */ + if (ctx->strDone == old) { + ctx->strDone = NULL; + ctx->strLast = NULL; + } + } else { + if (old->prevDone != NULL) + old->prevDone->nextDone = old->nextDone; + else + ctx->strDone = old->nextDone; + if (old->nextDone != NULL) + old->nextDone->prevDone = old->prevDone; + else + ctx->strLast = old->prevDone; + } + + /* Deallocate the stream. */ + if (old->file.opaque) + evDeselectFD(opaqueCtx, old->file); + memput(old->iovOrig, sizeof (struct iovec) * old->iovOrigCount); + FREE(old); + return (0); +} + +/* Copy a scatter/gather vector and initialize a stream handler's IO. */ +static int +copyvec(evStream *str, const struct iovec *iov, int iocnt) { + int i; + + str->iovOrig = (struct iovec *)memget(sizeof(struct iovec) * iocnt); + if (str->iovOrig == NULL) { + errno = ENOMEM; + return (-1); + } + str->ioTotal = 0; + for (i = 0; i < iocnt; i++) { + str->iovOrig[i] = iov[i]; + str->ioTotal += iov[i].iov_len; + } + str->iovOrigCount = iocnt; + str->iovCur = str->iovOrig; + str->iovCurCount = str->iovOrigCount; + str->ioDone = 0; + return (0); +} + +/* Pull off or truncate lead iovec(s). */ +static void +consume(evStream *str, size_t bytes) { + while (bytes > 0) { + if (bytes < str->iovCur->iov_len) { + str->iovCur->iov_len -= bytes; + str->iovCur->iov_base = (void *) + ((u_char *)str->iovCur->iov_base + bytes); + str->ioDone += bytes; + bytes = 0; + } else { + bytes -= str->iovCur->iov_len; + str->ioDone += str->iovCur->iov_len; + str->iovCur++; + str->iovCurCount--; + } + } +} + +/* Add a stream to Done list and deselect the FD. */ +static void +done(evContext opaqueCtx, evStream *str) { + evContext_p *ctx = opaqueCtx.opaque; + + if (ctx->strLast != NULL) { + str->prevDone = ctx->strLast; + ctx->strLast->nextDone = str; + ctx->strLast = str; + } else { + INSIST(ctx->strDone == NULL); + ctx->strDone = ctx->strLast = str; + } + evDeselectFD(opaqueCtx, str->file); + str->file.opaque = NULL; + /* evDrop() will call evCancelRW() on us. */ +} + +/* Dribble out some bytes on the stream. (Called by evDispatch().) */ +static void +writable(evContext opaqueCtx, void *uap, int fd, int evmask) { + evStream *str = uap; + int bytes; + + bytes = writev(fd, str->iovCur, str->iovCurCount); + if (bytes > 0) { + if ((str->flags & EV_STR_TIMEROK) != 0) + evTouchIdleTimer(opaqueCtx, str->timer); + consume(str, bytes); + } else { + if (bytes < 0 && errno != EINTR) { + str->ioDone = -1; + str->ioErrno = errno; + } + } + if (str->ioDone == -1 || str->ioDone == str->ioTotal) + done(opaqueCtx, str); +} + +/* Scoop up some bytes from the stream. (Called by evDispatch().) */ +static void +readable(evContext opaqueCtx, void *uap, int fd, int evmask) { + evStream *str = uap; + int bytes; + + bytes = readv(fd, str->iovCur, str->iovCurCount); + if (bytes > 0) { + if ((str->flags & EV_STR_TIMEROK) != 0) + evTouchIdleTimer(opaqueCtx, str->timer); + consume(str, bytes); + } else { + if (bytes == 0) + str->ioDone = 0; + else { + if (errno != EINTR) { + str->ioDone = -1; + str->ioErrno = errno; + } + } + } + if (str->ioDone <= 0 || str->ioDone == str->ioTotal) + done(opaqueCtx, str); +} diff --git a/contrib/bind/lib/isc/ev_timers.c b/contrib/bind/lib/isc/ev_timers.c new file mode 100644 index 0000000..198f27c --- /dev/null +++ b/contrib/bind/lib/isc/ev_timers.c @@ -0,0 +1,406 @@ +/* + * Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* ev_timers.c - implement timers for the eventlib + * vix 09sep95 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: ev_timers.c,v 1.23 1998/03/20 23:26:23 halley Exp $"; +#endif + +/* Import. */ + +#include "port_before.h" +#include "fd_setsize.h" + +#include <errno.h> + +#include <isc/eventlib.h> +#include "eventlib_p.h" + +#include "port_after.h" + +/* Constants. */ + +#define BILLION 1000000000 + +/* Forward. */ + +static int due_sooner(void *, void *); +static void set_index(void *, int); +static void free_timer(void *, void *); +static void print_timer(void *, void *); +static void idle_timeout(evContext, void *, struct timespec, struct timespec); + +/* Private type. */ + +typedef struct { + evTimerFunc func; + void * uap; + struct timespec lastTouched; + struct timespec max_idle; + evTimer * timer; +} idle_timer; + +/* Public. */ + +struct timespec +evConsTime(time_t sec, long nsec) { + struct timespec x; + + x.tv_sec = sec; + x.tv_nsec = nsec; + return (x); +} + +struct timespec +evAddTime(struct timespec addend1, struct timespec addend2) { + struct timespec x; + + x.tv_sec = addend1.tv_sec + addend2.tv_sec; + x.tv_nsec = addend1.tv_nsec + addend2.tv_nsec; + if (x.tv_nsec >= BILLION) { + x.tv_sec++; + x.tv_nsec -= BILLION; + } + return (x); +} + +struct timespec +evSubTime(struct timespec minuend, struct timespec subtrahend) { + struct timespec x; + + x.tv_sec = minuend.tv_sec - subtrahend.tv_sec; + if (minuend.tv_nsec >= subtrahend.tv_nsec) + x.tv_nsec = minuend.tv_nsec - subtrahend.tv_nsec; + else { + x.tv_nsec = BILLION - subtrahend.tv_nsec + minuend.tv_nsec; + x.tv_sec--; + } + return (x); +} + +int +evCmpTime(struct timespec a, struct timespec b) { + long x = a.tv_sec - b.tv_sec; + + if (x == 0L) + x = a.tv_nsec - b.tv_nsec; + return (x < 0L ? (-1) : x > 0L ? (1) : (0)); +} + +struct timespec +evNowTime() { + struct timeval now; + struct timespec ret; + + if (gettimeofday(&now, NULL) < 0) + return (evConsTime(0, 0)); + return (evTimeSpec(now)); +} + +struct timespec +evLastEventTime(evContext opaqueCtx) { + evContext_p *ctx = opaqueCtx.opaque; + + return (ctx->lastEventTime); +} + +struct timespec +evTimeSpec(struct timeval tv) { + struct timespec ts; + + ts.tv_sec = tv.tv_sec; + ts.tv_nsec = tv.tv_usec * 1000; + return (ts); +} + +struct timeval +evTimeVal(struct timespec ts) { + struct timeval tv; + + tv.tv_sec = ts.tv_sec; + tv.tv_usec = ts.tv_nsec / 1000; + return (tv); +} + +int +evSetTimer(evContext opaqueCtx, + evTimerFunc func, + void *uap, + struct timespec due, + struct timespec inter, + evTimerID *opaqueID +) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *id; + + evPrintf(ctx, 1, +"evSetTimer(ctx %#x, func %#x, uap %#x, due %d.%09ld, inter %d.%09ld)\n", + ctx, func, uap, + due.tv_sec, due.tv_nsec, + inter.tv_sec, inter.tv_nsec); + + /* due={0,0} is a magic cookie meaning "now." */ + if (due.tv_sec == 0 && due.tv_nsec == 0L) + due = evNowTime(); + + /* Allocate and fill. */ + OKNEW(id); + id->func = func; + id->uap = uap; + id->due = due; + id->inter = inter; + + if (heap_insert(ctx->timers, id) < 0) + return (-1); + + /* Remember the ID if the caller provided us a place for it. */ + if (opaqueID) + opaqueID->opaque = id; + + if (ctx->debug > 7) { + evPrintf(ctx, 7, "timers after evSetTimer:\n"); + (void) heap_for_each(ctx->timers, print_timer, (void *)ctx); + } + + return (0); +} + +int +evClearTimer(evContext opaqueCtx, evTimerID id) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *del = id.opaque; + + if (ctx->cur != NULL && + ctx->cur->type == Timer && + ctx->cur->u.timer.this == del) { + evPrintf(ctx, 8, "deferring delete of timer (executing)\n"); + /* + * Setting the interval to zero ensures that evDrop() will + * clean up the timer. + */ + del->inter = evConsTime(0, 0); + return (0); + } + + if (heap_element(ctx->timers, del->index) != del) + ERR(ENOENT); + + if (heap_delete(ctx->timers, del->index) < 0) + return (-1); + FREE(del); + + if (ctx->debug > 7) { + evPrintf(ctx, 7, "timers after evClearTimer:\n"); + (void) heap_for_each(ctx->timers, print_timer, (void *)ctx); + } + + return (0); +} + +int +evResetTimer(evContext opaqueCtx, + evTimerID id, + evTimerFunc func, + void *uap, + struct timespec due, + struct timespec inter +) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *timer = id.opaque; + struct timespec old_due; + int result=0; + + if (heap_element(ctx->timers, timer->index) != timer) + ERR(ENOENT); + + old_due = timer->due; + + timer->func = func; + timer->uap = uap; + timer->due = due; + timer->inter = inter; + + switch (evCmpTime(due, old_due)) { + case -1: + result = heap_increased(ctx->timers, timer->index); + break; + case 0: + result = 0; + break; + case 1: + result = heap_decreased(ctx->timers, timer->index); + break; + } + + if (ctx->debug > 7) { + evPrintf(ctx, 7, "timers after evResetTimer:\n"); + (void) heap_for_each(ctx->timers, print_timer, (void *)ctx); + } + + return (result); +} + +int +evSetIdleTimer(evContext opaqueCtx, + evTimerFunc func, + void *uap, + struct timespec max_idle, + evTimerID *opaqueID +) { + evContext_p *ctx = opaqueCtx.opaque; + idle_timer *tt; + + /* Allocate and fill. */ + OKNEW(tt); + tt->func = func; + tt->uap = uap; + tt->lastTouched = ctx->lastEventTime; + tt->max_idle = max_idle; + + if (evSetTimer(opaqueCtx, idle_timeout, tt, + evAddTime(ctx->lastEventTime, max_idle), + max_idle, opaqueID) < 0) { + FREE(tt); + return (-1); + } + + tt->timer = opaqueID->opaque; + + return (0); +} + +int +evClearIdleTimer(evContext opaqueCtx, evTimerID id) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *del = id.opaque; + idle_timer *tt = del->uap; + + FREE(tt); + return (evClearTimer(opaqueCtx, id)); +} + +int +evResetIdleTimer(evContext opaqueCtx, + evTimerID opaqueID, + evTimerFunc func, + void *uap, + struct timespec max_idle +) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *timer = opaqueID.opaque; + idle_timer *tt = timer->uap; + + tt->func = func; + tt->uap = uap; + tt->lastTouched = ctx->lastEventTime; + tt->max_idle = max_idle; + + return (evResetTimer(opaqueCtx, opaqueID, idle_timeout, tt, + evAddTime(ctx->lastEventTime, max_idle), + max_idle)); +} + +int +evTouchIdleTimer(evContext opaqueCtx, evTimerID id) { + evContext_p *ctx = opaqueCtx.opaque; + evTimer *t = id.opaque; + idle_timer *tt = t->uap; + + tt->lastTouched = ctx->lastEventTime; + + return (0); +} + +/* Public to the rest of eventlib. */ + +heap_context +evCreateTimers(const evContext_p *ctx) { + return (heap_new(due_sooner, set_index, 2048)); +} + +void +evDestroyTimers(const evContext_p *ctx) { + (void) heap_for_each(ctx->timers, free_timer, NULL); + (void) heap_free(ctx->timers); +} + +/* Private. */ + +static int +due_sooner(void *a, void *b) { + evTimer *a_timer, *b_timer; + + a_timer = a; + b_timer = b; + return (evCmpTime(a_timer->due, b_timer->due) < 0); +} + +static void +set_index(void *what, int index) { + evTimer *timer; + + timer = what; + timer->index = index; +} + +static void +free_timer(void *what, void *uap) { + evTimer *t = what; + FREE(t); +} + +static void +print_timer(void *what, void *uap) { + evTimer *cur = what; + evContext_p *ctx = uap; + + cur = what; + evPrintf(ctx, 7, + " func %p, uap %p, due %d.%09ld, inter %d.%09ld\n", + cur->func, cur->uap, + cur->due.tv_sec, cur->due.tv_nsec, + cur->inter.tv_sec, cur->inter.tv_nsec); +} + +static void +idle_timeout(evContext opaqueCtx, + void *uap, + struct timespec due, + struct timespec inter +) { + evContext_p *ctx = opaqueCtx.opaque; + idle_timer *this = uap; + struct timespec idle; + + idle = evSubTime(ctx->lastEventTime, this->lastTouched); + if (evCmpTime(idle, this->max_idle) >= 0) { + (this->func)(opaqueCtx, this->uap, this->timer->due, + this->max_idle); + /* + * Setting the interval to zero will cause the timer to + * be cleaned up in evDrop(). + */ + this->timer->inter = evConsTime(0, 0); + FREE(this); + } else { + /* evDrop() will reschedule the timer. */ + this->timer->inter = evSubTime(this->max_idle, idle); + } +} diff --git a/contrib/bind/lib/isc/ev_waits.c b/contrib/bind/lib/isc/ev_waits.c new file mode 100644 index 0000000..a45adf1 --- /dev/null +++ b/contrib/bind/lib/isc/ev_waits.c @@ -0,0 +1,245 @@ +/* + * Copyright (c) 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* ev_waits.c - implement deferred function calls for the eventlib + * vix 05dec95 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: ev_waits.c,v 8.6 1998/03/20 23:26:23 halley Exp $"; +#endif + +#include "port_before.h" +#include "fd_setsize.h" + +#include <errno.h> + +#include <isc/eventlib.h> +#include <isc/assertions.h> +#include "eventlib_p.h" + +#include "port_after.h" + +/* Forward. */ + +static void print_waits(evContext_p *ctx); +static evWaitList * evNewWaitList(evContext_p *); +static void evFreeWaitList(evContext_p *, evWaitList *); +static evWaitList * evGetWaitList(evContext_p *, const void *, int); + + +/* Public. */ + +/* + * Enter a new wait function on the queue. + */ +int +evWaitFor(evContext opaqueCtx, const void *tag, + evWaitFunc func, void *uap, evWaitID *id) +{ + evContext_p *ctx = opaqueCtx.opaque; + evWait *new; + evWaitList *wl = evGetWaitList(ctx, tag, 1); + + OKNEW(new); + new->func = func; + new->uap = uap; + new->tag = tag; + new->next = NULL; + if (wl->last != NULL) { + wl->last->next = new; + } else { + wl->first = new; + } + wl->last = new; + if (id != NULL) + id->opaque = new; + if (ctx->debug >= 9) + print_waits(ctx); + return (0); +} + +/* + * Mark runnable all waiting functions having a certain tag. + */ +int +evDo(evContext opaqueCtx, const void *tag) { + evContext_p *ctx = opaqueCtx.opaque; + evWaitList *wl = evGetWaitList(ctx, tag, 0); + evWait *first; + + if (!wl) { + errno = ENOENT; + return (-1); + } + + first = wl->first; + INSIST(first != NULL); + + if (ctx->waitDone.last != NULL) + ctx->waitDone.last->next = first; + else + ctx->waitDone.first = first; + ctx->waitDone.last = wl->last; + evFreeWaitList(ctx, wl); + + return (0); +} + +/* + * Remove a waiting (or ready to run) function from the queue. + */ +int +evUnwait(evContext opaqueCtx, evWaitID id) { + evContext_p *ctx = opaqueCtx.opaque; + evWait *this, *prev; + evWaitList *wl; + int found = 0; + + this = id.opaque; + INSIST(this != NULL); + wl = evGetWaitList(ctx, this->tag, 0); + if (wl != NULL) { + for (prev = NULL, this = wl->first; + this != NULL; + prev = this, this = this->next) + if (this == id.opaque) { + found = 1; + if (prev != NULL) + prev->next = this->next; + else + wl->first = this->next; + if (wl->last == this) + wl->last = prev; + if (wl->first == NULL) + evFreeWaitList(ctx, wl); + break; + } + } + + if (!found) { + /* Maybe it's done */ + for (prev = NULL, this = ctx->waitDone.first; + this != NULL; + prev = this, this = this->next) + if (this == id.opaque) { + found = 1; + if (prev != NULL) + prev->next = this->next; + else + ctx->waitDone.first = this->next; + if (ctx->waitDone.last == this) + ctx->waitDone.last = prev; + break; + } + } + + if (!found) { + errno = ENOENT; + return (-1); + } + + FREE(this); + + if (ctx->debug >= 9) + print_waits(ctx); + + return (0); +} + +int +evDefer(evContext opaqueCtx, evWaitFunc func, void *uap) { + evContext_p *ctx = opaqueCtx.opaque; + evWait *new; + + OKNEW(new); + new->func = func; + new->uap = uap; + new->tag = NULL; + new->next = NULL; + if (ctx->waitDone.last != NULL) + ctx->waitDone.last->next = new; + else + ctx->waitDone.first = new; + ctx->waitDone.last = new; + if (ctx->debug >= 9) + print_waits(ctx); + return (0); +} + +/* Private. */ + +static void +print_waits(evContext_p *ctx) { + evWaitList *wl; + evWait *this; + + evPrintf(ctx, 9, "wait waiting:\n"); + for (wl = ctx->waitLists; wl != NULL; wl = wl->next) { + INSIST(wl->first != NULL); + evPrintf(ctx, 9, " tag %#x:", wl->first->tag); + for (this = wl->first; this != NULL; this = this->next) + evPrintf(ctx, 9, " %#x", this); + evPrintf(ctx, 9, "\n"); + } + evPrintf(ctx, 9, "wait done:"); + for (this = ctx->waitDone.first; this != NULL; this = this->next) + evPrintf(ctx, 9, " %#x", this); + evPrintf(ctx, 9, "\n"); +} + +static evWaitList * +evNewWaitList(evContext_p *ctx) { + evWaitList *new; + + NEW(new); + if (new == NULL) + return (NULL); + new->first = new->last = NULL; + new->prev = NULL; + new->next = ctx->waitLists; + ctx->waitLists = new; + return (new); +} + +static void +evFreeWaitList(evContext_p *ctx, evWaitList *this) { + evWaitList *prev; + + INSIST(this != NULL); + + if (this->prev != NULL) + this->prev->next = this->next; + else + ctx->waitLists = this->next; + if (this->next != NULL) + this->next->prev = this->prev; + FREE(this); +} + +static evWaitList * +evGetWaitList(evContext_p *ctx, const void *tag, int should_create) { + evWaitList *this; + + for (this = ctx->waitLists; this != NULL; this = this->next) { + if (this->first != NULL && this->first->tag == tag) + break; + } + if (this == NULL && should_create) + this = evNewWaitList(ctx); + return (this); +} diff --git a/contrib/bind/lib/isc/eventlib.c b/contrib/bind/lib/isc/eventlib.c new file mode 100644 index 0000000..afb9d9d --- /dev/null +++ b/contrib/bind/lib/isc/eventlib.c @@ -0,0 +1,656 @@ +/* + * Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* eventlib.c - implement glue for the eventlib + * vix 09sep95 [initial] + */ + +#if !defined(LINT) && !defined(CODECENTER) +static const char rcsid[] = "$Id: eventlib.c,v 1.38 1998/03/20 23:26:24 halley Exp $"; +#endif + +#include "port_before.h" +#include "fd_setsize.h" + +#include <sys/types.h> +#include <sys/time.h> +#include <sys/stat.h> + +#include <errno.h> +#include <stdarg.h> +#include <stdlib.h> +#include <unistd.h> + +#include <isc/eventlib.h> +#include <isc/assertions.h> +#include "eventlib_p.h" + +#include "port_after.h" + +/* Forward. */ + +#ifdef NEED_PSELECT +static int pselect(int, void *, void *, void *, struct timespec*); +#endif + +/* Public. */ + +int +evCreate(evContext *opaqueCtx) { + evContext_p *ctx; + int i; + + /* Make sure the memory heap is initialized. */ + if (meminit(0, 0) < 0 && errno != EEXIST) + return (-1); + + OKNEW(ctx); + + /* Global. */ + ctx->cur = NULL; + + /* Debugging. */ + ctx->debug = 0; + ctx->output = NULL; + + /* Connections. */ + ctx->conns = NULL; + INIT_LIST(ctx->accepts); + + /* Files. */ + ctx->files = NULL; + FD_ZERO(&ctx->rdNext); + FD_ZERO(&ctx->wrNext); + FD_ZERO(&ctx->exNext); + ctx->fdMax = -1; + ctx->fdNext = NULL; + ctx->fdCount = 0; /* Invalidate {rd,wr,ex}Last. */ +#ifdef EVENTLIB_TIME_CHECKS + ctx->lastFdCount = 0; +#endif + for (i = 0; i < FD_SETSIZE; i++) + ctx->fdTable[i] = NULL; + + /* Streams. */ + ctx->streams = NULL; + ctx->strDone = NULL; + ctx->strLast = NULL; + + /* Timers. */ + ctx->lastEventTime = evNowTime(); +#ifdef EVENTLIB_TIME_CHECKS + ctx->lastSelectTime = ctx->lastEventTime; +#endif + ctx->timers = evCreateTimers(ctx); + if (ctx->timers == NULL) + return (-1); + + /* Waits. */ + ctx->waitLists = NULL; + ctx->waitDone.first = ctx->waitDone.last = NULL; + ctx->waitDone.prev = ctx->waitDone.next = NULL; + + opaqueCtx->opaque = ctx; + return (0); +} + +void +evSetDebug(evContext opaqueCtx, int level, FILE *output) { + evContext_p *ctx = opaqueCtx.opaque; + + ctx->debug = level; + ctx->output = output; +} + +int +evDestroy(evContext opaqueCtx) { + evContext_p *ctx = opaqueCtx.opaque; + int revs = 424242; /* Doug Adams. */ + evWaitList *this_wl, *next_wl; + evWait *this_wait, *next_wait; + + /* Connections. */ + while (revs-- > 0 && ctx->conns != NULL) { + evConnID id; + + id.opaque = ctx->conns; + (void) evCancelConn(opaqueCtx, id); + } + INSIST(revs >= 0); + + /* Streams. */ + while (revs-- > 0 && ctx->streams != NULL) { + evStreamID id; + + id.opaque = ctx->streams; + (void) evCancelRW(opaqueCtx, id); + } + + /* Files. */ + while (revs-- > 0 && ctx->files != NULL) { + evFileID id; + + id.opaque = ctx->files; + (void) evDeselectFD(opaqueCtx, id); + } + INSIST(revs >= 0); + + /* Timers. */ + evDestroyTimers(ctx); + + /* Waits. */ + for (this_wl = ctx->waitLists; + revs-- > 0 && this_wl != NULL; + this_wl = next_wl) { + next_wl = this_wl->next; + for (this_wait = this_wl->first; + revs-- > 0 && this_wait != NULL; + this_wait = next_wait) { + next_wait = this_wait->next; + FREE(this_wait); + } + FREE(this_wl); + } + for (this_wait = ctx->waitDone.first; + revs-- > 0 && this_wait != NULL; + this_wait = next_wait) { + next_wait = this_wait->next; + FREE(this_wait); + } + + FREE(ctx); + return (0); +} + +int +evGetNext(evContext opaqueCtx, evEvent *opaqueEv, int options) { + evContext_p *ctx = opaqueCtx.opaque; + struct timespec nextTime; + evTimer *nextTimer; + evEvent_p *new; + int x, pselect_errno, timerPast; +#ifdef EVENTLIB_TIME_CHECKS + struct timespec interval; +#endif + + /* Ensure that exactly one of EV_POLL or EV_WAIT was specified. */ + x = ((options & EV_POLL) != 0) + ((options & EV_WAIT) != 0); + if (x != 1) + ERR(EINVAL); + + /* Get the time of day. We'll do this again after select() blocks. */ + ctx->lastEventTime = evNowTime(); + + again: + /* Finished accept()'s do not require a select(). */ + if (!EMPTY(ctx->accepts)) { + OKNEW(new); + new->type = Accept; + new->u.accept.this = HEAD(ctx->accepts); + UNLINK(ctx->accepts, HEAD(ctx->accepts), link); + opaqueEv->opaque = new; + return (0); + } + + /* Stream IO does not require a select(). */ + if (ctx->strDone != NULL) { + OKNEW(new); + new->type = Stream; + new->u.stream.this = ctx->strDone; + ctx->strDone = ctx->strDone->nextDone; + if (ctx->strDone == NULL) + ctx->strLast = NULL; + opaqueEv->opaque = new; + return (0); + } + + /* Waits do not require a select(). */ + if (ctx->waitDone.first != NULL) { + OKNEW(new); + new->type = Wait; + new->u.wait.this = ctx->waitDone.first; + ctx->waitDone.first = ctx->waitDone.first->next; + if (ctx->waitDone.first == NULL) + ctx->waitDone.last = NULL; + opaqueEv->opaque = new; + return (0); + } + + /* Get the status and content of the next timer. */ + if ((nextTimer = heap_element(ctx->timers, 1)) != NULL) { + nextTime = nextTimer->due; + timerPast = (evCmpTime(nextTime, ctx->lastEventTime) <= 0); + } else + timerPast = 0; /* Make gcc happy. */ + + evPrintf(ctx, 9, "evGetNext: fdCount %d\n", ctx->fdCount); + if (ctx->fdCount == 0) { + static const struct timespec NoTime = {0, 0L}; + enum { JustPoll, Block, Timer } m; + struct timespec t, *tp; + + /* Are there any events at all? */ + if ((options & EV_WAIT) != 0 && !nextTimer && ctx->fdMax == -1) + ERR(ENOENT); + + /* Figure out what select()'s timeout parameter should be. */ + if ((options & EV_POLL) != 0) { + m = JustPoll; + t = NoTime; + tp = &t; + } else if (nextTimer == NULL) { + m = Block; + /* ``t'' unused. */ + tp = NULL; + } else if (timerPast) { + m = JustPoll; + t = NoTime; + tp = &t; + } else { + m = Timer; + /* ``t'' filled in later. */ + tp = &t; + } +#ifdef EVENTLIB_TIME_CHECKS + if (ctx->debug > 0) { + interval = evSubTime(ctx->lastEventTime, + ctx->lastSelectTime); + if (interval.tv_sec > 0) + evPrintf(ctx, 1, + "time between pselect() %u.%09u count %d\n", + interval.tv_sec, interval.tv_nsec, + ctx->lastFdCount); + } +#endif + do { + /* XXX need to copy only the bits we are using. */ + ctx->rdLast = ctx->rdNext; + ctx->wrLast = ctx->wrNext; + ctx->exLast = ctx->exNext; + + if (m == Timer) { + INSIST(tp == &t); + t = evSubTime(nextTime, ctx->lastEventTime); + } + + evPrintf(ctx, 4, + "pselect(%d, 0x%lx, 0x%lx, 0x%lx, %d.%09ld)\n", + ctx->fdMax+1, + (u_long)ctx->rdLast.fds_bits[0], + (u_long)ctx->wrLast.fds_bits[0], + (u_long)ctx->exLast.fds_bits[0], + tp ? tp->tv_sec : -1, + tp ? tp->tv_nsec : -1); + + /* XXX should predict system's earliness and adjust. */ + x = pselect(ctx->fdMax+1, + &ctx->rdLast, &ctx->wrLast, &ctx->exLast, + tp); + pselect_errno = errno; + + evPrintf(ctx, 4, "select() returns %d (err: %s)\n", + x, (x == -1) ? strerror(errno) : "none"); + + /* Anything but a poll can change the time. */ + if (m != JustPoll) + ctx->lastEventTime = evNowTime(); + + /* Select() likes to finish about 10ms early. */ + } while (x == 0 && m == Timer && + evCmpTime(ctx->lastEventTime, nextTime) < 0); +#ifdef EVENTLIB_TIME_CHECKS + ctx->lastSelectTime = ctx->lastEventTime; +#endif + if (x < 0) { + if (pselect_errno == EINTR) { + if ((options & EV_NULL) != 0) + goto again; + OKNEW(new); + new->type = Null; + /* No data. */ + opaqueEv->opaque = new; + return (0); + } + if (pselect_errno == EBADF) { + for (x = 0; x <= ctx->fdMax; x++) { + struct stat sb; + + if (FD_ISSET(x, &ctx->rdNext) == 0 && + FD_ISSET(x, &ctx->wrNext) == 0 && + FD_ISSET(x, &ctx->exNext) == 0) + continue; + if (fstat(x, &sb) == -1 && + errno == EBADF) + evPrintf(ctx, 1, "EBADF: %d\n", + x); + } + abort(); + } + ERR(pselect_errno); + } + if (x == 0 && (nextTimer && !timerPast) && (options & EV_POLL)) + ERR(EWOULDBLOCK); + ctx->fdCount = x; +#ifdef EVENTLIB_TIME_CHECKS + ctx->lastFdCount = x; +#endif + } + INSIST(nextTimer || ctx->fdCount); + + /* Timers go first since we'd like them to be accurate. */ + if (nextTimer && !timerPast) { + /* Has anything happened since we blocked? */ + timerPast = (evCmpTime(nextTime, ctx->lastEventTime) <= 0); + } + if (nextTimer && timerPast) { + OKNEW(new); + new->type = Timer; + new->u.timer.this = nextTimer; + opaqueEv->opaque = new; + return (0); + } + + /* No timers, so there should be a ready file descriptor. */ + x = 0; + while (ctx->fdCount > 0) { + evFile *fid; + int fd, eventmask; + + if (ctx->fdNext == NULL) { + if (++x == 2) { + /* + * Hitting the end twice means that the last + * select() found some FD's which have since + * been deselected. + * + * On some systems, the count returned by + * selects is the total number of bits in + * all masks that are set, and on others it's + * the number of fd's that have some bit set, + * and on others, it's just broken. We + * always assume that it's the number of + * bits set in all masks, because that's what + * the man page says it should do, and + * the worst that can happen is we do an + * extra select(). + */ + ctx->fdCount = 0; + break; + } + ctx->fdNext = ctx->files; + } + fid = ctx->fdNext; + ctx->fdNext = fid->next; + + fd = fid->fd; + eventmask = 0; + if (FD_ISSET(fd, &ctx->rdLast)) + eventmask |= EV_READ; + if (FD_ISSET(fd, &ctx->wrLast)) + eventmask |= EV_WRITE; + if (FD_ISSET(fd, &ctx->exLast)) + eventmask |= EV_EXCEPT; + eventmask &= fid->eventmask; + if (eventmask != 0) { + if ((eventmask & EV_READ) != 0) { + FD_CLR(fd, &ctx->rdLast); + ctx->fdCount--; + } + if ((eventmask & EV_WRITE) != 0) { + FD_CLR(fd, &ctx->wrLast); + ctx->fdCount--; + } + if ((eventmask & EV_EXCEPT) != 0) { + FD_CLR(fd, &ctx->exLast); + ctx->fdCount--; + } + OKNEW(new); + new->type = File; + new->u.file.this = fid; + new->u.file.eventmask = eventmask; + opaqueEv->opaque = new; + return (0); + } + } + if (ctx->fdCount < 0) { + /* + * select()'s count is off on a number of systems, and + * can result in fdCount < 0. + */ + evPrintf(ctx, 4, "fdCount < 0 (%d)\n", ctx->fdCount); + ctx->fdCount = 0; + } + + /* We get here if the caller deselect()'s an FD. Gag me with a goto. */ + goto again; +} + +int +evDispatch(evContext opaqueCtx, evEvent opaqueEv) { + evContext_p *ctx = opaqueCtx.opaque; + evEvent_p *ev = opaqueEv.opaque; +#ifdef EVENTLIB_TIME_CHECKS + void *func; + struct timespec start_time; + struct timespec interval; +#endif + +#ifdef EVENTLIB_TIME_CHECKS + if (ctx->debug > 0) + start_time = evNowTime(); +#endif + ctx->cur = ev; + switch (ev->type) { + case Accept: { + evAccept *this = ev->u.accept.this; + + evPrintf(ctx, 5, + "Dispatch.Accept: fd %d -> %d, func %#x, uap %#x\n", + this->conn->fd, this->fd, + this->conn->func, this->conn->uap); + errno = this->ioErrno; + (this->conn->func)(opaqueCtx, this->conn->uap, this->fd, + &this->la, this->lalen, + &this->ra, this->ralen); +#ifdef EVENTLIB_TIME_CHECKS + func = this->conn->func; +#endif + break; + } + case File: { + evFile *this = ev->u.file.this; + int eventmask = ev->u.file.eventmask; + + evPrintf(ctx, 5, + "Dispatch.File: fd %d, mask 0x%x, func %#x, uap %#x\n", + this->fd, this->eventmask, this->func, this->uap); + (this->func)(opaqueCtx, this->uap, this->fd, eventmask); +#ifdef EVENTLIB_TIME_CHECKS + func = this->func; +#endif + break; + } + case Stream: { + evStream *this = ev->u.stream.this; + + evPrintf(ctx, 5, + "Dispatch.Stream: fd %d, func %#x, uap %#x\n", + this->fd, this->func, this->uap); + errno = this->ioErrno; + (this->func)(opaqueCtx, this->uap, this->fd, this->ioDone); +#ifdef EVENTLIB_TIME_CHECKS + func = this->func; +#endif + break; + } + case Timer: { + evTimer *this = ev->u.timer.this; + + evPrintf(ctx, 5, "Dispatch.Timer: func %#x, uap %#x\n", + this->func, this->uap); + (this->func)(opaqueCtx, this->uap, this->due, this->inter); +#ifdef EVENTLIB_TIME_CHECKS + func = this->func; +#endif + break; + } + case Wait: { + evWait *this = ev->u.wait.this; + + evPrintf(ctx, 5, + "Dispatch.Wait: tag %#x, func %#x, uap %#x\n", + this->tag, this->func, this->uap); + (this->func)(opaqueCtx, this->uap, this->tag); +#ifdef EVENTLIB_TIME_CHECKS + func = this->func; +#endif + break; + } + case Null: { + /* No work. */ +#ifdef EVENTLIB_TIME_CHECKS + func = NULL; +#endif + break; + } + default: { + abort(); + } + } +#ifdef EVENTLIB_TIME_CHECKS + if (ctx->debug > 0) { + interval = evSubTime(evNowTime(), start_time); + /* + * Complain if it took longer than 50 milliseconds. + * + * We call getuid() to make an easy to find mark in a kernel + * trace. + */ + if (interval.tv_sec > 0 || interval.tv_nsec > 50000000) + evPrintf(ctx, 1, + "dispatch interval %u.%09u uid %d type %d func %p\n", + interval.tv_sec, interval.tv_nsec, + getuid(), ev->type, func); + } +#endif + ctx->cur = NULL; + evDrop(opaqueCtx, opaqueEv); + return (0); +} + +void +evDrop(evContext opaqueCtx, evEvent opaqueEv) { + evContext_p *ctx = opaqueCtx.opaque; + evEvent_p *ev = opaqueEv.opaque; + + switch (ev->type) { + case Accept: { + FREE(ev->u.accept.this); + break; + } + case File: { + /* No work. */ + break; + } + case Stream: { + evStreamID id; + + id.opaque = ev->u.stream.this; + (void) evCancelRW(opaqueCtx, id); + break; + } + case Timer: { + evTimer *this = ev->u.timer.this; + evTimerID opaque; + + /* Check to see whether the user func cleared the timer. */ + if (heap_element(ctx->timers, this->index) != this) { + evPrintf(ctx, 5, "Dispatch.Timer: timer rm'd?\n"); + break; + } + /* + * Timer is still there. Delete it if it has expired, + * otherwise set it according to its next interval. + */ + if (this->inter.tv_sec == 0 && this->inter.tv_nsec == 0L) { + opaque.opaque = this; + (void) evClearTimer(opaqueCtx, opaque); + } else { + opaque.opaque = this; + (void) evResetTimer(opaqueCtx, opaque, this->func, + this->uap, + evAddTime(ctx->lastEventTime, + this->inter), + this->inter); + } + break; + } + case Wait: { + FREE(ev->u.wait.this); + break; + } + case Null: { + /* No work. */ + break; + } + default: { + abort(); + } + } + FREE(ev); +} + +int +evMainLoop(evContext opaqueCtx) { + evEvent event; + int x; + + while ((x = evGetNext(opaqueCtx, &event, EV_WAIT)) == 0) + if ((x = evDispatch(opaqueCtx, event)) < 0) + break; + return (x); +} + +void +evPrintf(const evContext_p *ctx, int level, const char *fmt, ...) { + va_list ap; + + va_start(ap, fmt); + if (ctx->output != NULL && ctx->debug >= level) { + vfprintf(ctx->output, fmt, ap); + fflush(ctx->output); + } + va_end(ap); +} + +#ifdef NEED_PSELECT +static int +pselect(int nfds, void *rfds, void *wfds, void *efds, struct timespec *tsp) { + struct timeval tv, *tvp; + int n; + + if (tsp) { + tvp = &tv; + tv = evTimeVal(*tsp); + } else + tvp = NULL; + n = select(nfds, rfds, wfds, efds, tvp); + if (tsp) + *tsp = evTimeSpec(tv); + return (n); +} +#endif diff --git a/contrib/bind/lib/isc/eventlib.mdoc b/contrib/bind/lib/isc/eventlib.mdoc new file mode 100644 index 0000000..f0e31e1 --- /dev/null +++ b/contrib/bind/lib/isc/eventlib.mdoc @@ -0,0 +1,829 @@ +.\" $Id: eventlib.mdoc,v 1.18 1998/01/26 23:00:56 halley Exp $ +.\" +.\"Copyright (c) 1995, 1996, 1997 by Internet Software Consortium +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.Dd March 6, 1996 +.Dt EVENTLIB 3 +.Os BSD 4 +.Sh NAME +.Nm evConnFunc , +.Nm evFileFunc , +.Nm evStreamFunc , +.Nm evTimerFunc , +.Nm evWaitFunc , +.Nm evCreate , +.Nm evDestroy , +.Nm evGetNext , +.Nm evDispatch , +.Nm evDrop , +.Nm evMainLoop , +.Nm evConsTime , +.Nm evTimeSpec , +.Nm evTimeVal , +.Nm evAddTime , +.Nm evSubTime , +.Nm evCmpTime , +.Nm evNowTime , +.Nm evLastEventTime , +.Nm evSetTimer , +.Nm evResetTimer , +.Nm evClearTimer , +.Nm evSetIdleTimer , +.Nm evTouchIdleTimer , +.Nm evClearIdleTimer , +.Nm evWaitFor , +.Nm evDo , +.Nm evUnwait , +.Nm evDefer , +.Nm evSelectFD , +.Nm evDeselectFD , +.Nm evWrite , +.Nm evRead , +.Nm evCancelRW , +.Nm evTimeRW , +.Nm evUntimeRW , +.Nm evListen , +.Nm evConnect , +.Nm evCancelConn , +.Nm evHold , +.Nm evUnhold , +.Nm evTryAccept , +.Nm evConsIovec , +.Nm evSetDebug , +.Nm evPrintf +.Nd event handling library +.Sh SYNOPSIS +.Fd #include <isc/eventlib.h> +.Ft typedef void +.Fn (*evConnFunc) "evContext ctx" "void *uap" "int fd" \ +"const void *la" "int lalen" "const void *ra" "int ralen" +.Ft typedef void +.Fn (*evTimerFunc) "evContext ctx" "void *uap" \ +"struct timespec due" "struct timespec inter" +.Ft typedef void +.Fn (*evFileFunc) "evContext ctx" "void *uap" "int fd" "int eventmask" +.Ft typedef void +.Fn (*evStreamFunc) "evContext ctx" "void *uap" "int fd" "int bytes" +.Ft typedef void +.Fn (*evWaitFunc) "evContext ctx" "void *uap" "const void *tag" +.Ft int +.Fn evCreate "evContext *ctx" +.Ft int +.Fn evDestroy "evContext ctx" +.Ft int +.Fn evGetNext "evContext ctx" "evEvent *ev" "int options" +.Ft int +.Fn evDispatch "evContext ctx" "evEvent ev" +.Ft void +.Fn evDrop "evContext ctx" "evEvent ev" +.Ft int +.Fn evMainLoop "evContext ctx" +.Ft struct timespec +.Fn evConsTime "int sec" "int usec" +.Ft struct timespec +.Fn evTimeSpec "struct timeval tv" +.Ft struct timeval +.Fn evTimeVal "struct timespec ts" +.Ft struct timespec +.Fn evAddTime "struct timespec addend1" "struct timespec addend2" +.Ft struct timespec +.Fn evSubTime "struct timespec minuend" "struct timespec subtrahend" +.Ft struct timespec +.Fn evCmpTime "struct timespec a" "struct timespec b" +.Ft struct timespec +.Fn evNowTime "void" +.Ft struct timespec +.Fn evLastEventTime "evContext opaqueCtx" +.Ft int +.Fn evSetTimer "evContext ctx" "evTimerFunc func" "void *uap" \ +"struct timespec due" "struct timespec inter" "evTimerID *id" +.Ft int +.Fn evResetTimer "evContext ctx" "evTimerID id" "evTimerFunc func" \ +"void *uap" "struct timespec due" "struct timespec inter" +.Ft int +.Fn evClearTimer "evContext ctx" "evTimerID id" +.Ft int +.Fn evSetIdleTimer "evContext opaqueCtx" "evTimerFunc func" "void *uap" \ +"struct timespec max_idle" "evTimerID *opaqueID" +.Ft int +.Fn evTouchIdleTimer "evContext opaqueCtx" "evTimerID id" +.Ft int +.Fn evResetIdleTimer "evContext opaqueCtx" "evTimerID id" "evTimerFunc func" \ +"void *uap" "struct timespec max_idle" +.Ft int +.Fn evClearIdleTimer "evContext opaqueCtx" "evTimerID id" +.Ft int +.Fn evWaitFor "evContext opaqueCtx" "const void *tag" \ +"evWaitFunc func" "void *uap" "evWaitID *id" +.Ft int +.Fn evDo "evContext opaqueCtx" "const void *tag" +.Ft int +.Fn evUnwait "evContext opaqueCtx" "evWaitID id" +.Ft int +.Fn evDefer "evContext opaqueCtx" "evWaitFunc func" "void *uap" +.Ft int +.Fn evSelectFD "evContext ctx" "int fd" "int eventmask" \ +"evFileFunc func" "void *uap" "evFileID *id" +.Ft int +.Fn evDeselectFD "evContext ctx" "evFileID id" +.Ft struct iovec +.Fn evConsIovec "void *buf" "size_t cnt" +.Ft int +.Fn evWrite "evContext ctx" "int fd" "const struct iovec *iov" "int cnt" \ +"evStreamFunc func" "void *uap" "evStreamID *id" +.Ft int +.Fn evRead "evContext ctx" "int fd" "const struct iovec *iov" "int cnt" \ +"evStreamFunc func" "void *uap" "evStreamID *id" +.Ft int +.Fn evCancelRW "evContext ctx" "evStreamID id" +.Ft int +.Fn evTimeRW "evContext opaqueCtx" "evStreamID id" "evTimerID timer" +.Ft int +.Fn evUntimeRW "evContext opaqueCtx" "evStreamID id" +.Ft int +.Fn evListen "evContext ctx" "int fd" "int maxconn" \ +"evConnFunc func" "void *uap" "evConnID *id" +.Ft int +.Fn evConnect "evContext ctx" "int fd" "void *ra" "int ralen" \ +"evConnFunc func" "void *uap" "evConnID *id" +.Ft int +.Fn evCancelConn "evContext ctx" "evConnID id" +.Ft int +.Fn evHold "evContext ctx" "evConnID id" +.Ft int +.Fn evUnhold "evContext ctx" "evConnID id" +.Ft int +.Fn evTryAccept "evContext ctx" "evConnID id" "int *sys_errno" +.Ft void +.Fn evSetDebug "evContext ctx" "int level" "FILE *output" +.Ft void +.Fn evPrintf "const evContext_p *ctx" "int level" "const char *fmt" "..." +.Sh DESCRIPTION +This library provides multiple outstanding asynchronous timers and I/O +to a cooperating application. The model is similar to that of the X +Toolkit, in that events are registered with the library and the application +spends most of its time in the +.Fn evMainLoop +function. If an application already has a main loop, it can safely register +events with this library as long as it periodically calls the +.Fn evGetNext +and +.Fn evDispatch +functions. (Note that +.Fn evGetNext +has both polling and blocking modes.) +.Pp +The function +.Fn evCreate +creates an event context which is needed by all the other functions in this +library. All information used internally by this library is bound to this +context, rather than to static storage. This makes the library +.Dq thread safe, +and permits other library functions to use events without +disrupting the application's use of events. +.Pp +The function +.Fn evDestroy +destroys a context that has been created by +.Fn evCreate . +All dynamic memory bound to this context will be freed. An implicit +.Fn evTimerClear +will be done on all timers set in this event context. An implicit +.Fn evDeselectFD +will be done on all file descriptors selected in this event context. +.Pp +The function +.Fn evGetNext +potentially waits for and then retrieves the next asynchronous event, +placing it in the object of the +.Fa ev +pointer argument. The following +.Fa options +are available: +.Fa EV_POLL , +meaning that +.Fn evGetNext +should not block, but rather return +.Dq Fa -1 +with +.Fa errno +set to +.Fa EWOULDBLOCK +if no events have occurred; +.Fa EV_WAIT , +which tells +.Fn evGetNext +to block internally until the next event occurs; and +.Fa EV_NULL , +which tells +.Fn evGetNext +that it should return a special +.Dq no-op +event, which is ignored by +.Fn evDispatch +but handled correctly by +.Fn evDrop . +.Fa EV_NULL +can be necessary to the correct functioning of a caller\-written equivilent to +.Fn evMainLoop , +wherein perterbations caused by external system events must be polled for, and +the default behaviour of internally ignoring such events is undesirable. +Note that +.Fa EV_POLL +and +.Fa EV_WAIT +are mutually exclusive. +.Pp +The function +.Fn evDispatch +dispatches an event retrieved by +.Fn evGetNext . +This usually involves calling the function that was associated with the event +when the event was registered with +.Fn evSetTimer , +.Fn evResetTimer , +or +.Fn evSelectFD . +All events retrieved by +.Fn evGetNext +must be given over to +.Fn evDispatch +at some point, since there is some dynamic memory associated with each event. +.Pp +The function +.Fn evDrop +deallocates dynamic memory that has been allocated by +.Fn evGetNext . +Calling +.Fn evDispatch +has the side effect of calling +.Fn evDrop , +but if you are going to drop the event rather than dispatch it, you will have +to call +.Fn evDrop +directly. +.Pp +The function +.Fn evMainLoop +is just: +.Bd -literal -offset indent +while ((x = evGetNext(opaqueCtx, &event, EV_WAIT)) == 0) + if ((x = evDispatch(opaqueCtx, event)) < 0) + break; +return (x); +.Ed +.Pp +In other words, get events and dispatch them until an error occurs. One such +error would be that all the events under this context become unregistered; in +that event, there will be nothing to wait for and +.Fn evGetNext +becomes an undefined operation. +.Pp +The function +.Fn evConsTime +is a constructor for +.Dq Fa struct timespec +which allows these structures to be created and then passed as arguments to +other functions without the use of temporary variables. (If C had inline +constructors, there would be no need for this function.) +.Pp +The functions +.Fn evTimeSpec +and +.Fn evTimeVal +are utilities which allow the caller to convert a +.Dq Fa struct timeval +to a +.Dq Fa struct timespec +(the function of +.Fn evTimeSpec ) +or vice versa (the function of +.Fn evTimeVal ) . +Note that the name of the function indicates the type of the return value. +.Pp +The function +.Fn evAddTime +adds two +.Dq Fa struct timespec +values and returns the result as a +.Dq Fa struct timespec. +.Pp +The function +.Fn evSubTime +subtracts its second +.Dq Fa struct timespec +argument from its first +.Dq Fa struct timespec +argument and returns the result as a +.Dq Fa struct timespec. +.Pp +The function +.Fn evCmpTime +compares its two +.Dq Fa struct timespec +arguments and returns an +.Dq Fa int +that is less than zero if the first argument specifies an earlier time than +the second, or more than zero if the first argument specifies a later time +than the second, or equal to zero if both arguments specify the same time. +.Pp +The function +.Fn evNowTime +returns a +.Dq Fa struct timespec +which either describes the current time (using +.Xr gettimeofday 2 ) , +if successful, or has its fields set to zero, if there is an error. +(In the latter case, the caller can check +.Va errno , +since it will be set by +.Xr gettimeofday 2 . ) +.Pp +The function +.Fn evLastEventTime +returns the +.Dq Fa struct timespec +which describes the last time that certain events happened to the +event context indicated by +.Fa opaqueCtx . +This value is updated by +.Fn evCreate +and +.Fn evGetNext +(upon entry and after +.Xr select 2 +returns); it is routinely compared with other times in the internal handling +of, e.g., timers. +.Pp +The function +.Fn evSetTimer +registers a timer event, which will be delivered as a function call to the +function specified by the +.Fa func +argument. The event will be delivered at absolute time +.Fa due , +and then if time +.Fa inter +is not equal to +.Dq Fa evConsTime(0,0) , +subsequently at intervals equal to time +.Fa inter . +As a special case, specifying a +.Fa due +argument equal to +.Dq Fa evConsTime(0,0) +means +.Dq due immediately. +The +.Fa opaqueID +argument, if specified as a value other than +.Fa NULL , +will be used to store the resulting +.Dq timer \s-1ID\s+1 , +useful as an argument to +.Fn evClearTimer . +Note that in a +.Dq one\-shot +timer (which has an +.Fa inter +argument equal to +.Dq Fa evConsTime(0,0) +.\" putting the ) after the Dq Fa arg did not work well. --vix +) the user function +.Fa func +should deallocate any dynamic memory that is uniquely bound to the +.Fa uap , +since no handles to this memory will exist within the event library +after a one\-shot timer has been delivered. +.Pp +The function +.Fn evResetTimer +resets the values of the timer specified by +.Fa id +to the given arguments. The arguments are the same as in the description of +.Fn evSetTimer +above. +.Pp +The function +.Fn evClearTimer +will unregister the timer event specified by +.Fa id . +Note that if the +.Fa uap +specified in the corresponding +.Fn evSetTimer +call is uniquely bound to any dynamic memory, then that dynamic memory should +be freed by the caller before the handle is lost. After a call to +.Fn evClearTimer , +no handles to this +.Fa uap +will exist within the event library. +.Pp +The function +.Fn evSetIdleTimer +is similar to (and built on) +.Fn evSetTimer ; +it registers an idle timer event which provides for the function call to +.Fa func +to occur. However, for an +.Em idle +timer, the call will occur after at least +.Dq Fa max_idle +time has passed since the time the idle timer was +.Dq last touched ; +originally, this is set to the time returned by +.Fn evLastEventTime +(described above) for the event context specified by +.Fa opaqueCtx . +This is a +.Dq one\-shot +timer, but the time at which the +.Fa func +is actually called can be changed by recourse to +.Fn evTouchIdleTimer +(described below). The pointer to the underlying +.Dq timer \s-1ID\s+1 +is returned in +.Fa opaqueID , +if it is +.No non- Ns Dv NULL . +.Pp +The +.Fn evTouchIdleTimer +function updates the idle timer associated with +.Fa id , +setting its idea of the time it was last accessed to the value returned by +.Fn evLastEventTime +(described above) for the event context specified by +.Fa opaqueCtx . +This means that the idle timer will expire after at least +.Fa max_idle +time has passed since this (possibly new) time, providing a caller mechanism +for resetting the call to the +.Fa func +associated with the idle timer. (See the description of +.Fn evSetIdleTimer , +above, for information about +.Fa func +and +.Fa max_idle . ) +.Pp +The +.Fn evResetIdleTimer +function reschedules a timer and resets the callback function and its argument. +Note that resetting a timer also ``touches'' it. +.Pp +The +.Fn evClearIdleTimer +function unregisters the idle timer associated with +.Fa id . +See the discussion under +.Fn evClearTimer , +above, for information regarding caller handling of the +.Fa uap +associated with the corresponding +.Fn evSetIdleTimer +call. +.Pp +The function +.Fn evWaitFor +places the function +.Fa func +on the given event context's wait queue with the associated (possibly +.Dv NULL ) +.Dq Fa tag ; +if +.Fa id +is +.No non- Ns Dv NULL , +then it will contain the +.Dq wait \s-1ID\s+1 +associated with the created queue element. +.Pp +The function +.Fn evDo +marks +.Em all +of the +.Dq waiting +functions in the given event context's wait queue with the associated (possibly +.Dv NULL ) +.Dq Fa tag +as runnable. This places these functions in a +.Dq done +queue which will be read by +.Fn evGetNext . +.Pp +The function +.Fn evUnwait +will search for the +.Dq wait \s-1ID\s+1 +.Fa id +in the wait queue of the given event context; if an element with the given +.Fa id +is not found, then the +.Dq done +queue of that context is searched. If found, the queue element is removed +from the appropriate list. +.Pp +The function +.Fn evDefer +causes a function (specified as +.Fa func , +with argument +.Fa uap ) +to be dispatched at some later time. Note that the +.Fa tag +argument to +.Fa func +will always be +.Fa NULL +when dispatched. +.Pp +The function +.Fn evSelectFD +registers a file I/O event for the file descriptor specified by +.Fa fd . +Bits in the +.Fa eventmask +argument are named +.Fa EV_READ , +.Fa EV_WRITE , +and +.Fa EV_EXCEPT . +At least one of these bits must be specified. If the +.Fa id +argument is not equal to +.Fa NULL , +it will be used to store a unique ``file event \s-1ID\s+1'' for this event, +which is useful in subsequent calls to +.Fn evDeselectFD . +A file descriptor will be made nonblocking using the +.Fa O_NONBLOCK +flag with +.Xr fcntl 2 +on its first concurrent registration via +.Fn evSelectFD . +An +.Fn evSelectFD +remains in effect until cancelled via +.Fn evDeselectFD . +.Pp +The function +.Fn evDeselectFD +unregisters the ``file event'' specified by the +.Fa id +argument. If the corresponding +.Fa uap +uniquely points to dynamic memory, that memory should be freed before its +handle is lost, since after a call to +.Fn evDeselectFD , +no handles to this event's +.Fa uap +will remain within the event library. A file descriptor will be taken out of +nonblocking mode (see +.Fa O_NONBLOCK +and +.Xr fcntl 2 ) +when its last event registration is removed via +.Fn evDeselectFD , +if it was in blocking mode before the first registration via +.Fn evSelectFD . +.Pp +The function +.Fn evConsIovec +is a constructor for a single +.Ft struct iovec +structure, which is useful for +.Fn evWrite +and +.Fn evRead . +.Pp +The functions +.Fn evWrite +and +.Fn evRead +start asynchronous stream I/O operations on file descriptor +.Fa fd . +The data to be written or read is in the scatter/gather descriptor specified by +.Fa iov +and +.Fa cnt . +The supplied function +.Fa func +will be called with argument +.Fa uap +when the I/O operation is complete. If +.Fa id +is not +.Fa NULL , +it will be filled a with the stream event identifier suitable for use with +.Fn evCancelRW . +.Pp +The function +.Fn evCancelRW +extinguishes an outstanding +.Fn evWrite +or +.Fn evRead +call. System I/O calls cannot always be cancelled, but you are guaranteed +that the +.Fa func +function supplied to +.Fn evWrite +or +.Fn evRead +will not be called after a call to +.Fn evCancelRW . +Care should be taken not to deallocate or otherwise reuse the space pointed +to by the segment descriptors in +.Fa iov +unless the underlying file descriptor is closed first. +.Pp +The function +.Fn evTimeRW +sets the stream associated with the given stream \s-1ID\s+1 +.Dq Fa id +to have the idle timer associated with the timer \s-1ID\s+1 +.Dq Fa timer . +.Pp +The function +.Fn evUntimeRW +says that the stream associated with the given stream \s-1ID\s+1 +.Dq Fa id +should ignore its idle timer, if present. +.Pp +The functions +.Fn evListen , +.Fn evConnect , +and +.Fn evCancelConn +can be used to manage asynchronous incoming and outgoing socket connections. +Sockets to be used with these functions should first be created with +.Xr socket 2 +and given a local name with +.Xr bind 2 . +It is extremely unlikely that the same socket will ever be +useful for both incoming and outgoing connections. The +.Fa id +argument to +.Fn evListen +and +.Fn evConnect +is either +.Fa NULL +or the address of a +.Ft evFileID +variable which can then be used in a subsequent call to +.Fn evCancelConn . +.Pp +After a call to +.Fn evListen , +each incoming connection arriving on +.Fa fd +will cause +.Fa func +to be called with +.Fa uap +as one of its arguments. +.Fn evConnect +initiates an outgoing connection on +.Fa fd +to destination address +.Fa ra +(whose length is +.Fa ralen ). +When the connection is complete, +.Fa func +will be called with +.Fa uap +as one of its arguments. The argument +.Fa fd +to +.Fn (*func)() +will be +.Fa -1 +if an error occurred that prevented this connection from completing +successfully. In this case +.Fn errno +will have been set and the socket described by +.Fa fd +will have been closed. The +.Fn evCancelConn +function will prevent delivery of all pending and subsequent +events for the outstanding connection. The +.Fn evHold +function will suspend the acceptance of new connections on the listener +specified by +.Fa id . +Connections will be queued by the protocol stack up to the system's limit. The +.Fn evUnhold +function will reverse the effects of +.Fn evHold , +allowing incoming connections to be delivered for listener +.Fa id . +The +.Fn evTryAccept +function will poll the listener specified by +.Fa id , +accepting a new connection if one is available, and queuing a connection event +for later retrieval by +.Fn evGetNext . +If the connection event queued is an accept error(), sys_errno will contain +the error code; otherwise it will be zero. All connection events queued by +.Fn evTryAccept +will be delivered by +.Fn evGetNext +before a new select is done on the listener. +.Pp +The function +.Fn evSetDebug +sets the debugging +.Fa level +and diagnostic +.Fa output +file handle for an event context. Greater numeric levels will +result in more verbose output being sent to the output FILE during program +execution. +.Pp +The function +.Fn evPrintf +prints a message with the format +.Dq Fa fmt +and the following arguments (if any), on the output stream associated +with the event context pointed to by +.Fa ctx . +The message is output if the event context's debug level is greater than +or equal to the indicated +.Fa level . +.Sh RETURN VALUES +All the functions whose return type is +.Dq Fa int +use the standard convention of returning zero (0) to indicate success, or +returning +.Dq Fa -1 +and setting +.Fa errno +to indicate failure. +.Sh FILE +.Pa heap.h , +which is in the +.Pa src/lib/isc +directory of the current +.Sy BIND +distribution. +.Sh ERRORS +The possible values for +.Fa errno +when one of the +.Dq Fa int +functions in this library returns +.Dq Fa -1 +include those of the Standard C Library and also: +.Bl -tag -width EWOULDBLOCKAA +.It Bq Er EINVAL +Some function argument has an unreasonable value. +.It Bq Er EINVAL +The specified file descriptor has an integer value greater than the default +.Fa FD_SETSIZE , +meaning that the application's limit is higher than the library's. +.It Bq Er ENOENT +The specified +.Dq event \s-1ID\s+1 +does not exist. +.It Bq Er EWOULDBLOCK +No events have occurred and the +.Fa EV_POLL +option was specified. +.It Bq Er EBADF +The specified signal was unblocked outside the library. +.El +.Sh SEE ALSO +.Xr gettimeofday 2 , +.Xr select 2 , +.Xr fcntl 3 , +.Xr malloc 3 , +.Xr @INDOT@named @SYS_OPS_EXT@ , +.Xr readv 3 , +.Xr writev 3 . +.Sh BUGS +This huge man page needs to be broken up into a handful of smaller ones. +.Sh HISTORY +The +.Nm eventlib +library was designed by Paul Vixie with excellent advice from his friends +and with tips 'o the cap to the X Consortium and the implementors of DEC SRC +Modula-3. diff --git a/contrib/bind/lib/isc/eventlib_p.h b/contrib/bind/lib/isc/eventlib_p.h new file mode 100644 index 0000000..2606333 --- /dev/null +++ b/contrib/bind/lib/isc/eventlib_p.h @@ -0,0 +1,199 @@ +/* + * Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* eventlib_p.h - private interfaces for eventlib + * vix 09sep95 [initial] + * + * $Id: eventlib_p.h,v 1.25 1998/02/06 01:53:54 halley Exp $ + */ + +#ifndef _EVENTLIB_P_H +#define _EVENTLIB_P_H + +#include <sys/param.h> +#include <sys/types.h> +#include <sys/socket.h> + +#define EVENTLIB_DEBUG 1 + +#include <errno.h> +#include <fcntl.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +#include <isc/heap.h> +#include <isc/list.h> +#include <isc/memcluster.h> + +#define EV_MASK_ALL (EV_READ | EV_WRITE | EV_EXCEPT) +#define ERR(e) return (errno = (e), -1) +#define OK(x) if ((x) < 0) ERR(errno); else (void)NULL + +#define NEW(p) if (((p) = memget(sizeof *(p))) != NULL) \ + FILL(p); \ + else \ + (void)NULL; +#define OKNEW(p) if (!((p) = memget(sizeof *(p)))) { \ + errno = ENOMEM; \ + return (-1); \ + } else \ + FILL(p) +#define FREE(p) memput((p), sizeof *(p)) + +#if EVENTLIB_DEBUG +#define FILL(p) memset((p), 0xF5, sizeof *(p)) +#else +#define FILL(p) +#endif + +typedef struct evConn { + evConnFunc func; + void * uap; + int fd; + int flags; +#define EV_CONN_LISTEN 0x0001 /* Connection is a listener. */ +#define EV_CONN_SELECTED 0x0002 /* evSelectFD(conn->file). */ +#define EV_CONN_BLOCK 0x0004 /* Listener fd was blocking. */ + evFileID file; + struct evConn * prev; + struct evConn * next; +} evConn; + +typedef struct evAccept { + int fd; + struct sockaddr la; + int lalen; + struct sockaddr ra; + int ralen; + int ioErrno; + evConn * conn; + LINK(struct evAccept) link; +} evAccept; + +typedef struct evFile { + evFileFunc func; + void * uap; + int fd; + int eventmask; + int preemptive; + struct evFile * prev; + struct evFile * next; + struct evFile * fdprev; + struct evFile * fdnext; +} evFile; + +typedef struct evStream { + evStreamFunc func; + void * uap; + evFileID file; + evTimerID timer; + int flags; +#define EV_STR_TIMEROK 0x0001 /* IFF timer valid. */ + int fd; + struct iovec * iovOrig; + int iovOrigCount; + struct iovec * iovCur; + int iovCurCount; + int ioTotal; + int ioDone; + int ioErrno; + struct evStream *prevDone, *nextDone; + struct evStream *prev, *next; +} evStream; + +typedef struct evTimer { + evTimerFunc func; + void * uap; + struct timespec due, inter; + int index; +} evTimer; + +typedef struct evWait { + evWaitFunc func; + void * uap; + const void * tag; + struct evWait * next; +} evWait; + +typedef struct evWaitList { + evWait * first; + evWait * last; + struct evWaitList * prev; + struct evWaitList * next; +} evWaitList; + +typedef struct evEvent_p { + enum { Accept, File, Stream, Timer, Wait, Free, Null } type; + union { + struct { evAccept *this; } accept; + struct { evFile *this; int eventmask; } file; + struct { evStream *this; } stream; + struct { evTimer *this; } timer; + struct { evWait *this; } wait; + struct { struct evEvent_p *next; } free; + struct { const void *placeholder; } null; + } u; +} evEvent_p; + +typedef struct { + /* Global. */ + const evEvent_p *cur; + /* Debugging. */ + int debug; + FILE *output; + /* Connections. */ + evConn *conns; + LIST(evAccept) accepts; + /* Files. */ + evFile *files, *fdNext; + fd_set rdLast, rdNext; + fd_set wrLast, wrNext; + fd_set exLast, exNext; + fd_set nonblockBefore; + int fdMax, fdCount; + evFile *fdTable[FD_SETSIZE]; +#ifdef EVENTLIB_TIME_CHECKS + struct timespec lastSelectTime; + int lastFdCount; +#endif + /* Streams. */ + evStream *streams; + evStream *strDone, *strLast; + /* Timers. */ + struct timespec lastEventTime; + heap_context timers; + /* Waits. */ + evWaitList *waitLists; + evWaitList waitDone; +} evContext_p; + +/* eventlib.c */ +#define evPrintf __evPrintf +void evPrintf(const evContext_p *ctx, int level, const char *fmt, ...); + +/* ev_timers.c */ +#define evCreateTimers __evCreateTimers +heap_context evCreateTimers(const evContext_p *); +#define evDestroyTimers __evDestroyTimers +void evDestroyTimers(const evContext_p *); + +/* ev_waits.c */ +#define evFreeWait __evFreeWait +evWait *evFreeWait(evContext_p *ctx, evWait *old); + +#endif /*_EVENTLIB_P_H*/ diff --git a/contrib/bind/lib/isc/heap.c b/contrib/bind/lib/isc/heap.c new file mode 100644 index 0000000..821d323 --- /dev/null +++ b/contrib/bind/lib/isc/heap.c @@ -0,0 +1,221 @@ +/* + * Copyright (c) 1997 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/* + * Heap implementation of priority queues adapted from the following: + * + * _Introduction to Algorithms_, Cormen, Leiserson, and Rivest, + * MIT Press / McGraw Hill, 1990, ISBN 0-262-03141-8, chapter 7. + * + * _Algorithms_, Second Edition, Sedgewick, Addison-Wesley, 1988, + * ISBN 0-201-06673-4, chapter 11. + */ + +#if !defined(LINT) && !defined(CODECENTER) +static char rcsid[] = "$Id: heap.c,v 8.5 1998/03/27 00:17:47 halley Exp $"; +#endif /* not lint */ + +#include "port_before.h" + +#include <stddef.h> +#include <stdlib.h> +#include <errno.h> + +#include "port_after.h" + +#include <isc/heap.h> + +/* + * Note: to make heap_parent and heap_left easy to compute, the first + * element of the heap array is not used; i.e. heap subscripts are 1-based, + * not 0-based. + */ +#define heap_parent(i) ((i) >> 1) +#define heap_left(i) ((i) << 1) + +#define ARRAY_SIZE_INCREMENT 512 + +heap_context +heap_new(heap_higher_priority_func higher_priority, heap_index_func index, + int array_size_increment) { + heap_context ctx; + + ctx = (heap_context)malloc(sizeof (struct heap_context)); + if (ctx == NULL || higher_priority == NULL) + return (NULL); + ctx->array_size = 0; + if (array_size_increment == 0) + ctx->array_size_increment = ARRAY_SIZE_INCREMENT; + else + ctx->array_size_increment = array_size_increment; + ctx->heap_size = 0; + ctx->heap = NULL; + ctx->higher_priority = higher_priority; + ctx->index = index; + return (ctx); +} + +int +heap_free(heap_context ctx) { + if (ctx == NULL) { + errno = EINVAL; + return (-1); + } + + if (ctx->heap != NULL) + free(ctx->heap); + free(ctx); + + return (0); +} + +static int +heap_resize(heap_context ctx) { + void **new_heap; + + ctx->array_size += ctx->array_size_increment; + new_heap = (void **)realloc(ctx->heap, + (ctx->array_size) * (sizeof (void *))); + if (new_heap == NULL) { + errno = ENOMEM; + return (-1); + } + ctx->heap = new_heap; + return (0); +} + +static void +float_up(heap_context ctx, int i, void *elt) { + int p; + + for ( p = heap_parent(i); + i > 1 && ctx->higher_priority(elt, ctx->heap[p]); + i = p, p = heap_parent(i) ) { + ctx->heap[i] = ctx->heap[p]; + if (ctx->index != NULL) + (ctx->index)(ctx->heap[i], i); + } + ctx->heap[i] = elt; + if (ctx->index != NULL) + (ctx->index)(ctx->heap[i], i); +} + +static void +sink_down(heap_context ctx, int i, void *elt) { + int j, size, half_size; + + size = ctx->heap_size; + half_size = size / 2; + while (i <= half_size) { + /* find smallest of the (at most) two children */ + j = heap_left(i); + if (j < size && ctx->higher_priority(ctx->heap[j+1], + ctx->heap[j])) + j++; + if (ctx->higher_priority(elt, ctx->heap[j])) + break; + ctx->heap[i] = ctx->heap[j]; + if (ctx->index != NULL) + (ctx->index)(ctx->heap[i], i); + i = j; + } + ctx->heap[i] = elt; + if (ctx->index != NULL) + (ctx->index)(ctx->heap[i], i); +} + +int +heap_insert(heap_context ctx, void *elt) { + int i; + + if (ctx == NULL || elt == NULL) { + errno = EINVAL; + return (-1); + } + + i = ++ctx->heap_size; + if (ctx->heap_size >= ctx->array_size && heap_resize(ctx) < 0) + return (-1); + + float_up(ctx, i, elt); + + return (0); +} + +int +heap_delete(heap_context ctx, int i) { + void *elt; + + if (ctx == NULL || i < 1 || i > ctx->heap_size) { + errno = EINVAL; + return (-1); + } + + elt = ctx->heap[ctx->heap_size]; + if (--ctx->heap_size > 0) + sink_down(ctx, i, elt); + + return (0); +} + +int +heap_increased(heap_context ctx, int i) { + if (ctx == NULL || i < 1 || i > ctx->heap_size) { + errno = EINVAL; + return (-1); + } + + float_up(ctx, i, ctx->heap[i]); + + return (0); +} + +int +heap_decreased(heap_context ctx, int i) { + if (ctx == NULL || i < 1 || i > ctx->heap_size) { + errno = EINVAL; + return (-1); + } + + sink_down(ctx, i, ctx->heap[i]); + + return (0); +} + +void * +heap_element(heap_context ctx, int i) { + if (ctx == NULL || i < 1 || i > ctx->heap_size) { + errno = EINVAL; + return (NULL); + } + + return (ctx->heap[i]); +} + +int +heap_for_each(heap_context ctx, heap_for_each_func action, void *uap) { + int i; + + if (ctx == NULL || action == NULL) { + errno = EINVAL; + return (-1); + } + + for (i = 1; i <= ctx->heap_size; i++) + (action)(ctx->heap[i], uap); + return (0); +} diff --git a/contrib/bind/lib/isc/heap.mdoc b/contrib/bind/lib/isc/heap.mdoc new file mode 100644 index 0000000..2c22bc2 --- /dev/null +++ b/contrib/bind/lib/isc/heap.mdoc @@ -0,0 +1,369 @@ +.\" $Id: heap.mdoc,v 8.4 1997/04/26 04:00:55 vixie Exp $ +.\" +.\"Copyright (c) 1997 by Internet Software Consortium. + * +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. + * +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.Dd Jan 1, 1997 +.\"Os OPERATING_SYSTEM [version/release] +.Os BSD 4 +.\" TODO--get correct section # below!! +.Dt HEAP @SYSCALL_EXT@ +.Sh DESCRIPTION +.Nm heap_new , +.Nm heap_free , +.Nm heap_insert , +.Nm heap_delete , +.Nm heap_increased , +.Nm heap_decreased , +.Nm heap_element , +.Nm heap_for_each +.Nd heap implementation of priority queues +.Sh SYNOPSIS +.Fd #include \&"heap.h\&" +.Ft heap_context +.Fn heap_new "heap_higher_priority_func higher_priority" \ +"heap_index_func index" "int array_size_increment" +.Ft int +.Fn heap_free "heap_context ctx" +.Ft int +.Fn heap_insert "heap_context ctx" "void *elt" +.Ft int +.Fn heap_delete "heap_context ctx" "int i" +.Ft int +.Fn heap_increased "heap_context ctx" "int i" +.Ft int +.Fn heap_decreased "heap_context ctx" "int i" +.Ft void * +.Fn heap_element "heap_context ctx" "int i" +.Ft int +.Fn heap_for_each "heap_context ctx" "heap_for_each_func action" "void *uap" +.Sh DESCRIPTION +These functions implement heap\-based priority queues. The user defines a +priority scheme, and provides a function for comparison of the priority +of heap elements +.Po see the description of the +.Ft heap_higher_priority_func +function pointer, below +.Pc . +.Pp +Each of the functions depends upon the +.Ft heap_context +type, which is a pointer to a +.Ft struct heap_context +.Pq see Pa heap.h No for more information . +.Pp +The +.Pa heap.h +header file also defines the following set of function +function pointers: +.Bd -literal -offset indent +typedef int (*heap_higher_priority_func)(void *, void *); +typedef void (*heap_index_func)(void *, int); +typedef void (*heap_for_each_func)(void *, void *); +.Ed +.Pp +These are pointers to user-defined functions. +The +.Ft heap_higher_priority_func +type is a pointer to a function which compares two +different heap (queue) elements and returns an +.Ft int +which answers the question, "Does the first queue element +have a higher priority than the second?" In other words, +a function pointer of this type +.Em must +return a number greater than zero +if the element indicated by the first argument is of a higher priority than +that indicated by the second element, and zero otherwise. +.Pp +The other two function pointers are documented in the descriptions +of +.Fn heap_new +.Pq Va heap_index_func +and +.Fn heap_for_each +.Pq Va heap_for_each_func , +below. +.Pp +The function +.Fn heap_new +initializes a +.Ft struct heap_context +and returns a pointer to it. The +.Fa higher_priority +function pointer +.Em must +be +.No non\- Ns Dv NULL . +As explained above, this refers to a +function supplied by the user which compares the priority of two different +queue or heap elements; see above for more information. +The second argument, +.Fa index , +is a pointer to a user-defined function whose arguments are +a heap element and its index in the heap. +.Fa Index +is intended to provide the user a means of knowing the internal index +of an element in the heap while maintaining the opacity of the implementation; +since the user has to know the actual indexes of heap elements in order to use, +e.g., +.Fn heap_delete +or +.Fn heap_element , +the user +.Fa index +function could store the index in the heap element, itself. If +.Fa index +is +.No non\- Ns Dv NULL , +then it is called +.Em whenever +the index of an element changes, allowing the user to stay up\-to\-date +with index changes. +The last argument, +.Fa array_size_increment +will be used, as its name suggests, by +.Xr malloc 3 +or +.Xr realloc 3 +to increment the array which implements the heap; if zero, a default value +will be used. +.Pp +The +.Fn heap_free +function frees the given +.Ft heap_context +argument +.Pq Fa ctx , +which also frees the entire +.Nm heap , +if it is +.No non\- Ns Dv NULL . +The argument +.Fa ctx +should be +.No non\- Ns Dv NULL . +.Pp +The +.Fn heap_insert +function is used to insert the new heap element +.Fa elt +into the appropriate place (priority\-wise) in the +.Ft heap +indicated by +.Fa ctx +.Po a pointer to a +.Ft heap_context +.Pc . +If +.No non\- Ns Dv NULL , +the user-defined +.Ft higher_priority +function pointer associated with the indicated +.Nm heap +is used to determine that +.Dq appropriate place ; +the highest\-priority elements are at the front of the queue (top of +the heap). +(See the description of +.Fn heap_new , +above, for more information.) +.Pp +The function +.Fn heap_delete +is used to delete the +.Fa i\- Ns th +element of the queue (heap), and fixing up the queue (heap) from that +element onward via the priority as determined by the user function +pointed to by +.Ft higher_priority +function pointer +.Pq see description of Fn heap_new, No above . +.Pp +.Fn heap_increased +.Pp +.Fn heap_decreased +.Pp +The +.Fn heap_element +function returns the +.Fa i\- Ns th +element of the queue/heap indicated by +.Fa ctx , +if possible. +.Pp +The +.Fn heap_for_each +function provides a mechanism for the user to increment through the entire +queue (heap) and perform some +.Fa action +upon each of the queue elements. This +.Fa action +is pointer to a user\-defined function with two arguments, the first of +which should be interpreted by the user's function as a heap element. The +second value passed to the user function is just the +.Fa uap +argument to +.Fn heap_for_each ; +this allows the user to specify additional arguments, if necessary, to +the function pointed to by +.Fa action . +.\" The following requests should be uncommented and +.\" used where appropriate. This next request is +.\" for sections 2 and 3 function return values only. +.Sh RETURN VALUES +.Bl -tag -width "heap_decreased()" +.It Fn heap_new +.Dv NULL +if unable to +.Xr malloc 3 +a +.Ft struct heap_context +or if the +.Fa higher_priority +function pointer is +.Dv NULL; +otherwise, a valid +.Ft heap_context +.Ns . +.It Fn heap_free +-1 if +.Fa ctx +is +.Dv NULL +(with +.Va errno +set to +.Dv EINVAL ) ; +otherwise, 0. +.It Fn heap_insert +-1 +if either +.Fa ctx +or +.Fa elt +is +.Dv NULL , +or if an attempt to +.Xr malloc 3 +or +.Xr realloc 3 +the heap array fails (with +.Va errno +set to +.Dv EINVAL +or +.Dv ENOMEM , +respectively). +Otherwise, 0. +.It Fn heap_delete +-1 if +.Fa ctx +is +.Dv NULL +or +.Fa i +is out\-of\-range (with +.Va errno +set to +.Dv EINVAL ) ; +0 otherwise. +.It Fn heap_increased +As for +.Fn heap_delete . +.It Fn heap_decreased +As for +.Fn heap_delete . +.It Fn heap_element +NULL if +.Fa ctx +is +.Dv NULL +or +.Fa i +out\-of-bounds (with +.Va errno +set to +.Dv EINVAL ) ; +otherwise, a pointer to the +.Fa i\- Ns th +queue element. +.It Fn heap_for_each +-1 if either +.Fa ctx +or +.Fa action +is +.Dv NULL +(with +.Va errno +set to +.Dv EINVAL ) ; +0 otherwise. +.El +.\" This next request is for sections 1, 6, 7 & 8 only +.\" .Sh ENVIRONMENT +.Sh FILES +.Bl -tag -width "heap.h000" +.It Pa heap.h + heap library header file +.El +.\" .Sh EXAMPLES +.\" This next request is for sections 1, 6, 7 & 8 only +.\" (command return values (to shell) and +.\" fprintf/stderr type diagnostics) +.Sh DIAGNOSTICS +Please refer to +.Sx RETURN VALUES . +.\" The next request is for sections 2 and 3 error +.\" and signal handling only. +.Sh ERRORS +The variable +.Va errno +is set by +.Fn heap_free , +.Fn heap_insert , +.Fn heap_delete , +.Fn heap_increased , +and +.Fn heap_decreased +under the conditions of invalid input +.Pq Dv EINVAL +or lack of memory +.Pq Dv ENOMEM ; +please refer to +.Sx RETURN VALUES . +.Sh SEE ALSO +.Xr malloc 3 , +.Xr realloc 3 . +.Pp +Cormen, Leiserson, and Rivest, +.Sy Introduction to Algorithms, +MIT Press / McGraw Hill, 1990, ISBN 0\-262\-03141\-8, chapter 7. +.Pp +Sedgewick, +.Sy Algorithms, +2nd ed'n, Addison\-Wesley, 1988, ISBN 0\-201\-06673\-4, chapter 11. +.\" .Sh STANDARDS +.\" .Sh HISTORY +.Sh AUTHORS +The +.Nm heap +library was implemented by Bob Halley (halley@vix.com) of Vixie Enterprises, +Inc., for the Internet Software consortium, and was adapted from +the two books listed in the +.Sx SEE ALSO +section, above. +.\" .Sh BUGS diff --git a/contrib/bind/lib/isc/logging.c b/contrib/bind/lib/isc/logging.c new file mode 100644 index 0000000..e5264ff --- /dev/null +++ b/contrib/bind/lib/isc/logging.c @@ -0,0 +1,674 @@ +/* + * Copyright (c) 1996, 1997, 1998 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +#if !defined(LINT) && !defined(CODECENTER) +static char rcsid[] = "$Id: logging.c,v 8.18 1998/03/27 00:17:47 halley Exp $"; +#endif /* not lint */ + +#include "port_before.h" + +#include <sys/types.h> +#include <sys/time.h> +#include <sys/stat.h> + +#include <fcntl.h> +#include <limits.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <stdarg.h> +#include <syslog.h> +#include <errno.h> +#include <time.h> +#include <unistd.h> + +#include <isc/assertions.h> +#include <isc/logging.h> +#include <isc/memcluster.h> + +#include "port_after.h" + +#ifdef VSPRINTF_CHAR +# define VSPRINTF(x) strlen(vsprintf/**/x) +#else +# define VSPRINTF(x) ((size_t)vsprintf x) +#endif + +#include "logging_p.h" + +static const int syslog_priority[] = { LOG_DEBUG, LOG_INFO, LOG_NOTICE, + LOG_WARNING, LOG_ERR, LOG_CRIT }; + +static const char *months[] = { "Jan", "Feb", "Mar", "Apr", "May", "Jun", + "Jul", "Aug", "Sep", "Oct", "Nov", "Dec" }; + +static char *level_text[] = { "info: ", "notice: ", "warning: ", "error: ", + "critical: " }; + +static void +version_rename(log_channel chan) { + unsigned int ver; + char old_name[PATH_MAX+1]; + char new_name[PATH_MAX+1]; + + ver = chan->out.file.versions; + if (ver < 1) + return; + if (ver > LOG_MAX_VERSIONS) + ver = LOG_MAX_VERSIONS; + /* + * Need to have room for '.nn' (XXX assumes LOG_MAX_VERSIONS < 100) + */ + if (strlen(chan->out.file.name) > (PATH_MAX-3)) + return; + for (ver--; ver > 0; ver--) { + sprintf(old_name, "%s.%d", chan->out.file.name, ver-1); + sprintf(new_name, "%s.%d", chan->out.file.name, ver); + (void)rename(old_name, new_name); + } + sprintf(new_name, "%s.0", chan->out.file.name); + (void)rename(chan->out.file.name, new_name); +} + +FILE * +log_open_stream(log_channel chan) { + FILE *stream; + int fd, flags; + struct stat sb; + int regular; + + if (chan == NULL || chan->type != log_file) { + errno = EINVAL; + return (NULL); + } + + /* + * Don't open already open streams + */ + if (chan->out.file.stream != NULL) + return (chan->out.file.stream); + + if (stat(chan->out.file.name, &sb) < 0) { + if (errno != ENOENT) { + syslog(LOG_ERR, + "log_open_stream: stat of %s failed: %s", + chan->out.file.name, strerror(errno)); + chan->flags |= LOG_CHANNEL_BROKEN; + return (NULL); + } + regular = 1; + } else + regular = (sb.st_mode & S_IFREG); + + if (chan->out.file.versions) { + if (regular) + version_rename(chan); + else { + syslog(LOG_ERR, + "log_open_stream: want versions but %s isn't a regular file", + chan->out.file.name); + chan->flags |= LOG_CHANNEL_BROKEN; + errno = EINVAL; + return (NULL); + } + } + + flags = O_WRONLY|O_CREAT|O_APPEND; + + if (chan->flags & LOG_TRUNCATE) { + if (regular) { + (void)unlink(chan->out.file.name); + flags |= O_EXCL; + } else { + syslog(LOG_ERR, + "log_open_stream: want truncation but %s isn't a regular file", + chan->out.file.name); + chan->flags |= LOG_CHANNEL_BROKEN; + errno = EINVAL; + return (NULL); + } + } + + fd = open(chan->out.file.name, flags, + S_IRUSR|S_IWUSR|S_IRGRP|S_IWGRP|S_IROTH|S_IWOTH); + if (fd < 0) { + syslog(LOG_ERR, "log_open_stream: open(%s) failed: %s", + chan->out.file.name, strerror(errno)); + chan->flags |= LOG_CHANNEL_BROKEN; + return (NULL); + } + stream = fdopen(fd, "a"); + if (stream == NULL) { + syslog(LOG_ERR, "log_open_stream: fdopen() failed"); + chan->flags |= LOG_CHANNEL_BROKEN; + return (NULL); + } + + chan->out.file.stream = stream; + return (stream); +} + +int +log_close_stream(log_channel chan) { + FILE *stream; + + if (chan == NULL || chan->type != log_file) { + errno = EINVAL; + return (0); + } + stream = chan->out.file.stream; + chan->out.file.stream = NULL; + if (stream != NULL && fclose(stream) == EOF) + return (-1); + return (0); +} + +FILE * +log_get_stream(log_channel chan) { + if (chan == NULL || chan->type != log_file) { + errno = EINVAL; + return (NULL); + } + return (chan->out.file.stream); +} + +char * +log_get_filename(log_channel chan) { + if (chan == NULL || chan->type != log_file) { + errno = EINVAL; + return (NULL); + } + return (chan->out.file.name); +} + +int +log_check_channel(log_context lc, int level, log_channel chan) { + int debugging, chan_level; + + REQUIRE(lc != NULL); + + debugging = ((lc->flags & LOG_OPTION_DEBUG) != 0); + + /* + * If not debugging, short circuit debugging messages very early. + */ + if (level > 0 && !debugging) + return (0); + + if ((chan->flags & (LOG_CHANNEL_BROKEN|LOG_CHANNEL_OFF)) != 0) + return (0); + + /* Some channels only log when debugging is on. */ + if ((chan->flags & LOG_REQUIRE_DEBUG) && !debugging) + return (0); + + /* Some channels use the global level. */ + if ((chan->flags & LOG_USE_CONTEXT_LEVEL) != 0) { + chan_level = lc->level; + } else + chan_level = chan->level; + + if (level > chan_level) + return (0); + + return (1); +} + +int +log_check(log_context lc, int category, int level) { + log_channel_list lcl; + int debugging; + + REQUIRE(lc != NULL); + + debugging = ((lc->flags & LOG_OPTION_DEBUG) != 0); + + /* + * If not debugging, short circuit debugging messages very early. + */ + if (level > 0 && !debugging) + return (0); + + if (category < 0 || category > lc->num_categories) + category = 0; /* use default */ + lcl = lc->categories[category]; + if (lcl == NULL) { + category = 0; + lcl = lc->categories[0]; + } + + for ( /* nothing */; lcl != NULL; lcl = lcl->next) { + if (log_check_channel(lc, level, lcl->channel)) + return (1); + } + return (0); +} + +void +log_vwrite(log_context lc, int category, int level, const char *format, + va_list args) { + log_channel_list lcl; + int pri, debugging, did_vsprintf = 0; + int original_category; + FILE *stream; + int chan_level; + log_channel chan; + struct timeval tv; + struct tm *local_tm; + char *category_name; + char *level_str; + char time_buf[256]; + char level_buf[256]; + + REQUIRE(lc != NULL); + + debugging = (lc->flags & LOG_OPTION_DEBUG); + + /* + * If not debugging, short circuit debugging messages very early. + */ + if (level > 0 && !debugging) + return; + + if (category < 0 || category > lc->num_categories) + category = 0; /* use default */ + original_category = category; + lcl = lc->categories[category]; + if (lcl == NULL) { + category = 0; + lcl = lc->categories[0]; + } + + /* + * Get the current time and format it. + */ + time_buf[0]='\0'; + if (gettimeofday(&tv, NULL) < 0) { + syslog(LOG_INFO, "gettimeofday failed in log_vwrite()"); + } else { + local_tm = localtime((time_t *)&tv.tv_sec); + if (local_tm != NULL) { + sprintf(time_buf, "%02d-%s-%4d %02d:%02d:%02d.%03ld ", + local_tm->tm_mday, months[local_tm->tm_mon], + local_tm->tm_year+1900, local_tm->tm_hour, + local_tm->tm_min, local_tm->tm_sec, + (long)tv.tv_usec/1000); + } + } + + /* + * Make a string representation of the current category and level + */ + + if (lc->category_names != NULL && + lc->category_names[original_category] != NULL) + category_name = lc->category_names[original_category]; + else + category_name = ""; + + if (level >= log_critical) { + if (level >= 0) { + sprintf(level_buf, "debug %d: ", level); + level_str = level_buf; + } else + level_str = level_text[-level-1]; + } else { + sprintf(level_buf, "level %d: ", level); + level_str = level_buf; + } + + /* + * Write the message to channels. + */ + for ( /* nothing */; lcl != NULL; lcl = lcl->next) { + chan = lcl->channel; + + if (!log_check_channel(lc, level, chan)) + continue; + + if (!did_vsprintf) { + if (VSPRINTF((lc->buffer, format, args)) > + LOG_BUFFER_SIZE) { + syslog(LOG_CRIT, + "memory overrun in log_vwrite()"); + exit(1); + } + did_vsprintf = 1; + } + + switch (chan->type) { + case log_syslog: + if (level >= log_critical) + pri = (level >= 0) ? 0 : -level; + else + pri = -log_critical; + syslog(chan->out.facility|syslog_priority[pri], + "%s%s%s%s", + (chan->flags & LOG_TIMESTAMP) ? time_buf : "", + (chan->flags & LOG_PRINT_CATEGORY) ? + category_name : "", + (chan->flags & LOG_PRINT_LEVEL) ? + level_str : "", + lc->buffer); + break; + case log_file: + stream = chan->out.file.stream; + if (stream == NULL) { + stream = log_open_stream(chan); + if (stream == NULL) + break; + } + if (chan->out.file.max_size != ULONG_MAX) { + long pos; + + pos = ftell(stream); + if (pos >= 0 && + (unsigned long)pos > + chan->out.file.max_size) + break; + } + fprintf(stream, "%s%s%s%s\n", + (chan->flags & LOG_TIMESTAMP) ? time_buf : "", + (chan->flags & LOG_PRINT_CATEGORY) ? + category_name : "", + (chan->flags & LOG_PRINT_LEVEL) ? + level_str : "", + lc->buffer); + fflush(stream); + break; + case log_null: + break; + default: + syslog(LOG_ERR, + "unknown channel type in log_vwrite()"); + } + } +} + +void +log_write(log_context lc, int category, int level, const char *format, ...) { + va_list args; + + va_start(args, format); + log_vwrite(lc, category, level, format, args); + va_end(args); +} + +/* + * Functions to create, set, or destroy contexts + */ + +int +log_new_context(int num_categories, char **category_names, log_context *lc) { + log_context nlc; + + nlc = memget(sizeof (struct log_context)); + if (nlc == NULL) { + errno = ENOMEM; + return (-1); + } + nlc->num_categories = num_categories; + nlc->category_names = category_names; + nlc->categories = memget(num_categories * sizeof (log_channel_list)); + if (nlc->categories == NULL) { + memput(nlc, sizeof (struct log_context)); + errno = ENOMEM; + return (-1); + } + memset(nlc->categories, '\0', + num_categories * sizeof (log_channel_list)); + nlc->flags = 0U; + nlc->level = 0; + *lc = nlc; + return (0); +} + +void +log_free_context(log_context lc) { + log_channel_list lcl, lcl_next; + log_channel chan; + int i; + + REQUIRE(lc != NULL); + + for (i = 0; i < lc->num_categories; i++) + for (lcl = lc->categories[i]; lcl != NULL; lcl = lcl_next) { + lcl_next = lcl->next; + chan = lcl->channel; + (void)log_free_channel(chan); + memput(lcl, sizeof (struct log_channel_list)); + } + memput(lc->categories, + lc->num_categories * sizeof (log_channel_list)); + memput(lc, sizeof (struct log_context)); +} + +int +log_add_channel(log_context lc, int category, log_channel chan) { + log_channel_list lcl; + + if (lc == NULL || category < 0 || category >= lc->num_categories) { + errno = EINVAL; + return (-1); + } + + lcl = memget(sizeof (struct log_channel_list)); + if (lcl == NULL) { + errno = ENOMEM; + return(-1); + } + lcl->channel = chan; + lcl->next = lc->categories[category]; + lc->categories[category] = lcl; + chan->references++; + return (0); +} + +int +log_remove_channel(log_context lc, int category, log_channel chan) { + log_channel_list lcl, prev_lcl, next_lcl; + int found = 0; + + if (lc == NULL || category < 0 || category >= lc->num_categories) { + errno = EINVAL; + return (-1); + } + + for (prev_lcl = NULL, lcl = lc->categories[category]; + lcl != NULL; + lcl = next_lcl) { + next_lcl = lcl->next; + if (lcl->channel == chan) { + log_free_channel(chan); + if (prev_lcl != NULL) + prev_lcl->next = next_lcl; + else + lc->categories[category] = next_lcl; + memput(lcl, sizeof (struct log_channel_list)); + /* + * We just set found instead of returning because + * the channel might be on the list more than once. + */ + found = 1; + } else + prev_lcl = lcl; + } + if (!found) { + errno = ENOENT; + return (-1); + } + return (0); +} + +int +log_option(log_context lc, int option, int value) { + if (lc == NULL) { + errno = EINVAL; + return (-1); + } + switch (option) { + case LOG_OPTION_DEBUG: + if (value) + lc->flags |= option; + else + lc->flags &= ~option; + break; + case LOG_OPTION_LEVEL: + lc->level = value; + break; + default: + errno = EINVAL; + return (-1); + } + return (0); +} + +int +log_category_is_active(log_context lc, int category) { + if (lc == NULL) { + errno = EINVAL; + return (-1); + } + if (category >= 0 && category < lc->num_categories && + lc->categories[category] != NULL) + return (1); + return (0); +} + +log_channel +log_new_syslog_channel(unsigned int flags, int level, int facility) { + log_channel chan; + + chan = memget(sizeof (struct log_channel)); + if (chan == NULL) { + errno = ENOMEM; + return (NULL); + } + chan->type = log_syslog; + chan->flags = flags; + chan->level = level; + chan->out.facility = facility; + chan->references = 0; + return (chan); +} + +log_channel +log_new_file_channel(unsigned int flags, int level, + char *name, FILE *stream, unsigned int versions, + unsigned long max_size) { + log_channel chan; + + chan = memget(sizeof (struct log_channel)); + if (chan == NULL) { + errno = ENOMEM; + return (NULL); + } + chan->type = log_file; + chan->flags = flags; + chan->level = level; + if (name != NULL) { + size_t len; + + len = strlen(name); + /* + * Quantize length to a multiple of 256. There's space for the + * NUL, since if len is a multiple of 256, the size chosen will + * be the next multiple. + */ + chan->out.file.name_size = ((len / 256) + 1) * 256; + chan->out.file.name = memget(chan->out.file.name_size); + if (chan->out.file.name == NULL) { + memput(chan, sizeof (struct log_channel)); + errno = ENOMEM; + return (NULL); + } + /* This is safe. */ + strcpy(chan->out.file.name, name); + } else { + chan->out.file.name_size = 0; + chan->out.file.name = NULL; + } + chan->out.file.stream = stream; + chan->out.file.versions = versions; + chan->out.file.max_size = max_size; + chan->references = 0; + return (chan); +} + +log_channel +log_new_null_channel() { + log_channel chan; + + chan = memget(sizeof (struct log_channel)); + if (chan == NULL) { + errno = ENOMEM; + return (NULL); + } + chan->type = log_null; + chan->flags = LOG_CHANNEL_OFF; + chan->level = log_info; + chan->references = 0; + return (chan); +} + +int +log_inc_references(log_channel chan) { + if (chan == NULL) { + errno = EINVAL; + return (-1); + } + chan->references++; + return (0); +} + +int +log_dec_references(log_channel chan) { + if (chan == NULL || chan->references <= 0) { + errno = EINVAL; + return (-1); + } + chan->references--; + return (0); +} + +log_channel_type +log_get_channel_type(log_channel chan) { + REQUIRE(chan != NULL); + + return (chan->type); +} + +int +log_free_channel(log_channel chan) { + if (chan == NULL || chan->references <= 0) { + errno = EINVAL; + return (-1); + } + chan->references--; + if (chan->references == 0) { + if (chan->type == log_file) { + if ((chan->flags & LOG_CLOSE_STREAM) && + chan->out.file.stream != NULL) + (void)fclose(chan->out.file.stream); + if (chan->out.file.name != NULL) + memput(chan->out.file.name, + chan->out.file.name_size); + } + memput(chan, sizeof (struct log_channel)); + } + return (0); +} diff --git a/contrib/bind/lib/isc/logging.mdoc b/contrib/bind/lib/isc/logging.mdoc new file mode 100644 index 0000000..6fdb618 --- /dev/null +++ b/contrib/bind/lib/isc/logging.mdoc @@ -0,0 +1,1044 @@ +.\" $Id: logging.mdoc,v 8.2 1998/02/06 01:54:34 halley Exp $ +.\" +.\"Copyright (c) 1995, 1996, 1997, 1998 by Internet Software Consortium +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.\" The following six UNCOMMENTED lines are required. +.Dd January 1, 1996 +.\"Os OPERATING_SYSTEM [version/release] +.Os BSD 4 +.\"Dt DOCUMENT_TITLE [section number] [volume] +.Dt LOGGING @SYSCALL_EXT@ +.Sh NAME +.Nm log_open_stream , +.Nm log_close_stream , +.Nm log_get_stream , +.Nm log_get_filename , +.Nm log_vwrite , +.Nm log_write , +.Nm log_new_context , +.Nm log_free_context , +.Nm log_add_channel , +.Nm log_remove_channel , +.Nm log_option , +.Nm log_category_is_active , +.Nm log_new_syslog_channel , +.Nm log_new_file_channel , +.Nm log_new_null_channel , +.Nm log_inc_references , +.Nm log_dec_references , +.Nm log_free_channel +.Nd logging system +.Sh SYNOPSIS +.Fd #include <isc/logging.h> +.Ft FILE * +.Fn log_open_stream "log_channel chan" +.Ft int +.Fn log_close_stream "log_channel chan" +.Ft FILE * +.Fn log_get_stream "log_channel chan" +.Ft char * +.Fn log_get_filename "log_channel chan" +.Ft void +.Fn log_vwrite "log_context lc" "int category" "int level" \ + "const char *format" va_list args" +.Ft void +.Fn log_write "log_context lc" "int category" "int level" \ + "const char *format" "..." +.Ft int +.Fn log_check_channel "log_context lc" "int level" "log_channel chan" +.Ft int +.Fn log_check "log_context lc" "int category" "int level" +.Ft int +.Fn log_new_context "int num_categories" "char **category_names" \ + "log_context *lc" +.Ft void +.Fn log_free_context "log_context lc" +.Ft int +.Fn log_add_channel "log_context lc" "int category" "log_channel chan" +.Ft int +.Fn log_remove_channel "log_context lc" "int category" "log_channel chan" +.Ft int +.Fn log_option "log_context lc" "int option" "int value" +.Ft int +.Fn log_category_is_active "log_context lc" "int category" +.Ft log_channel +.Fn log_new_syslog_channel "unsigned int flags" "int level" "int facility" +.Ft log_channel +.Fn log_new_file_channel "unsigned int flags" "int level" \ + "char *name" "FILE *stream" "unsigned int versions" \ + "unsigned long max_size" +.Ft log_channel +.Fn log_new_null_channel "void" +.Ft int +.Fn log_inc_references "log_channel chan" +.Ft int +.Fn log_dec_references "log_channel chan" +.Ft int +.Fn log_free_channel "log_channel chan" +.Sh DESCRIPTION +The +.Sy ISC +.Nm logging library +is flexible logging system which is based upon a set of concepts: +.Nm logging channels , +.Nm categories , +and +.Nm logging contexts . +.Pp +The basic building block is the +.Dq Nm logging channel , +which includes a +.Nm priority +(logging level), which type of logging is to occur, and other +flags and information associated with technical aspects of the logging. +The set of priorities which are supported is shown below, in the section +.Sx Message Priorities . +A priority sets a threshold for message logging; a logging channel will +.Em only +log those messages which are +.Em at least as important +as its priority indicates. (The fact that +.Dq more important +means +.Dq more negative , +under the current scheme, is an implementation detail; if a channel has +a priority of +.Dv log_error , +then it will +.Em not +log messages with the +.Dv log_warning +priority, but it +.Em will +log messages with the +.Dv log_error +or +.Dv log_critical +priority.) +.Pp +The +.Nm logging channel +also has an indication of the type of logging performed. Currently, +the supported +.Nm logging types +include (see also +.Sx Logging Types , +below): +.Bl -tag -width "log_syslog" -compact -offset indent +.It Dv log_syslog +for +.Xr syslog 3 Ns -style +logging +.It Dv log_file +for use of a file +.It Dv log_null +for +.Em no +logging +.El +A new logging channel is created by calling either +.Fn log_new_syslog_channel , +.Fn log_new_file_channel , +or +.Fn log_new_null_channel , +respectively. +When a channel is no longer to be used, it can be freed using +.Fn log_free_channel . +.Pp +Both +.Dv log_syslog +and +.Dv log_file +channel types can include more information; for instance, a +.Dv log_syslog Ns -type +channel allows the specification of a +.Xr syslog 3 Ns -style +.Dq facility , +and a +.Dv log_file Ns -type +channels allows the caller to set a maximum file size and number +of versions. (See +.Fn log_new_syslog_channel +or +.Fn log_new_file_channel , +below.) +Additionally, once a logging channel of type +.Dv log_file +is defined, the functions +.Fn log_open_stream +and +.Fn log_close_stream +can open or close the stream associated with the logging channel's logging +filename. The +.Fn log_get_stream +and +.Fn log_get_filename +functions return the stream or filename, respectively, of such a logging +channel. +.Pp +Callers provide +.Dq Nm categories , +determining both the number of such categories and any (optional) names. +Categories are like array indexes in C; if the caller declares +.Dq Va n +categories, then they are considered to run from 0 to +.Va n-1 ; +with this scheme, a category number would be invalid if it were negative or +greater than/equal to +.Va n . +Each category can have its own list of +.Nm logging channels +associated with it; we say that such a channel is +.Dq in +the particular category. +.Sy NOTE: +Individual logging channels can appear in more than one category. +.Pp +A +.Dq Nm logging context +is the set of all +.Nm logging channels +associated with the context's +.Nm categories; +thus, a particular +.Nm category +scheme is associated with a particular +.Nm logging context. +.Sy NOTE: +A logging channel may appear in more than one logging context, and in +multiple categories within each logging context. +.Pp +Use +.Fn log_add_channel +and +.Fn log_remove_channel +to add or remove a logging channel to some category in a logging context. +To see if a given category in a logging context is being used, use the +Boolean test +.Fn log_category_is_active . +.Pp +A +.Nm logging context +can also have a +.Nm priority +(logging level) +and various flags associated with the whole context; in order to alter the +flags or change the priority of a context, use +.Fn log_option . +.Ss Message Priorities +Currently, five +.Nm priorities +(logging levels) are supported (they can also be found in the header file): +.Bd -literal -offset indent +#define log_critical (-5) +#define log_error (-4) +#define log_warning (-3) +#define log_notice (-2) +#define log_info (-1) +.Ed +.Pp +In the current implementation, logging messages which have a level greater +than 0 are considered to be debugging messages. +.Ss Logging Types +The three different +.Nm logging types +currently supported are different values of the enumerated type +.Ft log_output_type +(these are also listed in the header file): +.Bd -literal -offset indent +typedef enum { log_syslog, log_file, log_null } log_output_type; +.Ed +.Ss Logging Channel Flags +There are several flags which can be set on a logging channel; the flags +and their meanings are as follows (they are also found in the header file): +.Bl -tag -width "LOG_USE_CONTEXT_LEVEL " -offset indent +.It Dv LOG_CHANNEL_BROKEN +This is set only when some portion of +.Fn log_open_stream +fails: +.Xr open 2 +or +.Xr fdopen 3 +fail; +.Xr stat 2 +fails in a +.Dq bad +way; versioning or truncation is requested on a non-normal file. +.It Dv LOG_CHANNEL_OFF +This is set for channels opened by +.Fn log_new_null_channel . +.It Dv LOG_CLOSE_STREAM +If this flag is set, then +.Fn log_free_channel +will free a +.No non- Dv NULL +stream of a logging channel which is being +.Xr free 3 Ns -d +(if the logging channel is of type +.Dv log_file , +of course). +.It Dv LOG_PRINT_CATEGORY +If set, +.Fn log_vwrite +will insert the category name, if available, into logging messages which are +logged to channels of type +.Dv log_syslog +or +.Dv log_file . +.It Dv LOG_PRINT_LEVEL +If set, +.Fn log_vwrite +will insert a string identifying the message priority level into the +information logged to channels of type +.Dv log_syslog +or +.Dv log_file . +.It Dv LOG_REQUIRE_DEBUG +Only log debugging messages (i.e., those with a priority greater than zero). +.It Dv LOG_TIMESTAMP +If set, +.Fn log_vwrite +will insert a timestamp into logging messages which are logged to channels of +type +.Dv log_syslog +or +.Dv log_file . +.It Dv LOG_TRUNCATE +Truncate logging file when re-opened ( +.Fn log_open_stream +will +.Xr unlink 2 +the file and then +.Xr open 2 +a new file of the same name with the +.Dv O_EXCL +bit set). +.It Dv LOG_USE_CONTEXT_LEVEL +Use the logging context's priority or logging level, rather than the logging +channel's own priority. This can be useful for those channels which are +included in multiple logging contexts. +.El +.Ss FUNCTION DESCRIPTIONS +The function +.Fn log_open_stream +is for use with channels which log to a file; i.e., logging channels with a +.Va type +field set to +.Dq Dv log_file . +If the logging channel pointed to by +.Dq Fa chan +is valid, it attempts to open (and return) the stream associated with that +channel. If the stream is already opened, then it is returned; otherwise, +.Xr stat 2 +is used to test the filename for the stream. +.Pp +At this point, if the logging file is supposed to have different +.Va versions +(i.e., incremented version numbers; higher numbers indicate older versions +of the logging file). If so, then any existing versions are +.Xr rename 2 Ns -d +to have one version-number higher than previously, and the +.Dq current +filename for the stream is set to the +.Dq \&.0 +form of the name. Next, if the logging file is supposed to be truncated +(i.e., the +.Dv LOG_TRUNCATE +bit of the +.Va flags +field of the logging channel structure is set), then any file with the +.Dq current +filename for the stream is +.X4 unlink 2 Ns -d . +.Sy NOTE: +If the logging file is +.Em not +a regular file, and either of the above operations (version numbering +or truncation) is supposed to take place, a +.Dv NULL +file pointer is returned. +.Pp +Finally, the filename associated with the logging channel is +.Xr open 2 Ns -d +using the appropriate flags and a mode which sets the read/write permissions +for the user, group, and others. The file descriptor returned by +.Xr open 2 +is then passed to +.Xr fopen 3 , +with the append mode set, and the stream returned by this call is stored +in the +.Fa chan +structure and returned. +.Pp +If +.Fn log_open_stream +fails at any point, then the +.Dv LOG_CHANNEL_BROKEN +bit of the +.Va flags +field of the logging channel pointed to by +.Fa chan +is set, a +.Dv NULL +is returned, and +.Va errno +contains pertinent information. +.Pp +The +.Fn log_close_stream +function closes the stream associated with the logging channel pointed to by +.Dq Fa chan +(if +.Fa chan +is valid and the stream exists and can be closed properly by +.Xr fclose 3 ) . +The stream is set to +.Dv NULL +even if the call to +.Xr fclose 3 +fails. +.Pp +The function +.Fn log_get_stream +returns the stream associated with the logging channel pointed to by +.Dq Fa chan , +if it is +.No non- Ns Dv NULL +and specifies a logging channel which has a +.Dv FILE * +or stream associated with it. +.Pp +The +.Fn log_get_filename +function returns the name of the file associated with the logging channel +pointed to by +.Dq Fa chan , +if it is +.No non- Ns Dv NULL +and specifies a logging channel which has a file associated with it. +.Pp +The +.Fn log_vwrite +function performs the actual logging of a message to the various logging +channels of a logging context +.Fa lc . +The message consists of an +.Xr fprint 3 Ns -style +.Fa format +and its associated +.Fa args +(if any); it will be written to all logging channels in the given +.Fa category +which have a priority set to +.Fa level +or any +.Em less important +priority value. If the +.Fa category +is not valid or has no logging channels, then the category defaults to 0. +.Pp +There are a number of conditions under which a call to +.Fn log_vwrite +will not result in actually logging the message: if there is no logging channel +at even the default category (0), or if a given channel is either +.Dq broken +or +.Dq off +(i.e., its flags have +.Dv LOG_CHANNEL_BROKEN +or +.Dv LOG_CHANNEL_OFF +set, respectively), or if the logging channel channel is of type +.Dv log_null . +Additionally, if the logging channel's flag has +.Dv LOG_REQUIRE_DEBUG +set and the message is not a debugging message (i.e., has a level greater +than 0), then it will not be logged. +Finally, if the message's priority is less important than the +channel's logging level (the priority threshold), will not be logged. +.Sy NOTE: +If a logging channel's flag has +.Dv LOG_USE_CONTEXT_LEVEL +set, it will use the logging context's priority, rather than its own. +.Pp +If all of these hurdles are passed, then only +.Dv log_syslog +and +.Dv log_file +channels actually can have logging. For channels which use +.Xr syslog 3 , +the channel's +.Xr syslog 3 +facility is used in conjunction with a potentially modified form of the +message's priority level, since +.Xr syslog 3 +has its own system of priorities +.Pq Pa /usr/include/syslog.h . +All debug messages (priority >= 0) are mapped to +.Xr syslog 3 Ns 's +.Dv LOG_DEBUG +priority, all messages +.Dq more important +than +.Dv log_critical +are mapped to +.Dv LOG_CRIT , +and the priorities corresponding to the ones listed in the section +.Sx Message Priorities +are given the obvious corresponding +.Xr syslog 3 +priority. +.Pp +For +.Dv log_file +type logging channels, if the file size is greater than the maximum file +size, then no logging occurs. (The same thing happens if a +.Dv NULL +stream is encountered and +.Fn log_open_stream +fails to open the channel's stream.) +.Pp +For both logging to normal files and logging via +.Xr syslog 3 , +the value of the flags +.Dv LOG_TIMESTAMP , +.Dv LOG_PRINT_CATEGORY , +and +.Dv LOG_PRINT_LEVEL +are used in determining whether or not these items are included in the logged +information. +.Pp +The +.Fn log_write +function is merely a front-end to a call to +.Fn log_vwrite ; +see the description of that function, above, for more information. +.Pp +.Fn log_check +and +.Fn log_check_channel +are used to see if a contemplated logging call will actually generate any +output, which is useful when creating a log message involves non-trivial +work. +.Fn log_check +will return non-zero if a call to +.Fn log_vwrite +with the given +.Fa category +and +.Fa level +would generate output on any channels, and zero otherwise. +.Fn log_check_channel +will return non-zero if writing to the +.Fa chan +at the given +.Fa level +would generate output. +.Pp +The function +.Fn log_new_context +creates a new +.Nm logging context , +and stores this in the +.Dq Va opaque +field of the argument +.Dq Fa lc , +and opaque structure used internally. This new +.Nm context +will include the +.Dq Fa num_categories +and +.Dq Fa category_names +which are supplied; the latter can be +.Dv NULL . +.Sy NOTE: +Since +.Dq Fa category_names +is used directly, it +.Em must not +be freed by the caller, if it is +.No non- Ns Dv NULL . +The initial logging flags and priority are both set to zero. +.Pp +The +.Fn log_free_context +function is used to free the opaque structure +.Dq Va lc.opaque +and its components. +.Sy NOTE: +The +.Dq Va opaque +field of +.Dq Fa lc +.Em must +be +.No non- Ns Dv NULL . +For each of the various +.Dq categories +(indicated by the +.Dq Va num_categories +which were in the corresponding call to +.Fn log_new_context ) +associated with the given +.Nm logging context , +.Em all +of the +.Nm logging channels +are +.Xr free 3 Ns -d . +The opaque structure itself is then +.Xr free 3 Ns -d , +and +.Dq Va lc.opaque +is set to +.Dv NULL . +.Pp +.Sy NOTE: +The function +.Fn log_free_context +does +.Em not +free the memory associated with +.Fa category_names , +since the logging library did not allocate the memory for it, originally; +it was supplied in the call to +.Fn log_new_context . +.Pp +The function +.Fn log_add_channel +adds the +.Nm logging channel +.Dq Fa chan +to the list of logging channels in the given +.Fa category +of the +.Nm logging context +.Dq Fa lc . +No checking is performed to see whether or not +.Fa chan +is already present in the given +.Fa category , +so multiple instances in a single +.Fa category +can occur (but see +.Fn log_remove_channel , +below). +.Pp +The +.Fn log_remove_channel +function +removes +.Em all +occurrences of the +.Nm logging channel +.Dq Fa chan +from the list of logging channels in the given +.Fa category +of the +.Nm logging context +.Dq Fa lc . +It also attempts to free the channel by calling +.Fn log_free_channel +(see its description, below). +.Pp +The +.Fn log_option +function is used to change the +.Fa option +of the indicated logging context +.Fa lc +to the given +.Fa value . +The +.Fa option +can be either +.Dv LOG_OPTION_LEVEL +or +.Dv LOG_OPTION_DEBUG ; +in the first case, the log context's debugging level is reset to the +indicated level. If the +.Fa option +is +.Dv LOG_OPTION_DEBUG , +then a non-zero +.Fa value +results in setting the debug flag of the logging context, while a zero +.Fa value +means that the debug flag is reset. +.Pp +The +.Fn log_category_is_active +test returns a 1 if the given +.Fa category +of the indicated logging context +.Fa lc +has at least one logging channel, and 0, otherwise. +.Pp +The functions +.Fn log_new_syslog_channel , +.Fn log_new_file_channel , +and +.Fn log_new_null_channel +create a new channel of the type specified (thus, the difference in arguments); +the +.Dq Va type +field of the new +.Dq Ft struct log_channel +is always set to the appropriate value. +.Pp +The +.Fn log_new_syslog_channel +function +.Xr malloc 3 Ns -s +a new +.Ft struct log_channel +of +.Va type +.Dv log_syslog , +i.e., a logging channel which will use +.Xr syslog 3 . +The new structure is filled out with the +.Dq Fa flags , +.Dq Fa level , +and +.Dq Fa facility +which are given; the +.Va references +field is initialized to zero. +See +.Sx Logging Channel Flags +and +.Sx Message Priorities , +above, or the header file for information about acceptable values for +.Dq Fa flags , +and +.Dq Fa level . +The +.Dq Fa facility . +can be any valid +.Xr syslog 3 +facility; see the appropriate system header file or manpage for more +information. +.Pp +.Ft log_channel +.Fn log_new_file_channel "unsigned int flags" "int level" \ + "char *name" "FILE *stream" "unsigned int versions" \ + "unsigned long max_size" +.Pp +.Fn log_new_null_channel +.Pp +The functions +.Fn log_inc_references +and +.Fn log_dec_references +increment or decrements, respectively, the +.Va references +field of the logging channel pointed to by +.Dq Fa chan , +if it is a valid channel (and if the +.Va references +field is strictly positive, in the case of +.Fn log_dec_references ) . +These functions are meant to track changes in the number of different clients +which refer to the given logging channel. +.Pp +The +.Fn log_free_channel +function frees the +field of the logging channel pointed to by +.Dq Fa chan +if there are no more outstanding references to it. If the channel uses a file, +the stream is +.Xr fclose 3 Ns -d +(if the +.Dv LOG_CLOSE_STREAM +flag is set), and the filename, if +.No non- Ns Dv NULL , +is +.Xr free 3 Ns -d +before +.Dq Fa chan +is +.Xr free 3 Ns -d . +.Pp +.\" The following requests should be uncommented and +.\" used where appropriate. This next request is +.\" for sections 2 and 3 function return values only. +.Sh RETURN VALUES +.\" This next request is for sections 1, 6, 7 & 8 only +.Bl -tag -width "log_category_is_active()" +.It Fn log_open_stream +.Dv NULL +is returned under any of several error conditions: +a) if +.Dq Fa chan +is either +.Dv NULL +or a +.No non- Ns Dv log_file +channel +.Pq Va errno No is set to Dv EINVAL ; +b) if either versioning or truncation is requested for a non-normal file +.Pq Va errno No is set to Dv EINVAL ; +c) if any of +.Xr stat 2 , +.Xr open 2 , +or +.Xr fdopen 3 +fails +.Po Va errno +is set by the call which failed +.Pc . +If some value other than +.Dv NULL +is returned, then it is a valid logging stream (either newly-opened or +already-open). +.It Fn log_close_stream +-1 if the stream associated with +.Dq Fa chan +is +.No non- Ns Dv NULL +and the call to +.Xr fclose 3 +fails. +0 if successful or the logging channel pointed to by +.Dq Fa chan +is invalid (i.e., +.Dv NULL +or not a logging channel which has uses a file); in the latter case, +.Va errno +is set to +.Dv EINVAL . +.It Fn log_get_stream +.Dv NULL +under the same conditions as those under which +.Fn log_close_stream , +above, returns 0 (including the setting of +.Va errno ) . +Otherwise, the stream associated with the logging channel is returned. +.It Fn log_get_filename +.Dv NULL +under the same conditions as those under which +.Fn log_close_stream , +above, returns 0 (including the setting of +.Va errno ) . +Otherwise, the name of the file associated with the logging channel is +returned. +.It Fn log_new_context +-1 if +.Xr malloc 3 +fails +.Pq with Va errno No set to Dv ENOMEM . +Otherwise, 0, with +.Dq Va lc->opaque +containing the new structures and information. +.It Fn log_add_channel +-1 if +a) either +.Dq Va lc.opaque +is +.Dv NULL +or +.Fa category +is invalid (negative or greater than or equal to +.Va lcp->num_categories ), with +.Va errno +set to +.Dv EINVAL ; +b) +.Xr malloc 3 +fails +.Pq with Va errno No set to Dv ENOMEM . +Otherwise, 0. +.It Fn log_remove_channel +-1 if +a) either +.Dq Va lc.opaque +is +.Dv NULL +or +.Fa category +is invalid, as under failure condition a) for +.Fn log_add_channel , +above, including the setting of +.Va errno ; +b) no channel numbered +.Fa chan +is found in the logging context indicated by +.Fa lc +.Pq with Va errno No set to Dv ENOENT . +Otherwise, 0. +.It Fn log_option +-1 if +a) +.Dq Va lc.opaque +is +.Dv NULL , +b) +.Fa option +specifies an unknown logging option ; +in either case, +.Va errno +is set to +.Dv EINVAL . +Otherwise, 0. +.It Fn log_category_is_active +-1 if +.Dq Va lc.opaque +is +.Dv NULL +.Pq with Va errno No set to Dv EINVAL ; +1 if the +.Fa category +number is valid and there are logging channels in this +.Fa category +within the indicated logging context; 0 if the +.Fa category +number is invalid or there are no logging channels in this +.Fa category +within the indicated logging context. +.It Fn log_new_syslog_channel +.Dv NULL +if +.Xr malloc 3 +fails +.Pq with Va errno No set to ENOMEM ; +otherwise, a valid +.Dv log_syslog Ns -type +.Ft log_channel . +.It Fn log_new_file_channel +.Dv NULL +if +.Xr malloc 3 +fails +.Pq with Va errno No set to ENOMEM ; +otherwise, a valid +.Dv log_file Ns -type +.Ft log_channel . +.It Fn log_new_null_channel +.Dv NULL +if +.Xr malloc 3 +fails +.Pq with Va errno No set to ENOMEM ; +otherwise, a valid +.Dv log_null Ns -type +.Ft log_channel . +.It Fn log_inc_references +-1 if +.Dq Fa chan +is +.Dv NULL +.Pq with Va errno set to Dv EINVAL . +Otherwise, 0. +.It Fn log_dec_references +-1 if +.Dq Fa chan +is +.Dv NULL +or its +.Va references +field is already <= 0 +.Pq with Va errno set to Dv EINVAL . +Otherwise, 0. +.It Fn log_free_channel +-1 under the same conditions as +.Fn log_dec_references , +above, including the setting of +.Va errno ; +0 otherwise. +.El +.\" .Sh ENVIRONMENT +.Sh FILES +.Bl -tag -width "isc/logging.h" +.It Pa isc/logging.h +include file for logging library +.It Pa syslog.h +.Xr syslog 3 Ns -style +priorities +.El +.\" .Sh EXAMPLES +.\" This next request is for sections 1, 6, 7 & 8 only +.\" (command return values (to shell) and +.\" fprintf/stderr type diagnostics) +.\" .Sh DIAGNOSTICS +.\" The next request is for sections 2 and 3 error +.\" and signal handling only. +.Sh ERRORS +This table shows which functions can return the indicated error in the +.Va errno +variable; see the +.Sx RETURN VALUES +section, above, for more information. +.Bl -tag -width "(any0other0value)0" +.It Dv EINVAL +.Fn log_open_stream , +.Fn log_close_stream , +.Fn log_get_stream , +.Fn log_get_filename , +.Fn log_add_channel , +.Fn log_remove_channel , +.Fn log_option , +.Fn log_category_is_active , +.Fn log_inc_references , +.Fn log_dec_references , +.Fn log_free_channel . +.It Dv ENOENT +.Fn log_remove_channel . +.It Dv ENOMEM +.Fn log_new_context , +.Fn log_add_channel , +.Fn log_new_syslog_channel , +.Fn log_new_file_channel , +.Fn log_new_null_channel . +.It (any other value) +returned via a pass-through of an error code from +.Xr stat 2 , +.Xr open 2 , +or +.Xr fdopen 3 , +which can occur in +.Fn log_open_stream +and functions which call it +.Pq currently, only Fn log_vwrite . +.El +.Pp +Additionally, +.Fn log_vwrite +and +.Fn log_free_context +will fail via +.Fn assert +if +.Dq Va lc.opaque +is +.Dv NULL . +The function +.Fn log_vwrite +can also exit with a critical error logged via +.Xr syslog 3 +indicating a memory overrun +.Sh SEE ALSO +.Xr @INDOT@named @SYS_OPS_EXT@ , +.Xr syslog 3 . +The HTML documentation includes a file, +.Pa logging.html , +which has more information about this logging system. +.\" .Sh STANDARDS +.\" .Sh HISTORY +.Sh AUTHORS +Bob Halley...TODO +.\" .Sh BUGS diff --git a/contrib/bind/lib/isc/logging_p.h b/contrib/bind/lib/isc/logging_p.h new file mode 100644 index 0000000..317582d --- /dev/null +++ b/contrib/bind/lib/isc/logging_p.h @@ -0,0 +1,58 @@ +/* + * Copyright (c) 1996, 1997 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +#ifndef LOGGING_P_H +#define LOGGING_P_H + +typedef struct log_file_desc { + char *name; + size_t name_size; + FILE *stream; + unsigned int versions; + unsigned long max_size; +} log_file_desc; + +typedef union log_output { + int facility; + log_file_desc file; +} log_output; + +struct log_channel { + int level; /* don't log messages > level */ + log_channel_type type; + log_output out; + unsigned int flags; + int references; +}; + +typedef struct log_channel_list { + log_channel channel; + struct log_channel_list *next; +} *log_channel_list; + +#define LOG_BUFFER_SIZE 20480 + +struct log_context { + int num_categories; + char **category_names; + log_channel_list *categories; + int flags; + int level; + char buffer[LOG_BUFFER_SIZE]; +}; + +#endif /* !LOGGING_P_H */ diff --git a/contrib/bind/lib/isc/memcluster.c b/contrib/bind/lib/isc/memcluster.c new file mode 100644 index 0000000..0cdd3d4 --- /dev/null +++ b/contrib/bind/lib/isc/memcluster.c @@ -0,0 +1,278 @@ +/* + * Copyright (c) 1997 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +#if !defined(LINT) && !defined(CODECENTER) +static char rcsid[] = "$Id: memcluster.c,v 8.7 1998/03/27 00:17:31 halley Exp $"; +#endif /* not lint */ + +#include "port_before.h" + +#include <sys/types.h> +#include <sys/uio.h> +#include <sys/param.h> +#include <sys/stat.h> + +#include <netinet/in.h> +#include <arpa/inet.h> +#include <arpa/nameser.h> + +#include <errno.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#include <isc/memcluster.h> +#include <isc/assertions.h> + +#include "port_after.h" + +#define DEF_MAX_SIZE 1100 +#define DEF_MEM_TARGET 4096 + +typedef struct { + void * next; +} memcluster_element; + +#define SMALL_SIZE_LIMIT sizeof(memcluster_element) +#define P_SIZE sizeof(void *) + +struct stats { + u_long gets; + u_long puts; + u_long blocks; + u_long freefrags; +}; + +/* Private data. */ + +static size_t max_size; +static size_t mem_target; +static size_t mem_target_half; +static size_t mem_target_fudge; +static memcluster_element ** freelists; +static struct stats * stats; + +/* Forward. */ + +static size_t quantize(size_t); + +/* Public. */ + +int +meminit(size_t init_max_size, size_t target_size) { + int i; + + if (freelists != NULL) { + errno = EEXIST; + return (-1); + } + if (init_max_size == 0) + max_size = DEF_MAX_SIZE; + else + max_size = init_max_size; + if (target_size == 0) + mem_target = DEF_MEM_TARGET; + else + mem_target = target_size; + mem_target_half = mem_target / 2; + mem_target_fudge = mem_target + mem_target / 4; + freelists = malloc(max_size * sizeof (memcluster_element *)); + stats = malloc((max_size+1) * sizeof (struct stats)); + if (freelists == NULL || stats == NULL) { + errno = ENOMEM; + return (-1); + } + memset(freelists, 0, + max_size * sizeof (memcluster_element *)); + memset(stats, 0, (max_size + 1) * sizeof (struct stats)); + + return (0); +} + +void * +__memget(size_t size) { + size_t new_size = quantize(size); + void *ret; + + if (freelists == NULL) + if (meminit(0, 0) == -1) + return (NULL); + if (size == 0) { + errno = EINVAL; + return (NULL); + } + if (size >= max_size || new_size >= max_size) { + /* memget() was called on something beyond our upper limit. */ + stats[max_size].gets++; + return (malloc(size)); + } + + /* + * If there are no blocks in the free list for this size, get a chunk + * of memory and then break it up into "new_size"-sized blocks, adding + * them to the free list. + */ + if (freelists[new_size] == NULL) { + int i, frags; + size_t total_size; + void *new; + char *curr, *next; + + if (new_size > mem_target_half) + total_size = mem_target_fudge; + else + total_size = mem_target; + new = malloc(total_size); + if (new == NULL) { + errno = ENOMEM; + return (NULL); + } + frags = total_size / new_size; + stats[new_size].blocks++; + stats[new_size].freefrags += frags; + /* Set up a linked-list of blocks of size "new_size". */ + curr = new; + next = curr + new_size; + for (i = 0; i < (frags - 1); i++) { + ((memcluster_element *)curr)->next = next; + curr = next; + next += new_size; + } + /* curr is now pointing at the last block in the array. */ + ((memcluster_element *)curr)->next = freelists[new_size]; + freelists[new_size] = new; + } + + /* The free list uses the "rounded-up" size "new_size": */ + ret = freelists[new_size]; + freelists[new_size] = freelists[new_size]->next; + + /* + * The stats[] uses the _actual_ "size" requested by the + * caller, with the caveat (in the code above) that "size" >= the + * max. size (max_size) ends up getting recorded as a call to + * max_size. + */ + stats[size].gets++; + stats[new_size].freefrags--; + return (ret); +} + +/* + * This is a call from an external caller, + * so we want to count this as a user "put". + */ +void +__memput(void *mem, size_t size) { + size_t new_size = quantize(size); + + REQUIRE(freelists != NULL); + + if (size == 0) { + errno = EINVAL; + return; + } + if (size == max_size || new_size >= max_size) { + /* memput() called on something beyond our upper limit */ + free(mem); + INSIST(stats[max_size].puts < stats[max_size].gets); + stats[max_size].puts++; + return; + } + + /* The free list uses the "rounded-up" size "new_size": */ + ((memcluster_element *)mem)->next = freelists[new_size]; + freelists[new_size] = (memcluster_element *)mem; + + /* + * The stats[] uses the _actual_ "size" requested by the + * caller, with the caveat (in the code above) that "size" >= the + * max. size (max_size) ends up getting recorded as a call to + * max_size. + */ + INSIST(stats[size].puts < stats[size].gets); + stats[size].puts++; + stats[new_size].freefrags++; +} + +void * +__memget_debug(size_t size, const char *file, int line) { + void *ptr; + ptr = __memget(size); + fprintf(stderr, "%s:%d: memget(%lu) -> %p\n", file, line, + (u_long)size, ptr); + return (ptr); +} + +void +__memput_debug(void *ptr, size_t size, const char *file, int line) { + fprintf(stderr, "%s:%d: memput(%p, %lu)\n", file, line, ptr, + (u_long)size); + __memput(ptr, size); +} + +/* + * Print the stats[] on the stream "out" with suitable formatting. + */ +void +memstats(FILE *out) { + size_t i; + + if (freelists == NULL) + return; + for (i = 1; i <= max_size; i++) { + const struct stats *s = &stats[i]; + + if (s->gets == 0 && s->puts == 0) + continue; + INSIST(s->gets >= s->puts); + fprintf(out, "%s%5d: %11lu get, %11lu put, %11lu rem", + (i == max_size) ? ">=" : " ", + i, s->gets, s->puts, s->gets - s->puts); + if (s->blocks != 0) + fprintf(out, " (%lu bl, %lu ff)", + s->blocks, s->freefrags); + fputc('\n', out); + } +} + +/* Private. */ + +/* + * Round up size to a multiple of sizeof(void *). This guarantees that a + * block is at least sizeof void *, and that we won't violate alignment + * restrictions, both of which are needed to make lists of blocks. + */ +static size_t +quantize(size_t size) { + int remainder; + /* + * If there is no remainder for the integer division of + * + * (rightsize/P_SIZE) + * + * then we already have a good size; if not, then we need + * to round up the result in order to get a size big + * enough to satisfy the request _and_ aligned on P_SIZE boundaries. + */ + remainder = size % P_SIZE; + if (remainder != 0) + size += P_SIZE - remainder; + return (size); +} + diff --git a/contrib/bind/lib/isc/memcluster.mdoc b/contrib/bind/lib/isc/memcluster.mdoc new file mode 100644 index 0000000..c076972 --- /dev/null +++ b/contrib/bind/lib/isc/memcluster.mdoc @@ -0,0 +1,375 @@ +.\" $Id: memcluster.mdoc,v 8.1 1997/09/26 17:56:10 halley Exp $ +.\" +.\"Copyright (c) 1995, 1996 by Internet Software Consortium +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.\" The following six UNCOMMENTED lines are required. +.Dd Month day, year +.\"Os OPERATING_SYSTEM [version/release] +.Os BSD 4 +.\"Dt DOCUMENT_TITLE [section number] [volume] +.Dt memcluster 3 +.Sh NAME +.Nm meminit , +.Nm memget , +.Nm memput , +.Nm memstats +.Nd memory allocation/deallocation system +.Sh SYNOPSIS +.Fd #include \&<isc/memcluster.h\&> +.Ft void * +.Fn memget "size_t size" +.Ft void +.Fn memput "void *mem" "size_t size" +.Ft void +.Fn memstats "FILE *out" +.Sh DESCRIPTION +These functions access a memory management system which allows callers to not +fragment memory to the extent which can ordinarily occur through many random +calls to +.Xr malloc 3 . +Instead, +.Fn memget +gets a large contiguous chunk of blocks of the requested +.Fa size +and parcels out these blocks as requested. The symmetric call is +.Fn memput , +which callers use to return a piece of memory obtained from +.Fn memget . +Statistics about memory usage are returned by +.Fn memstats , +which prints a report on the stream +.Fa out . +.Ss INTERNALS +Internally, linked lists of free memory blocks are stored in an array. +The size of this array is determined by the value +.Dv MEM_FREECOUNT , +currently set to 1100. In general, for any requested blocksize +.Dq Fa size , +any free blocks will be stored on the linked list at that index. +No free lists are managed for blocks greater than or equal to +.Dv MEM_FREECOUNT +bytes; instead, calls to +.Xr malloc 3 +or +.Xr free 3 +are made, directly. +.Pp +Since the blocks are actually stored as linked lists, they must at least +be large enough to hold a pointer to the next block. This size, which is +.Dv SMALL_SIZE_LIMIT , +is currently defined as +.Bd -literal -offset indent +#define SMALL_SIZE_LIMIT sizeof(struct { void *next; }) +.Ed +.Pp +Both +.Fn memget +and +.Fn memput +enforce this limit; for example, any call to +.Fn memget +requesting a block smaller than +.Dv SMALL_SIZE_LIMIT +bytes will actually be considered to be of size +.Dv SMALL_SIZE_LIMIT +internally. (Such a caller request will be logged for +.Fn memstats +purposes using the caller-requested +.Fa size ; +see the discussion of +.Fn memstats , +below, for more information.) +.Pp +Additionally, the requested +.Fa size +will be adjusted so that when a large +.Xr malloc 3 Ns No -d +chunk of memory is broken up into a linked list, the blocks will all fall on +the correct memory alignment boundaries. Thus, one can conceptualize a call +which mentions +.Fa size +as resulting in a +.Fa new_size +which is used internally. +.Pp +In order to more efficiently allocate memory, there is a +.Dq target +size for calls to +.Xr malloc 3 . +It is given by the pre-defined value +.Dv MEM_TARGET , +which is currently 4096 bytes. +For any requested block +.Fa size , +enough memory is +.Xr malloc 3 Ns No -d +in order to fill up a block of about +.Dv MEM_TARGET +bytes. +.No [ Ns Sy NOTE : +For allocations larger than +.Dv MEM_TARGET Ns No /2 +bytes, there is a +.Dq fudge factor +introduced which boosts the target size by 25% of +.Dv MEM_TARGET . +This means that enough memory for two blocks +will actually be allocated for any +.Fa size +such that +.Pq Dv MEM_TARGET Ns No / 3 +.No < Fa size No < +.Pq Dv MEM_TARGET Ns No *5/8 , +provided that the value of +.Dv MEM_FREECOUNT +is at least as large as the upper limit shown above.] +.Pp +.Ss FUNCTION DESCRIPTIONS +.Pp +The function +.Fn memget +returns a pointer to a block of memory of at least the requested +.Fa size . +After adjusting +.Fa size +to the value +.Va new_size +as mentioned above in the +.Sx INTERNALS +subsection, the internal array of free lists is checked. +If there is no block of the needed +.Va new_size , +then +.Fn memget +will +.Xr malloc 3 +a chunk of memory which is as many times as +.Va new_size +will fit into the target size. This memory is then turned into a linked list +of +.Va new_size Ns No -sized +blocks which are given out as requested; the last such block is the first one +returned by +.Fn memget . +If the requested +.Fa size +is zero or negative, then +.Dv NULL +is returned and +.Va errno +is set to +.Dv EINVAL ; +if +.Fa size +is larger than or equal to the pre-defined maximum size +.Dv MEM_FREECOUNT , +then only a single block of exactly +.Fa size +will be +.Xr malloc 3 Ns No -d +and returned. +.Pp +The +.Fn memput +call is used to return memory once the caller is finished with it. +After adjusting +.Fa size +the the value +.Va new_size +as mentioned in the +.Sx INTERNALS +subsection, above, the block is placed at the head of the free list of +.Va new_size Ns No -sized blocks. +If the given +.Fa size +is zero or negative, then +.Va errno +is set to +.Dv EINVAL , +as for +.Fn memget . +If +.Fa size +is larger than or equal to the pre-defined maximum size +.Dv MEM_FREECOUNT , +then the block is immediately +.Xr free 3 Ns No -d . +.Pp +.Sy NOTE : +It is important that callers give +.Fn memput +.Em only +blocks of memory which were previously obtained from +.Fn memget +if the block is +.Em actually +less than +.Dv SMALL_SIZE_LIMIT +bytes in size. Since all blocks will be added to a free list, any block +which is not at least +.Dv SMALL_SIZE_LIMIT +bytes long will not be able to hold a pointer to the next block in the +free list. +.Pp +The +.Fn memstats +function will summarize the number of calls to +.Fn memget +and +.Fn memput +for any block size from 1 byte up to +.Pq Dv MEM_FREECOUNT No - 1 +bytes, followed by a single line for any calls using a +.Fa size +greater than or equal to +.Dv MEM_FREECOUNT ; +a brief header with shell-style comment lines prefaces the report and +explains the information. The +.Dv FILE +pointer +.Fa out +identifies the stream which is used for this report. Currently, +.Fn memstat +reports the number of calls to +.Fn memget +and +.Fn memput +using the caller-supplied value +.Fa size ; +the percentage of outstanding blocks of a given size (i.e., the percentage +by which calls to +.Fn memget +exceed +.Fn memput ) +are also reported on the line for blocks of the given +.Fa size . +However, the percent of blocks used is computed using the number of +blocks allocated according to the internal parameter +.Va new_size ; +it is the percentage of blocks used to those available at a given +.Va new_size , +and is computed using the +.Em total +number of caller +.Dq gets +for any caller +.Fa size Ns No -s +which map to the internally-computed +.Va new_size . +Keep in mind that +.Va new_size +is generally +.Em not +equal to +.Fa size , +which has these implications: +.Bl -enum -offset -indent means that, for +.It +For +.Fa size +smaller than +.Dv SMALL_SIZE_LIMIT , +.Fn memstat +.Em will +show statistics for caller requests under +.Fa size , +but "percent used" information about such blocks will be reported under +.Dv SMALL_SIZE_LIMIT Ns No -sized +blocks. +.It +As a general case of point 1, internal statistics are reported on the the +line corresponding to +.Va new_size , +so that, for a given caller-supplied +.Fa size , +the associated internal information will appear on that line or on the next +line which shows "percent used" information. +.El +.Pp +.Sy NOTE : +If the caller returns blocks of a given +.Fa size +and requests others of +.Fa size Ns No -s +which map to the same internal +.Va new_size , +it is possible for +.Fn memstats +to report usage of greater than 100% for blocks of size +.Va new_size . +This should be viewed as A Good Thing. +.Sh RETURN VALUES +The function +.Fn memget +returns a +.No non- Ns Dv NULL +pointer to a block of memory of the requested +.Fa size . +It returns +.Dv NULL +if either the +.Fa size +is invalid (less than or equal to zero) or a +.Xr malloc 3 +of a new block of memory fails. In the former case, +.Va errno +is set to +.Dv EINVAL ; +in the latter, it is set to +.Dv ENOMEM . +.Pp +Neither +.Fn memput +nor +.Fn memstats +return a value. +.\" This next request is for sections 1, 6, 7 & 8 only +.\" .Sh ENVIRONMENT +.\" .Sh FILES +.\" .Sh EXAMPLES +.\" This next request is for sections 1, 6, 7 & 8 only +.\" (command return values (to shell) and +.\" fprintf/stderr type diagnostics) +.\" .Sh DIAGNOSTICS +.\" The next request is for sections 2 and 3 error +.\" and signal handling only. +.Sh ERRORS +.Va errno +is set as follows: +.Bl -tag -width "ENOMEM " -offset indent +.It Dv EINVAL +set by both +.Fn memget +and +.Fn memput +if the +.Fa size +is zero or negative +.It Dv ENOMEM +set by +.Fn memget +if a call to +.Xr malloc 3 +fails +.El +.Sh SEE ALSO +.Xr free 3 , +.Xr malloc 3 . +.\" .Sh STANDARDS +.\" .Sh HISTORY +.Sh AUTHORS +Steven J. Richardson and Paul Vixie, Vixie Enterprises. +.\" .Sh BUGS diff --git a/contrib/bind/lib/isc/tree.c b/contrib/bind/lib/isc/tree.c new file mode 100644 index 0000000..ce500ec --- /dev/null +++ b/contrib/bind/lib/isc/tree.c @@ -0,0 +1,532 @@ +#ifndef LINT +static char RCSid[] = "$Id: tree.c,v 8.6 1997/09/26 17:56:11 halley Exp $"; +#endif + +/* + * tree - balanced binary tree library + * + * vix 05apr94 [removed vixie.h dependencies; cleaned up formatting, names] + * vix 22jan93 [revisited; uses RCS, ANSI, POSIX; has bug fixes] + * vix 23jun86 [added delete uar to add for replaced nodes] + * vix 20jun86 [added tree_delete per wirth a+ds (mod2 v.) p. 224] + * vix 06feb86 [added tree_mung()] + * vix 02feb86 [added tree balancing from wirth "a+ds=p" p. 220-221] + * vix 14dec85 [written] + */ + +/* + * This program text was created by Paul Vixie using examples from the book: + * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN + * 0-13-022005-1. Any errors in the conversion from Modula-2 to C are Paul + * Vixie's. + */ + +/* + * Portions Copyright (c) 1996,1997 by Internet Software Consortium. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS + * ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE + * CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL + * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR + * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS + * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS + * SOFTWARE. + */ + +/*#define DEBUG "tree"*/ + +#include "port_before.h" + +#include <stdio.h> +#include <stdlib.h> + +#include "port_after.h" + +#include <isc/memcluster.h> +#include <isc/tree.h> + +#ifdef DEBUG +static int debugDepth = 0; +static char *debugFuncs[256]; +# define ENTER(proc) { \ + debugFuncs[debugDepth] = proc; \ + fprintf(stderr, "ENTER(%d:%s.%s)\n", \ + debugDepth, DEBUG, + debugFuncs[debugDepth]); \ + debugDepth++; \ + } +# define RET(value) { \ + debugDepth--; \ + fprintf(stderr, "RET(%d:%s.%s)\n", \ + debugDepth, DEBUG, \ + debugFuncs[debugDepth]); \ + return (value); \ + } +# define RETV { \ + debugDepth--; \ + fprintf(stderr, "RETV(%d:%s.%s)\n", \ + debugDepth, DEBUG, \ + debugFuncs[debugDepth]); \ + return; \ + } +# define MSG(msg) fprintf(stderr, "MSG(%s)\n", msg); +#else +# define ENTER(proc) ; +# define RET(value) return (value); +# define RETV return; +# define MSG(msg) ; +#endif + +#ifndef TRUE +# define TRUE 1 +# define FALSE 0 +#endif + +static tree * sprout(tree **, tree_t, int *, int (*)(), void (*)()); +static int delete(tree **, int (*)(), tree_t, void (*)(), int *, int *); +static void del(tree **, int *, tree **, void (*)(), int *); +static void bal_L(tree **, int *); +static void bal_R(tree **, int *); + +void +tree_init(tree **ppr_tree) { + ENTER("tree_init") + *ppr_tree = NULL; + RETV +} + +tree_t +tree_srch(tree **ppr_tree, int (*pfi_compare)(), tree_t p_user) { + ENTER("tree_srch") + + if (*ppr_tree) { + int i_comp = (*pfi_compare)(p_user, (**ppr_tree).data); + + if (i_comp > 0) + RET(tree_srch(&(**ppr_tree).right, + pfi_compare, + p_user)) + + if (i_comp < 0) + RET(tree_srch(&(**ppr_tree).left, + pfi_compare, + p_user)) + + /* not higher, not lower... this must be the one. + */ + RET((**ppr_tree).data) + } + + /* grounded. NOT found. + */ + RET(NULL) +} + +tree_t +tree_add(tree **ppr_tree, int (*pfi_compare)(), + tree_t p_user, void (*pfv_uar)()) +{ + int i_balance = FALSE; + + ENTER("tree_add") + if (!sprout(ppr_tree, p_user, &i_balance, pfi_compare, pfv_uar)) + RET(NULL) + RET(p_user) +} + +int +tree_delete(tree **ppr_p, int (*pfi_compare)(), + tree_t p_user, void (*pfv_uar)()) +{ + int i_balance = FALSE, i_uar_called = FALSE; + + ENTER("tree_delete"); + RET(delete(ppr_p, pfi_compare, p_user, pfv_uar, + &i_balance, &i_uar_called)) +} + +int +tree_trav(tree **ppr_tree, int (*pfi_uar)()) { + ENTER("tree_trav") + + if (!*ppr_tree) + RET(TRUE) + + if (!tree_trav(&(**ppr_tree).left, pfi_uar)) + RET(FALSE) + if (!(*pfi_uar)((**ppr_tree).data)) + RET(FALSE) + if (!tree_trav(&(**ppr_tree).right, pfi_uar)) + RET(FALSE) + RET(TRUE) +} + +void +tree_mung(tree **ppr_tree, void (*pfv_uar)()) { + ENTER("tree_mung") + if (*ppr_tree) { + tree_mung(&(**ppr_tree).left, pfv_uar); + tree_mung(&(**ppr_tree).right, pfv_uar); + if (pfv_uar) + (*pfv_uar)((**ppr_tree).data); + memput(*ppr_tree, sizeof(tree)); + *ppr_tree = NULL; + } + RETV +} + +static tree * +sprout(tree **ppr, tree_t p_data, int *pi_balance, + int (*pfi_compare)(), void (*pfv_delete)()) +{ + tree *p1, *p2, *sub; + int cmp; + + ENTER("sprout") + + /* are we grounded? if so, add the node "here" and set the rebalance + * flag, then exit. + */ + if (!*ppr) { + MSG("grounded. adding new node, setting h=true") + *ppr = (tree *) memget(sizeof(tree)); + if (*ppr) { + (*ppr)->left = NULL; + (*ppr)->right = NULL; + (*ppr)->bal = 0; + (*ppr)->data = p_data; + *pi_balance = TRUE; + } + RET(*ppr); + } + + /* compare the data using routine passed by caller. + */ + cmp = (*pfi_compare)(p_data, (*ppr)->data); + + /* if LESS, prepare to move to the left. + */ + if (cmp < 0) { + MSG("LESS. sprouting left.") + sub = sprout(&(*ppr)->left, p_data, pi_balance, + pfi_compare, pfv_delete); + if (sub && *pi_balance) { /* left branch has grown */ + MSG("LESS: left branch has grown") + switch ((*ppr)->bal) { + case 1: + /* right branch WAS longer; bal is ok now */ + MSG("LESS: case 1.. bal restored implicitly") + (*ppr)->bal = 0; + *pi_balance = FALSE; + break; + case 0: + /* balance WAS okay; now left branch longer */ + MSG("LESS: case 0.. balnce bad but still ok") + (*ppr)->bal = -1; + break; + case -1: + /* left branch was already too long. rebal */ + MSG("LESS: case -1: rebalancing") + p1 = (*ppr)->left; + if (p1->bal == -1) { /* LL */ + MSG("LESS: single LL") + (*ppr)->left = p1->right; + p1->right = *ppr; + (*ppr)->bal = 0; + *ppr = p1; + } else { /* double LR */ + MSG("LESS: double LR") + + p2 = p1->right; + p1->right = p2->left; + p2->left = p1; + + (*ppr)->left = p2->right; + p2->right = *ppr; + + if (p2->bal == -1) + (*ppr)->bal = 1; + else + (*ppr)->bal = 0; + + if (p2->bal == 1) + p1->bal = -1; + else + p1->bal = 0; + *ppr = p2; + } /*else*/ + (*ppr)->bal = 0; + *pi_balance = FALSE; + } /*switch*/ + } /*if*/ + RET(sub) + } /*if*/ + + /* if MORE, prepare to move to the right. + */ + if (cmp > 0) { + MSG("MORE: sprouting to the right") + sub = sprout(&(*ppr)->right, p_data, pi_balance, + pfi_compare, pfv_delete); + if (sub && *pi_balance) { + MSG("MORE: right branch has grown") + + switch ((*ppr)->bal) { + case -1: + MSG("MORE: balance was off, fixed implicitly") + (*ppr)->bal = 0; + *pi_balance = FALSE; + break; + case 0: + MSG("MORE: balance was okay, now off but ok") + (*ppr)->bal = 1; + break; + case 1: + MSG("MORE: balance was off, need to rebalance") + p1 = (*ppr)->right; + if (p1->bal == 1) { /* RR */ + MSG("MORE: single RR") + (*ppr)->right = p1->left; + p1->left = *ppr; + (*ppr)->bal = 0; + *ppr = p1; + } else { /* double RL */ + MSG("MORE: double RL") + + p2 = p1->left; + p1->left = p2->right; + p2->right = p1; + + (*ppr)->right = p2->left; + p2->left = *ppr; + + if (p2->bal == 1) + (*ppr)->bal = -1; + else + (*ppr)->bal = 0; + + if (p2->bal == -1) + p1->bal = 1; + else + p1->bal = 0; + + *ppr = p2; + } /*else*/ + (*ppr)->bal = 0; + *pi_balance = FALSE; + } /*switch*/ + } /*if*/ + RET(sub) + } /*if*/ + + /* not less, not more: this is the same key! replace... + */ + MSG("FOUND: Replacing data value") + *pi_balance = FALSE; + if (pfv_delete) + (*pfv_delete)((*ppr)->data); + (*ppr)->data = p_data; + RET(*ppr) +} + +static int +delete(tree **ppr_p, int (*pfi_compare)(), tree_t p_user, + void (*pfv_uar)(), int *pi_balance, int *pi_uar_called) +{ + tree *pr_q; + int i_comp, i_ret; + + ENTER("delete") + + if (*ppr_p == NULL) { + MSG("key not in tree") + RET(FALSE) + } + + i_comp = (*pfi_compare)((*ppr_p)->data, p_user); + if (i_comp > 0) { + MSG("too high - scan left") + i_ret = delete(&(*ppr_p)->left, pfi_compare, p_user, pfv_uar, + pi_balance, pi_uar_called); + if (*pi_balance) + bal_L(ppr_p, pi_balance); + } else if (i_comp < 0) { + MSG("too low - scan right") + i_ret = delete(&(*ppr_p)->right, pfi_compare, p_user, pfv_uar, + pi_balance, pi_uar_called); + if (*pi_balance) + bal_R(ppr_p, pi_balance); + } else { + MSG("equal") + pr_q = *ppr_p; + if (pr_q->right == NULL) { + MSG("right subtree null") + *ppr_p = pr_q->left; + *pi_balance = TRUE; + } else if (pr_q->left == NULL) { + MSG("right subtree non-null, left subtree null") + *ppr_p = pr_q->right; + *pi_balance = TRUE; + } else { + MSG("neither subtree null") + del(&pr_q->left, pi_balance, &pr_q, + pfv_uar, pi_uar_called); + if (*pi_balance) + bal_L(ppr_p, pi_balance); + } + if (!*pi_uar_called && pfv_uar) + (*pfv_uar)(pr_q->data); + /* Thanks to wuth@castrov.cuc.ab.ca for the following stmt. */ + memput(pr_q, sizeof(tree)); + i_ret = TRUE; + } + RET(i_ret) +} + +static void +del(tree **ppr_r, int *pi_balance, tree **ppr_q, + void (*pfv_uar)(), int *pi_uar_called) +{ + ENTER("del") + + if ((*ppr_r)->right != NULL) { + del(&(*ppr_r)->right, pi_balance, ppr_q, + pfv_uar, pi_uar_called); + if (*pi_balance) + bal_R(ppr_r, pi_balance); + } else { + if (pfv_uar) + (*pfv_uar)((*ppr_q)->data); + *pi_uar_called = TRUE; + (*ppr_q)->data = (*ppr_r)->data; + *ppr_q = *ppr_r; + *ppr_r = (*ppr_r)->left; + *pi_balance = TRUE; + } + + RETV +} + +static void +bal_L(tree **ppr_p, int *pi_balance) { + tree *p1, *p2; + int b1, b2; + + ENTER("bal_L") + MSG("left branch has shrunk") + + switch ((*ppr_p)->bal) { + case -1: + MSG("was imbalanced, fixed implicitly") + (*ppr_p)->bal = 0; + break; + case 0: + MSG("was okay, is now one off") + (*ppr_p)->bal = 1; + *pi_balance = FALSE; + break; + case 1: + MSG("was already off, this is too much") + p1 = (*ppr_p)->right; + b1 = p1->bal; + if (b1 >= 0) { + MSG("single RR") + (*ppr_p)->right = p1->left; + p1->left = *ppr_p; + if (b1 == 0) { + MSG("b1 == 0") + (*ppr_p)->bal = 1; + p1->bal = -1; + *pi_balance = FALSE; + } else { + MSG("b1 != 0") + (*ppr_p)->bal = 0; + p1->bal = 0; + } + *ppr_p = p1; + } else { + MSG("double RL") + p2 = p1->left; + b2 = p2->bal; + p1->left = p2->right; + p2->right = p1; + (*ppr_p)->right = p2->left; + p2->left = *ppr_p; + if (b2 == 1) + (*ppr_p)->bal = -1; + else + (*ppr_p)->bal = 0; + if (b2 == -1) + p1->bal = 1; + else + p1->bal = 0; + *ppr_p = p2; + p2->bal = 0; + } + } + RETV +} + +static void +bal_R(tree **ppr_p, int *pi_balance) { + tree *p1, *p2; + int b1, b2; + + ENTER("bal_R") + MSG("right branch has shrunk") + switch ((*ppr_p)->bal) { + case 1: + MSG("was imbalanced, fixed implicitly") + (*ppr_p)->bal = 0; + break; + case 0: + MSG("was okay, is now one off") + (*ppr_p)->bal = -1; + *pi_balance = FALSE; + break; + case -1: + MSG("was already off, this is too much") + p1 = (*ppr_p)->left; + b1 = p1->bal; + if (b1 <= 0) { + MSG("single LL") + (*ppr_p)->left = p1->right; + p1->right = *ppr_p; + if (b1 == 0) { + MSG("b1 == 0") + (*ppr_p)->bal = -1; + p1->bal = 1; + *pi_balance = FALSE; + } else { + MSG("b1 != 0") + (*ppr_p)->bal = 0; + p1->bal = 0; + } + *ppr_p = p1; + } else { + MSG("double LR") + p2 = p1->right; + b2 = p2->bal; + p1->right = p2->left; + p2->left = p1; + (*ppr_p)->left = p2->right; + p2->right = *ppr_p; + if (b2 == -1) + (*ppr_p)->bal = 1; + else + (*ppr_p)->bal = 0; + if (b2 == 1) + p1->bal = -1; + else + p1->bal = 0; + *ppr_p = p2; + p2->bal = 0; + } + } + RETV +} diff --git a/contrib/bind/lib/isc/tree.mdoc b/contrib/bind/lib/isc/tree.mdoc new file mode 100644 index 0000000..2406219 --- /dev/null +++ b/contrib/bind/lib/isc/tree.mdoc @@ -0,0 +1,154 @@ +.\" $Id: tree.mdoc,v 8.1 1997/01/30 20:27:25 vixie Exp $ +.\" +.\"Copyright (c) 1995, 1996 by Internet Software Consortium +.\" +.\"Permission to use, copy, modify, and distribute this software for any +.\"purpose with or without fee is hereby granted, provided that the above +.\"copyright notice and this permission notice appear in all copies. +.\" +.\"THE SOFTWARE IS PROVIDED "AS IS" AND INTERNET SOFTWARE CONSORTIUM DISCLAIMS +.\"ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES +.\"OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL INTERNET SOFTWARE +.\"CONSORTIUM BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL +.\"DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR +.\"PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS +.\"ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS +.\"SOFTWARE. +.\" +.Dd April 5, 1994 +.Dt TREE 3 +.Os BSD 4 +.Sh NAME +.Nm tree_init , +.Nm tree_mung , +.Nm tree_srch , +.Nm tree_add , +.Nm tree_delete , +.Nm tree_trav +.Nd balanced binary tree routines +.Sh SYNOPSIS +.Ft void +.Fn tree_init "void **tree" +.Ft void * +.Fn tree_srch "void **tree" "int (*compare)()" "void *data" +.Ft void +.Fn tree_add(tree, compare, data, del_uar) "void **tree" "int (*compare)()" \ +"void *data" "void (*del_uar)()" +.Ft int +.Fn tree_delete(tree, compare, data, del_uar) "void **tree" "int (*compare)()" \ +"void *data" "void (*del_uar)()" +.Ft int +.Fn tree_trav(tree, trav_uar) "void **tree" "int (*trav_uar)()" +.Ft void +.Fn tree_mung(tree, del_uar) "void **tree" "void (*del_uar)()" +.Sh DESCRIPTION +These functions create and manipulate a balanced binary (AVL) tree. Each node +of the tree contains the expected left & right subtree pointers, a short int +balance indicator, and a pointer to the user data. On a 32 bit system, this +means an overhead of 4+4+2+4 bytes per node (or, on a RISC or otherwise +alignment constrained system with implied padding, 4+4+4+4 bytes per node). +There is no key data type enforced by this package; a caller supplied +compare routine is used to compare user data blocks. +.Pp +Balanced binary trees are very fast on searches and replacements, but have a +moderately high cost for additions and deletions. If your application does a +lot more searches and replacements than it does additions and deletions, the +balanced (AVL) binary tree is a good choice for a data structure. +.Pp +.Fn Tree_init +creates an empty tree and binds it to +.Dq Fa tree +(which for this and all other routines in this package should be declared as +a pointer to void or int, and passed by reference), which can then be used by +other routines in this package. Note that more than one +.Dq Fa tree +variable can exist at once; thus multiple trees can be manipulated +simultaneously. +.Pp +.Fn Tree_srch +searches a tree for a specific node and returns either +.Fa NULL +if no node was found, or the value of the user data pointer if the node +was found. +.Fn compare +is the address of a function to compare two user data blocks. This routine +should work much the way +.Xr strcmp 3 +does; in fact, +.Xr strcmp +could be used if the user data was a \s-2NUL\s+2 terminated string. +.Dq Fa Data +is the address of a user data block to be used by +.Fn compare +as the search criteria. The tree is searched for a node where +.Fn compare +returns 0. +.Pp +.Fn Tree_add +inserts or replaces a node in the specified tree. The tree specified by +.Dq Fa tree +is searched as in +.Fn tree_srch, +and if a node is found to match +.Dq Fa data, +then the +.Fn del_uar +function, if non\-\s-2NULL\s+2, is called with the address of the user data +block for the node (this routine should deallocate any dynamic memory which +is referenced exclusively by the node); the user data pointer for the node +is then replaced by the value of +.Dq Fa data. +If no node is found to match, a new node is added (which may or may not +cause a transparent rebalance operation), with a user data pointer equal to +.Dq Fa data. +A rebalance may or may not occur, depending on where the node is added +and what the rest of the tree looks like. +.Fn Tree_add +will return the +.Dq Fa data +pointer unless catastrophe occurs in which case it will return \s-2NULL\s+2. +.Pp +.Fn Tree_delete +deletes a node from +.Dq Fa tree. +A rebalance may or may not occur, depending on where the node is removed from +and what the rest of the tree looks like. +.Fn Tree_delete +returns TRUE if a node was deleted, FALSE otherwise. +.Pp +.Fn Tree_trav +traverses all of +.Dq Fa tree, +calling +.Fn trav_uar +with the address of each user data block. If +.Fn trav_uar +returns FALSE at any time, +.Fn tree_trav +will immediately return FALSE to its caller. Otherwise all nodes will be +reached and +.Fn tree_trav +will return TRUE. +.Pp +.Fn Tree_mung +deletes every node in +.Dq Fa tree, +calling +.Fn del_uar +(if it is not \s-2NULL\s+2) with the user data address from each node (see +.Fn tree_add +and +.Fn tree_delete +above). The tree is left in the same state that +.Fn tree_init +leaves it in \- i.e., empty. +.Sh BUGS +Should have a way for the caller to specify application-specific +.Xr malloc +and +.Xr free +functions to be used internally when allocating meta data. +.Sh AUTHOR +Paul Vixie, converted and augumented from Modula\-2 examples in +.Dq Algorithms & Data Structures , +Niklaus Wirth, Prentice\-Hall, ISBN 0\-13\-022005\-1. |
