aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--.gitignore4
-rw-r--r--ChangeLog323
-rw-r--r--apps/nc/Makefile.am6
-rw-r--r--configure.ac17
-rw-r--r--crypto/CMakeLists.txt3
-rw-r--r--crypto/Makefile.am18
-rw-r--r--include/Makefile.am3
-rw-r--r--include/compat/machine/endian.h11
-rwxr-xr-x[-rw-r--r--]include/compat/pthread.h31
-rw-r--r--include/compat/sys/_null.h18
-rw-r--r--include/compat/sys/queue.h536
-rw-r--r--include/compat/sys/tree.h1006
-rw-r--r--libtls.pc.in3
-rw-r--r--m4/ax_add_fortify_source.m480
-rw-r--r--m4/ax_check_compile_flag.m453
-rw-r--r--m4/check-hardening-options.m42
-rw-r--r--man/links40
-rw-r--r--patches/aeadtest.c.patch10
-rw-r--r--patches/handshake_table.c.patch8
-rw-r--r--patches/openssl.c.patch6
-rw-r--r--patches/tlsexttest.c.patch16
-rw-r--r--ssl/CMakeLists.txt1
-rw-r--r--ssl/Makefile.am10
-rw-r--r--tests/CMakeLists.txt28
-rw-r--r--tests/Makefile.am16
-rw-r--r--tls/Makefile.am9
-rwxr-xr-xupdate.sh2
27 files changed, 2203 insertions, 57 deletions
diff --git a/.gitignore b/.gitignore
index 38ea860..4bef715 100644
--- a/.gitignore
+++ b/.gitignore
@@ -59,6 +59,7 @@ tests/bnaddsub*
59tests/bn_rand_interval* 59tests/bn_rand_interval*
60tests/bn_to_string* 60tests/bn_to_string*
61tests/cipher* 61tests/cipher*
62tests/constraints*
62tests/explicit_bzero* 63tests/explicit_bzero*
63tests/freenull* 64tests/freenull*
64tests/gost2814789t* 65tests/gost2814789t*
@@ -77,6 +78,9 @@ tests/*.pem
77tests/testssl 78tests/testssl
78tests/*.txt 79tests/*.txt
79tests/compat/*.c 80tests/compat/*.c
81tests/verify*
82tests/x509_info*
83tests/x509attribute*
80tests/x509name* 84tests/x509name*
81!tests/optionstest.c 85!tests/optionstest.c
82!tests/*.test 86!tests/*.test
diff --git a/ChangeLog b/ChangeLog
index cba5873..24de35e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -28,11 +28,298 @@ history is also available from Git.
28 28
29LibreSSL Portable Release Notes: 29LibreSSL Portable Release Notes:
30 30
313.2.2 - Stable release
32
33 * Define OPENSSL_NO_SSL_TRACE in opensslfeatures.h.
34
35 * Start replacing the existing TLSv1.2 record layer.
36
37 * Send alert on ssl_get_prev_session() failure.
38
39 * Simplify return codes for tls1_process_ticket() and
40 tls_decrypt_ticket().
41
42 * Simplify tls_decrypt_ticket() exit path.
43
44 * Copy the session id directly in ssl_get_prev_session() instead of
45 handing it through several functions for copying.
46
47 * Split session retrieval out of ssl_get_prev_session().
48
49 * Zero out variable on the stack to avoid leaving garbage in the tail
50 of short session ids.
51
52 * Remove unnecessary zeroing after recallocarray() in
53 ASN1_BIT_STRING_set_bit().
54
55 * Rewrite X509_INFO_{new,free}() more idiomatically.
56
57 * Import commented versions of the latest OPENSSL_NO_* flags from
58 OpenSSL 1.1.1g.
59
60 * Document return value from EC_KEY_get0_public_key(3).
61
62 * Set alpn_selected_len = 0 whenever alpn_selected is NULL.
63
64 * Add option type OPTION_UL_VALUE_OR to openssl(1) option parser.
65
66 * Convert openssl(1) ocsp option handling.
67
68 * Major style cleanup in ocsp.c.
69
70 * Assorted ciphers related cleanup in ssl_lib.c.
71
72 * Add issuer cache in preparation for changes to the validation code.
73
74 * Replace some SSL_AD_* with TLS13_ALERT_* defines in the new TLSv1.3
75 code.
76
77 * Rename ssl_cipher_is_permitted() to the more accurate and specific
78 ssl_cipher_allowed_in_version_range().
79
80 * Simplify SSL_get_ciphers().
81
82 * Remove cipher_list_by_id.
83
84 * Add a new implementation of X509 name constraints with regression
85 tests.
86
87 * Fix and re-enable cert and cipher interop tests.
88
89 * Include machine/endian.h gost2814789.c in order to pick up the
90 __STRICT_ALIGNMENT define.
91
92 * Enable the new X509 name constraints verification.
93
94 * Avoid an out-of-bounds write in BN_rand().
95
96 * Simplify tls1_set_ec_id().
97
98 * Use uint16_t for curve_id.
99
100 * Improve the handling of BIO_read()/BIO_write() failures in the
101 TLSv1.3 stack.
102
103 * Add a new certificate chain validator.
104
105 The new validator finds multiple validated chains to handle the
106 modern PKI cases which may frequently have multiple paths via
107 different intermediates to different roots. It is loosely based on
108 golang's X509 validator.
109
110 This includes integration so that the new validator can be used via
111 X509_verify_cert() as well as a new API x509_verify() which will
112 return multiple chains (similar to go).
113
114 The new public API is not yet exposed, and will be finalized and
115 exposed with a man page and a library minor bump later.
116
117 * Implement SSL_{CTX_,}set_ciphersuites() and add regress. This is not
118 yet public API and will be enabled in a future release.
119
120 * Enable the use of the new X509 chain validator by default.
121
122 * Fix double frees and a NULL dereference introduced on review of the
123 new validator.
124
125 * Remove various unused variables in the X509 code.
126
127 * Fix memory leaks in x509_constraints_chain() and
128 X509V3_ext_add_alias().
129
130 * Add initial manual page for the x509_verify() chain validator which
131 will be installed once the new API is publically exposed.
132
133 * Avoid NULL deref in SSL_{,CTX_}set_ciphersuites().
134
135 * Clean up and simplify SSL_set_session().
136
137 * Move state initialization from SSL_clear() to ssl3_clear() to ensure
138 that it gets correctly reinitialized across a SSL_set_ssl_method()
139 call.
140
141 * Test the Botan TLS client with LibreSSL, OpenSSL 1.0.2 and 1.1.1
142 servers.
143
144 * Mop up the get_ssl_method function pointer.
145
146 * Clean up and simplify SSL_set_ssl_method().
147
148 * Deduplicate the time validation code between the legacy and the new
149 verification code.
150
151 * Set error_depth and current_cert to avoid problems in legacy
152 callbacks that don't do proper error checking.
153
154 * Correct a failure case in tls12_record_layer_seal_record_protected().
155
156 * Do not destroy an existing cipher list when ssl_parse_ciphersuites()
157 fails to match the behavior of ssl_create_cipher_list() and
158 SSL_set_ciphersuites() of OpenSSL.
159
160 * Split the tls12_record_layer_write_mac() for future reuse on the
161 read side.
162
163 * Dedup code in x509_verify_ctx_new_from_xsc().
164
165 * Make check in x509_verify_ctx_set_max_signatures() consistent with
166 others.
167
168 * Avoid memset() before memcpy() for CBS_add_bytes().
169
170 * Make SSL_CTX_get_ciphers(NULL) return NULL rather than crash.
171
172 * Simplify SSL method lookups.
173
174 * Prepare to provide most of the TLSv1.3-related OpenSSL 1.1.1 API.
175 This will be finished in an upcoming release.
176
177 * Fix an overflow in the CN subject line parsing.
178
179 * Correctly handle ssl_cert_dup() failure in SSL_set_SSL_CTX().
180
181 * Fix memory leaks in x509_constraints_extract_names().
182
183 * Correct a 1 byte read overflow in x509_constraints_uri().
184
185 * Ensure the chain is set on the X509_STORE_CTX before triggering
186 callback.
187
188 * Release read and write buffers using freezero()
189
190 * Simplify the cleanup of init_buf via an ssl3_release_init_buffer()
191 function.
192
193 * Fix numerous leaks in the UI_dup_* functions.
194
195 * Simplify and tidy up hte code in ui_lib.c.
196
197 * Refactor dtls1_clear_queues() to make it NULL safe.
198
199 * Have dtls1_hm_fragment_new() call dtls1_hm_fragment_free() on
200 failure.
201
202 * Have dtls1_new() call dtls1_free() on failure.
203
204 * Call dtls1_hm_fragment_free() from dtls1_drain_fragments() to fix
205 potential memory leaks.
206
207 * Ensure that leaf is set up on X509_STORE_CTX before verification.
208
209 * Document SSL_set1_host(3).
210
211 * Document SSL_set_SSL_CTX(3).
212
213 * Make pthread_mutex static initialisation work on Windows.
214
215 * Get __STRICT_ALIGNMENT from machine/endian.h with portable build.
216
313.2.1 - Development release 2173.2.1 - Development release
32 218
33 * Enforce in the TLS 1.3 server that ClientHello messages 219 * Propagate alerts from the read half of the TLSv1.3 record layer to I/O
34 following a HelloRetryRequest must match the original ClientHello 220 functions.
35 as per RFC 8446 section 4.1.2 221
222 * Send a record overflow alert for TLSv1.3 messages having overlong
223 plaintext or inner plaintext.
224
225 * Send an illegal parameter alert if a client sends an invalid DH key
226 share.
227
228 * Document PKCS7_final(3), PKCS7_add_attribute(3).
229
230 * Collapse x509v3 directory into x509.
231
232 * Improve TLSv1.3 client certificate selection to allow EC certificates
233 instead of only RSA certificates.
234
235 * Fail on receiving an invalid NID in X509_ATTRIBUTE_create() instead
236 of constructing a broken objects that may cause NULL pointer accesses.
237
238 * Add support for additional GOST curves from RFC 7836 and
239 draft-deremin-rfc4491-bis.
240
241 * Add OIDs for HMAC using the Streebog hash function.
242
243 * Allow GOST R 34.11-2012 in PBE/PBKDF2/PKCS#5.
244
245 * Enable GOST_SIG_FORMAT_RS_LE when verifying certificate signatures.
246
247 * Handle GOST in ssl_cert_dup().
248
249 * Stop sending GOST R 34.10-94 as a CertificateType.
250
251 * Use IANA allocated GOST ClientCertificateTypes.
252
253 * Add a custom copy handler for AES keywrap to fix a use-after-free.
254
255 * Enforce in the TLSv1.3 server that that ClientHello messages after
256 a HelloRetryRequest match the original ClientHello as per RFC 8446
257 section 4.1.2
258
259 * Document more PKCS7 attribute functions.
260
261 * Document PKCS7_get_signer_info(3).
262
263 * Document PEM_ASN1_read(3) and PEM_ASN1_read_bio(3).
264
265 * Document PEM_def_callback(3).
266
267 * Document EVP_read_pw_string_min(3).
268
269 * Merge documentation of X509_get0_serialNumber from OpenSSL 1.1.1.
270
271 * Document error handling of X509_PUBKEY_get0(3) and X509_PUBKEY_get(3)
272
273 * Document X509_get0_pubkey_bitstr(3).
274
275 * Fix an off-by-one in the CBS padding removal. From BoringSSL.
276
277 * Enforce restrictions on extensions present in the ClientHello as per
278 RFC 8446, section 9.2.
279
280 * Add new CMAC_Init(3) and ChaCha(3) manual pages.
281
282 * Fix SSL_shutdown behavior to match the legacy stack. The previous
283 behavior could cause a hang.
284
285 * Add initial support for openbsd/powerpc64.
286
287 * Make the message type available in the internal TLS extensions API
288 functions.
289
290 * Enable TLSv1.3 for the generic TLS_method().
291
292 * Convert openssl(1) s_client option handling.
293
294 * Document openssl(1) certhash.
295
296 * Convert openssl(1) verify option handling.
297
298 * Fix a longstanding bug in PEM_X509_INFO_read_bio(3) that could cause
299 use-after-free and double-free issues in calling programs.
300
301 * Document PEM_X509_INFO_read(3) and PEM_X509_INFO_read_bio(3).
302
303 * Handle SSL_MODE_AUTO_RETRY being changed during a TLSv1.3 session.
304
305 * Convert openssl(1) s_server option handling.
306
307 * Add minimal info callback support for TLSv1.3.
308
309 * Refactor, clean up and simplify some SSL3/DTLS1 record writing code.
310
311 * Correctly handle server requests for an OCSP response.
312
313 * Add the P-521 curve to the list of curves supported by default
314 in the client.
315
316 * Convert openssl(1) req option handling.
317
318 * Avoid calling freezero with a negative size if a server sends a
319 malformed plaintext of all zeroes.
320
321 * Send an unexpected message alert if no valid content type is found
322 in a TLSv1.3 record.
36 323
373.2.0 - Development release 3243.2.0 - Development release
38 325
@@ -96,6 +383,36 @@ LibreSSL Portable Release Notes:
96 383
97 * Use non-expired certificates first when building a certificate chain. 384 * Use non-expired certificates first when building a certificate chain.
98 385
3863.1.4 - Interoperability and bug fixes for the TLSv1.3 client:
387
388 * Improve client certificate selection to allow EC certificates
389 instead of only RSA certificates.
390
391 * Do not error out if a TLSv1.3 server requests an OCSP response as
392 part of a certificate request.
393
394 * Fix SSL_shutdown behavior to match the legacy stack. The previous
395 behaviour could cause a hang.
396
397 * Fix a memory leak and add a missing error check in the handling of
398 the key update message.
399
400 * Fix a memory leak in tls13_record_layer_set_traffic_key.
401
402 * Avoid calling freezero with a negative size if a server sends a
403 malformed plaintext of all zeroes.
404
405 * Ensure that only PSS may be used with RSA in TLSv1.3 in order
406 to avoid using PKCS1-based signatures.
407
408 * Add the P-521 curve to the list of curves supported by default
409 in the client.
410
4113.1.3 - Bug fix
412
413 * libcrypto may fail to build a valid certificate chain due to
414 expired untrusted issuer certificates.
415
993.1.2 - Bug fix 4163.1.2 - Bug fix
100 417
101 * A TLS client with peer verification disabled may crash when 418 * A TLS client with peer verification disabled may crash when
diff --git a/apps/nc/Makefile.am b/apps/nc/Makefile.am
index 4b5b561..d678f1e 100644
--- a/apps/nc/Makefile.am
+++ b/apps/nc/Makefile.am
@@ -12,9 +12,9 @@ endif
12EXTRA_DIST = nc.1 12EXTRA_DIST = nc.1
13EXTRA_DIST += CMakeLists.txt 13EXTRA_DIST += CMakeLists.txt
14 14
15nc_LDADD = $(abs_top_builddir)/crypto/libcrypto.la 15nc_LDFLAGS = $(abs_top_builddir)/crypto/.libs/libcrypto.a
16nc_LDADD += $(abs_top_builddir)/ssl/libssl.la 16
17nc_LDADD += $(abs_top_builddir)/tls/libtls.la 17nc_LDADD = $(abs_top_builddir)/tls/libtls.la
18nc_LDADD += $(PLATFORM_LDADD) $(PROG_LDADD) 18nc_LDADD += $(PLATFORM_LDADD) $(PROG_LDADD)
19 19
20AM_CPPFLAGS += -I$(top_srcdir)/apps/nc/compat 20AM_CPPFLAGS += -I$(top_srcdir)/apps/nc/compat
diff --git a/configure.ac b/configure.ac
index 888ca19..3aca617 100644
--- a/configure.ac
+++ b/configure.ac
@@ -29,8 +29,7 @@ USER_CFLAGS="$CFLAGS"
29AC_PROG_CC([cc gcc]) 29AC_PROG_CC([cc gcc])
30AC_PROG_CC_STDC 30AC_PROG_CC_STDC
31AM_PROG_CC_C_O 31AM_PROG_CC_C_O
32AC_PROG_LIBTOOL 32LT_INIT([pic-only])
33LT_INIT
34 33
35CHECK_OS_OPTIONS 34CHECK_OS_OPTIONS
36 35
@@ -75,26 +74,12 @@ AC_ARG_ENABLE([tests],
75 [enable_tests="yes"]) 74 [enable_tests="yes"])
76AM_CONDITIONAL([ENABLE_TESTS], [test "x$enable_tests" = xyes]) 75AM_CONDITIONAL([ENABLE_TESTS], [test "x$enable_tests" = xyes])
77 76
78# Add CPU-specific alignment flags
79old_cflags=$CFLAGS
80CFLAGS="$CFLAGS -I$srcdir/include"
81AC_MSG_CHECKING([if BSWAP4 builds without __STRICT_ALIGNMENT])
82AC_TRY_COMPILE([#include "$srcdir/crypto/modes/modes_lcl.h"],
83 [int a = 0; BSWAP4(a);],
84 AC_MSG_RESULT([yes])
85 BSWAP4=yes,
86 AC_MSG_RESULT([no])
87 BSWAP4=no)
88CFLAGS="$old_cflags"
89
90AS_CASE([$host_cpu], 77AS_CASE([$host_cpu],
91 [*sparc*], [CPPFLAGS="$CPPFLAGS -D__STRICT_ALIGNMENT"],
92 [*arm*], [host_cpu=arm], 78 [*arm*], [host_cpu=arm],
93 [*amd64*], [host_cpu=x86_64 HOSTARCH=intel], 79 [*amd64*], [host_cpu=x86_64 HOSTARCH=intel],
94 [i?86], [HOSTARCH=intel], 80 [i?86], [HOSTARCH=intel],
95 [x86_64], [HOSTARCH=intel] 81 [x86_64], [HOSTARCH=intel]
96) 82)
97AS_IF([test "x$BSWAP4" = "xyes" -a "$host_cpu" = "arm" ],,CPPFLAGS="$CPPFLAGS -D__STRICT_ALIGNMENT")
98AM_CONDITIONAL([HOST_CPU_IS_INTEL], [test "x$HOSTARCH" = "xintel"]) 83AM_CONDITIONAL([HOST_CPU_IS_INTEL], [test "x$HOSTARCH" = "xintel"])
99 84
100AC_MSG_CHECKING([if .gnu.warning accepts long strings]) 85AC_MSG_CHECKING([if .gnu.warning accepts long strings])
diff --git a/crypto/CMakeLists.txt b/crypto/CMakeLists.txt
index e57e6c2..7066cc8 100644
--- a/crypto/CMakeLists.txt
+++ b/crypto/CMakeLists.txt
@@ -734,6 +734,7 @@ set(
734 x509/x509_bitst.c 734 x509/x509_bitst.c
735 x509/x509_cmp.c 735 x509/x509_cmp.c
736 x509/x509_conf.c 736 x509/x509_conf.c
737 x509/x509_constraints.c
737 x509/x509_cpols.c 738 x509/x509_cpols.c
738 x509/x509_crld.c 739 x509/x509_crld.c
739 x509/x509_d2.c 740 x509/x509_d2.c
@@ -746,6 +747,7 @@ set(
746 x509/x509_ia5.c 747 x509/x509_ia5.c
747 x509/x509_info.c 748 x509/x509_info.c
748 x509/x509_int.c 749 x509/x509_int.c
750 x509/x509_issuer_cache.c
749 x509/x509_lib.c 751 x509/x509_lib.c
750 x509/x509_lu.c 752 x509/x509_lu.c
751 x509/x509_ncons.c 753 x509/x509_ncons.c
@@ -767,6 +769,7 @@ set(
767 x509/x509_txt.c 769 x509/x509_txt.c
768 x509/x509_utl.c 770 x509/x509_utl.c
769 x509/x509_v3.c 771 x509/x509_v3.c
772 x509/x509_verify.c
770 x509/x509_vfy.c 773 x509/x509_vfy.c
771 x509/x509_vpm.c 774 x509/x509_vpm.c
772 x509/x509cset.c 775 x509/x509cset.c
diff --git a/crypto/Makefile.am b/crypto/Makefile.am
index 6f9887b..97a84e1 100644
--- a/crypto/Makefile.am
+++ b/crypto/Makefile.am
@@ -20,6 +20,7 @@ EXTRA_DIST += compat/strcasecmp.c
20 20
21BUILT_SOURCES = crypto_portable.sym 21BUILT_SOURCES = crypto_portable.sym
22CLEANFILES = crypto_portable.sym 22CLEANFILES = crypto_portable.sym
23CLEANFILES += libcrypto_la_objects.mk
23 24
24crypto_portable.sym: crypto.sym Makefile 25crypto_portable.sym: crypto.sym Makefile
25 -echo "generating crypto_portable.sym ..." 26 -echo "generating crypto_portable.sym ..."
@@ -93,8 +94,20 @@ if HOST_WIN
93 -mv crypto_portable.sym.tmp crypto_portable.sym 94 -mv crypto_portable.sym.tmp crypto_portable.sym
94endif 95endif
95 96
97libcrypto_la_objects.mk: Makefile
98 @echo "libcrypto_la_objects= $(libcrypto_la_OBJECTS)" \
99 | sed 's/ */ $$\(abs_top_builddir\)\/crypto\//g' \
100 > libcrypto_la_objects.mk
101 @echo "libcompat_la_objects= $(libcompat_la_OBJECTS)" \
102 | sed 's/ */ $$\(abs_top_builddir\)\/crypto\//g' \
103 >> libcrypto_la_objects.mk
104 @echo "libcompatnoopt_la_objects= $(libcompatnoopt_la_OBJECTS)" \
105 | sed 's/ */ $$\(abs_top_builddir\)\/crypto\//g' \
106 >> libcrypto_la_objects.mk
107
96libcrypto_la_LDFLAGS = -version-info @LIBCRYPTO_VERSION@ -no-undefined -export-symbols crypto_portable.sym 108libcrypto_la_LDFLAGS = -version-info @LIBCRYPTO_VERSION@ -no-undefined -export-symbols crypto_portable.sym
97EXTRA_libcrypto_la_DEPENDENCIES = crypto_portable.sym 109EXTRA_libcrypto_la_DEPENDENCIES = crypto_portable.sym
110EXTRA_libcrypto_la_DEPENDENCIES += libcrypto_la_objects.mk
98libcrypto_la_LIBADD = libcompat.la 111libcrypto_la_LIBADD = libcompat.la
99if !HAVE_EXPLICIT_BZERO 112if !HAVE_EXPLICIT_BZERO
100libcrypto_la_LIBADD += libcompatnoopt.la 113libcrypto_la_LIBADD += libcompatnoopt.la
@@ -918,6 +931,7 @@ libcrypto_la_SOURCES += x509/x509_bcons.c
918libcrypto_la_SOURCES += x509/x509_bitst.c 931libcrypto_la_SOURCES += x509/x509_bitst.c
919libcrypto_la_SOURCES += x509/x509_cmp.c 932libcrypto_la_SOURCES += x509/x509_cmp.c
920libcrypto_la_SOURCES += x509/x509_conf.c 933libcrypto_la_SOURCES += x509/x509_conf.c
934libcrypto_la_SOURCES += x509/x509_constraints.c
921libcrypto_la_SOURCES += x509/x509_cpols.c 935libcrypto_la_SOURCES += x509/x509_cpols.c
922libcrypto_la_SOURCES += x509/x509_crld.c 936libcrypto_la_SOURCES += x509/x509_crld.c
923libcrypto_la_SOURCES += x509/x509_d2.c 937libcrypto_la_SOURCES += x509/x509_d2.c
@@ -930,6 +944,7 @@ libcrypto_la_SOURCES += x509/x509_genn.c
930libcrypto_la_SOURCES += x509/x509_ia5.c 944libcrypto_la_SOURCES += x509/x509_ia5.c
931libcrypto_la_SOURCES += x509/x509_info.c 945libcrypto_la_SOURCES += x509/x509_info.c
932libcrypto_la_SOURCES += x509/x509_int.c 946libcrypto_la_SOURCES += x509/x509_int.c
947libcrypto_la_SOURCES += x509/x509_issuer_cache.c
933libcrypto_la_SOURCES += x509/x509_lib.c 948libcrypto_la_SOURCES += x509/x509_lib.c
934libcrypto_la_SOURCES += x509/x509_lu.c 949libcrypto_la_SOURCES += x509/x509_lu.c
935libcrypto_la_SOURCES += x509/x509_ncons.c 950libcrypto_la_SOURCES += x509/x509_ncons.c
@@ -951,6 +966,7 @@ libcrypto_la_SOURCES += x509/x509_trs.c
951libcrypto_la_SOURCES += x509/x509_txt.c 966libcrypto_la_SOURCES += x509/x509_txt.c
952libcrypto_la_SOURCES += x509/x509_utl.c 967libcrypto_la_SOURCES += x509/x509_utl.c
953libcrypto_la_SOURCES += x509/x509_v3.c 968libcrypto_la_SOURCES += x509/x509_v3.c
969libcrypto_la_SOURCES += x509/x509_verify.c
954libcrypto_la_SOURCES += x509/x509_vfy.c 970libcrypto_la_SOURCES += x509/x509_vfy.c
955libcrypto_la_SOURCES += x509/x509_vpm.c 971libcrypto_la_SOURCES += x509/x509_vpm.c
956libcrypto_la_SOURCES += x509/x509cset.c 972libcrypto_la_SOURCES += x509/x509cset.c
@@ -962,4 +978,6 @@ libcrypto_la_SOURCES += x509/x_all.c
962noinst_HEADERS += x509/ext_dat.h 978noinst_HEADERS += x509/ext_dat.h
963noinst_HEADERS += x509/pcy_int.h 979noinst_HEADERS += x509/pcy_int.h
964noinst_HEADERS += x509/vpm_int.h 980noinst_HEADERS += x509/vpm_int.h
981noinst_HEADERS += x509/x509_internal.h
982noinst_HEADERS += x509/x509_issuer_cache.h
965noinst_HEADERS += x509/x509_lcl.h 983noinst_HEADERS += x509/x509_lcl.h
diff --git a/include/Makefile.am b/include/Makefile.am
index 6d808cc..4184cf8 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -32,12 +32,15 @@ noinst_HEADERS += compat/netinet/in.h
32noinst_HEADERS += compat/netinet/ip.h 32noinst_HEADERS += compat/netinet/ip.h
33noinst_HEADERS += compat/netinet/tcp.h 33noinst_HEADERS += compat/netinet/tcp.h
34 34
35noinst_HEADERS += compat/sys/_null.h
35noinst_HEADERS += compat/sys/ioctl.h 36noinst_HEADERS += compat/sys/ioctl.h
36noinst_HEADERS += compat/sys/mman.h 37noinst_HEADERS += compat/sys/mman.h
37noinst_HEADERS += compat/sys/param.h 38noinst_HEADERS += compat/sys/param.h
39noinst_HEADERS += compat/sys/queue.h
38noinst_HEADERS += compat/sys/select.h 40noinst_HEADERS += compat/sys/select.h
39noinst_HEADERS += compat/sys/socket.h 41noinst_HEADERS += compat/sys/socket.h
40noinst_HEADERS += compat/sys/stat.h 42noinst_HEADERS += compat/sys/stat.h
43noinst_HEADERS += compat/sys/tree.h
41noinst_HEADERS += compat/sys/time.h 44noinst_HEADERS += compat/sys/time.h
42noinst_HEADERS += compat/sys/types.h 45noinst_HEADERS += compat/sys/types.h
43noinst_HEADERS += compat/sys/uio.h 46noinst_HEADERS += compat/sys/uio.h
diff --git a/include/compat/machine/endian.h b/include/compat/machine/endian.h
index 43dac8f..4dcb60d 100644
--- a/include/compat/machine/endian.h
+++ b/include/compat/machine/endian.h
@@ -37,4 +37,15 @@
37 37
38#endif 38#endif
39 39
40#ifndef __STRICT_ALIGNMENT
41#define __STRICT_ALIGNMENT
42#if defined(__i386) || defined(__i386__) || \
43 defined(__x86_64) || defined(__x86_64__) || \
44 defined(__s390__) || defined(__s390x__) || \
45 defined(__aarch64__) || \
46 ((defined(__arm__) || defined(__arm)) && __ARM_ARCH >= 6)
47#undef __STRICT_ALIGNMENT
48#endif
49#endif
50
40#endif 51#endif
diff --git a/include/compat/pthread.h b/include/compat/pthread.h
index 8b8c3c6..1527d3c 100644..100755
--- a/include/compat/pthread.h
+++ b/include/compat/pthread.h
@@ -8,6 +8,8 @@
8 8
9#ifdef _WIN32 9#ifdef _WIN32
10 10
11#include <malloc.h>
12#include <stdlib.h>
11#include <windows.h> 13#include <windows.h>
12 14
13/* 15/*
@@ -16,6 +18,11 @@
16#define PTHREAD_ONCE_INIT { INIT_ONCE_STATIC_INIT } 18#define PTHREAD_ONCE_INIT { INIT_ONCE_STATIC_INIT }
17 19
18/* 20/*
21 * Static mutex initialization values.
22 */
23#define PTHREAD_MUTEX_INITIALIZER { .lock = NULL }
24
25/*
19 * Once definitions. 26 * Once definitions.
20 */ 27 */
21struct pthread_once { 28struct pthread_once {
@@ -55,27 +62,43 @@ pthread_equal(pthread_t t1, pthread_t t2)
55 return t1 == t2; 62 return t1 == t2;
56} 63}
57 64
58typedef CRITICAL_SECTION pthread_mutex_t; 65struct pthread_mutex {
66 volatile LPCRITICAL_SECTION lock;
67};
68typedef struct pthread_mutex pthread_mutex_t;
59typedef void pthread_mutexattr_t; 69typedef void pthread_mutexattr_t;
60 70
61static inline int 71static inline int
62pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr) 72pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr)
63{ 73{
64 InitializeCriticalSection(mutex); 74 if ((mutex->lock = malloc(sizeof(CRITICAL_SECTION))) == NULL)
75 exit(ENOMEM);
76 InitializeCriticalSection(mutex->lock);
65 return 0; 77 return 0;
66} 78}
67 79
68static inline int 80static inline int
69pthread_mutex_lock(pthread_mutex_t *mutex) 81pthread_mutex_lock(pthread_mutex_t *mutex)
70{ 82{
71 EnterCriticalSection(mutex); 83 if (mutex->lock == NULL) {
84 LPCRITICAL_SECTION lcs;
85
86 if ((lcs = malloc(sizeof(CRITICAL_SECTION))) == NULL)
87 exit(ENOMEM);
88 InitializeCriticalSection(lcs);
89 if (InterlockedCompareExchangePointer((PVOID*)&mutex->lock, (PVOID)lcs, NULL) != NULL) {
90 DeleteCriticalSection(lcs);
91 free(lcs);
92 }
93 }
94 EnterCriticalSection(mutex->lock);
72 return 0; 95 return 0;
73} 96}
74 97
75static inline int 98static inline int
76pthread_mutex_unlock(pthread_mutex_t *mutex) 99pthread_mutex_unlock(pthread_mutex_t *mutex)
77{ 100{
78 LeaveCriticalSection(mutex); 101 LeaveCriticalSection(mutex->lock);
79 return 0; 102 return 0;
80} 103}
81 104
diff --git a/include/compat/sys/_null.h b/include/compat/sys/_null.h
new file mode 100644
index 0000000..5d15401
--- /dev/null
+++ b/include/compat/sys/_null.h
@@ -0,0 +1,18 @@
1/* $OpenBSD: _null.h,v 1.2 2016/09/09 22:07:58 millert Exp $ */
2
3/*
4 * Written by Todd C. Miller, September 9, 2016
5 * Public domain.
6 */
7
8#ifndef NULL
9#if !defined(__cplusplus)
10#define NULL ((void *)0)
11#elif __cplusplus >= 201103L
12#define NULL nullptr
13#elif defined(__GNUG__)
14#define NULL __null
15#else
16#define NULL 0L
17#endif
18#endif
diff --git a/include/compat/sys/queue.h b/include/compat/sys/queue.h
new file mode 100644
index 0000000..f28ba89
--- /dev/null
+++ b/include/compat/sys/queue.h
@@ -0,0 +1,536 @@
1/* $OpenBSD: queue.h,v 1.45 2018/07/12 14:22:54 sashan Exp $ */
2/* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */
3
4/*
5 * Copyright (c) 1991, 1993
6 * The Regents of the University of California. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in the
15 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of the University nor the names of its contributors
17 * may be used to endorse or promote products derived from this software
18 * without specific prior written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
21 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
24 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
25 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
26 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
27 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
28 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
29 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
30 * SUCH DAMAGE.
31 *
32 * @(#)queue.h 8.5 (Berkeley) 8/20/94
33 */
34
35#ifndef _SYS_QUEUE_H_
36#define _SYS_QUEUE_H_
37
38#include <sys/_null.h>
39
40/*
41 * This file defines five types of data structures: singly-linked lists,
42 * lists, simple queues, tail queues and XOR simple queues.
43 *
44 *
45 * A singly-linked list is headed by a single forward pointer. The elements
46 * are singly linked for minimum space and pointer manipulation overhead at
47 * the expense of O(n) removal for arbitrary elements. New elements can be
48 * added to the list after an existing element or at the head of the list.
49 * Elements being removed from the head of the list should use the explicit
50 * macro for this purpose for optimum efficiency. A singly-linked list may
51 * only be traversed in the forward direction. Singly-linked lists are ideal
52 * for applications with large datasets and few or no removals or for
53 * implementing a LIFO queue.
54 *
55 * A list is headed by a single forward pointer (or an array of forward
56 * pointers for a hash table header). The elements are doubly linked
57 * so that an arbitrary element can be removed without a need to
58 * traverse the list. New elements can be added to the list before
59 * or after an existing element or at the head of the list. A list
60 * may only be traversed in the forward direction.
61 *
62 * A simple queue is headed by a pair of pointers, one to the head of the
63 * list and the other to the tail of the list. The elements are singly
64 * linked to save space, so elements can only be removed from the
65 * head of the list. New elements can be added to the list before or after
66 * an existing element, at the head of the list, or at the end of the
67 * list. A simple queue may only be traversed in the forward direction.
68 *
69 * A tail queue is headed by a pair of pointers, one to the head of the
70 * list and the other to the tail of the list. The elements are doubly
71 * linked so that an arbitrary element can be removed without a need to
72 * traverse the list. New elements can be added to the list before or
73 * after an existing element, at the head of the list, or at the end of
74 * the list. A tail queue may be traversed in either direction.
75 *
76 * An XOR simple queue is used in the same way as a regular simple queue.
77 * The difference is that the head structure also includes a "cookie" that
78 * is XOR'd with the queue pointer (first, last or next) to generate the
79 * real pointer value.
80 *
81 * For details on the use of these macros, see the queue(3) manual page.
82 */
83
84#if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC))
85#define _Q_INVALID ((void *)-1)
86#define _Q_INVALIDATE(a) (a) = _Q_INVALID
87#else
88#define _Q_INVALIDATE(a)
89#endif
90
91/*
92 * Singly-linked List definitions.
93 */
94#define SLIST_HEAD(name, type) \
95struct name { \
96 struct type *slh_first; /* first element */ \
97}
98
99#define SLIST_HEAD_INITIALIZER(head) \
100 { NULL }
101
102#define SLIST_ENTRY(type) \
103struct { \
104 struct type *sle_next; /* next element */ \
105}
106
107/*
108 * Singly-linked List access methods.
109 */
110#define SLIST_FIRST(head) ((head)->slh_first)
111#define SLIST_END(head) NULL
112#define SLIST_EMPTY(head) (SLIST_FIRST(head) == SLIST_END(head))
113#define SLIST_NEXT(elm, field) ((elm)->field.sle_next)
114
115#define SLIST_FOREACH(var, head, field) \
116 for((var) = SLIST_FIRST(head); \
117 (var) != SLIST_END(head); \
118 (var) = SLIST_NEXT(var, field))
119
120#define SLIST_FOREACH_SAFE(var, head, field, tvar) \
121 for ((var) = SLIST_FIRST(head); \
122 (var) && ((tvar) = SLIST_NEXT(var, field), 1); \
123 (var) = (tvar))
124
125/*
126 * Singly-linked List functions.
127 */
128#define SLIST_INIT(head) { \
129 SLIST_FIRST(head) = SLIST_END(head); \
130}
131
132#define SLIST_INSERT_AFTER(slistelm, elm, field) do { \
133 (elm)->field.sle_next = (slistelm)->field.sle_next; \
134 (slistelm)->field.sle_next = (elm); \
135} while (0)
136
137#define SLIST_INSERT_HEAD(head, elm, field) do { \
138 (elm)->field.sle_next = (head)->slh_first; \
139 (head)->slh_first = (elm); \
140} while (0)
141
142#define SLIST_REMOVE_AFTER(elm, field) do { \
143 (elm)->field.sle_next = (elm)->field.sle_next->field.sle_next; \
144} while (0)
145
146#define SLIST_REMOVE_HEAD(head, field) do { \
147 (head)->slh_first = (head)->slh_first->field.sle_next; \
148} while (0)
149
150#define SLIST_REMOVE(head, elm, type, field) do { \
151 if ((head)->slh_first == (elm)) { \
152 SLIST_REMOVE_HEAD((head), field); \
153 } else { \
154 struct type *curelm = (head)->slh_first; \
155 \
156 while (curelm->field.sle_next != (elm)) \
157 curelm = curelm->field.sle_next; \
158 curelm->field.sle_next = \
159 curelm->field.sle_next->field.sle_next; \
160 } \
161 _Q_INVALIDATE((elm)->field.sle_next); \
162} while (0)
163
164/*
165 * List definitions.
166 */
167#define LIST_HEAD(name, type) \
168struct name { \
169 struct type *lh_first; /* first element */ \
170}
171
172#define LIST_HEAD_INITIALIZER(head) \
173 { NULL }
174
175#define LIST_ENTRY(type) \
176struct { \
177 struct type *le_next; /* next element */ \
178 struct type **le_prev; /* address of previous next element */ \
179}
180
181/*
182 * List access methods.
183 */
184#define LIST_FIRST(head) ((head)->lh_first)
185#define LIST_END(head) NULL
186#define LIST_EMPTY(head) (LIST_FIRST(head) == LIST_END(head))
187#define LIST_NEXT(elm, field) ((elm)->field.le_next)
188
189#define LIST_FOREACH(var, head, field) \
190 for((var) = LIST_FIRST(head); \
191 (var)!= LIST_END(head); \
192 (var) = LIST_NEXT(var, field))
193
194#define LIST_FOREACH_SAFE(var, head, field, tvar) \
195 for ((var) = LIST_FIRST(head); \
196 (var) && ((tvar) = LIST_NEXT(var, field), 1); \
197 (var) = (tvar))
198
199/*
200 * List functions.
201 */
202#define LIST_INIT(head) do { \
203 LIST_FIRST(head) = LIST_END(head); \
204} while (0)
205
206#define LIST_INSERT_AFTER(listelm, elm, field) do { \
207 if (((elm)->field.le_next = (listelm)->field.le_next) != NULL) \
208 (listelm)->field.le_next->field.le_prev = \
209 &(elm)->field.le_next; \
210 (listelm)->field.le_next = (elm); \
211 (elm)->field.le_prev = &(listelm)->field.le_next; \
212} while (0)
213
214#define LIST_INSERT_BEFORE(listelm, elm, field) do { \
215 (elm)->field.le_prev = (listelm)->field.le_prev; \
216 (elm)->field.le_next = (listelm); \
217 *(listelm)->field.le_prev = (elm); \
218 (listelm)->field.le_prev = &(elm)->field.le_next; \
219} while (0)
220
221#define LIST_INSERT_HEAD(head, elm, field) do { \
222 if (((elm)->field.le_next = (head)->lh_first) != NULL) \
223 (head)->lh_first->field.le_prev = &(elm)->field.le_next;\
224 (head)->lh_first = (elm); \
225 (elm)->field.le_prev = &(head)->lh_first; \
226} while (0)
227
228#define LIST_REMOVE(elm, field) do { \
229 if ((elm)->field.le_next != NULL) \
230 (elm)->field.le_next->field.le_prev = \
231 (elm)->field.le_prev; \
232 *(elm)->field.le_prev = (elm)->field.le_next; \
233 _Q_INVALIDATE((elm)->field.le_prev); \
234 _Q_INVALIDATE((elm)->field.le_next); \
235} while (0)
236
237#define LIST_REPLACE(elm, elm2, field) do { \
238 if (((elm2)->field.le_next = (elm)->field.le_next) != NULL) \
239 (elm2)->field.le_next->field.le_prev = \
240 &(elm2)->field.le_next; \
241 (elm2)->field.le_prev = (elm)->field.le_prev; \
242 *(elm2)->field.le_prev = (elm2); \
243 _Q_INVALIDATE((elm)->field.le_prev); \
244 _Q_INVALIDATE((elm)->field.le_next); \
245} while (0)
246
247/*
248 * Simple queue definitions.
249 */
250#define SIMPLEQ_HEAD(name, type) \
251struct name { \
252 struct type *sqh_first; /* first element */ \
253 struct type **sqh_last; /* addr of last next element */ \
254}
255
256#define SIMPLEQ_HEAD_INITIALIZER(head) \
257 { NULL, &(head).sqh_first }
258
259#define SIMPLEQ_ENTRY(type) \
260struct { \
261 struct type *sqe_next; /* next element */ \
262}
263
264/*
265 * Simple queue access methods.
266 */
267#define SIMPLEQ_FIRST(head) ((head)->sqh_first)
268#define SIMPLEQ_END(head) NULL
269#define SIMPLEQ_EMPTY(head) (SIMPLEQ_FIRST(head) == SIMPLEQ_END(head))
270#define SIMPLEQ_NEXT(elm, field) ((elm)->field.sqe_next)
271
272#define SIMPLEQ_FOREACH(var, head, field) \
273 for((var) = SIMPLEQ_FIRST(head); \
274 (var) != SIMPLEQ_END(head); \
275 (var) = SIMPLEQ_NEXT(var, field))
276
277#define SIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
278 for ((var) = SIMPLEQ_FIRST(head); \
279 (var) && ((tvar) = SIMPLEQ_NEXT(var, field), 1); \
280 (var) = (tvar))
281
282/*
283 * Simple queue functions.
284 */
285#define SIMPLEQ_INIT(head) do { \
286 (head)->sqh_first = NULL; \
287 (head)->sqh_last = &(head)->sqh_first; \
288} while (0)
289
290#define SIMPLEQ_INSERT_HEAD(head, elm, field) do { \
291 if (((elm)->field.sqe_next = (head)->sqh_first) == NULL) \
292 (head)->sqh_last = &(elm)->field.sqe_next; \
293 (head)->sqh_first = (elm); \
294} while (0)
295
296#define SIMPLEQ_INSERT_TAIL(head, elm, field) do { \
297 (elm)->field.sqe_next = NULL; \
298 *(head)->sqh_last = (elm); \
299 (head)->sqh_last = &(elm)->field.sqe_next; \
300} while (0)
301
302#define SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
303 if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)\
304 (head)->sqh_last = &(elm)->field.sqe_next; \
305 (listelm)->field.sqe_next = (elm); \
306} while (0)
307
308#define SIMPLEQ_REMOVE_HEAD(head, field) do { \
309 if (((head)->sqh_first = (head)->sqh_first->field.sqe_next) == NULL) \
310 (head)->sqh_last = &(head)->sqh_first; \
311} while (0)
312
313#define SIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
314 if (((elm)->field.sqe_next = (elm)->field.sqe_next->field.sqe_next) \
315 == NULL) \
316 (head)->sqh_last = &(elm)->field.sqe_next; \
317} while (0)
318
319#define SIMPLEQ_CONCAT(head1, head2) do { \
320 if (!SIMPLEQ_EMPTY((head2))) { \
321 *(head1)->sqh_last = (head2)->sqh_first; \
322 (head1)->sqh_last = (head2)->sqh_last; \
323 SIMPLEQ_INIT((head2)); \
324 } \
325} while (0)
326
327/*
328 * XOR Simple queue definitions.
329 */
330#define XSIMPLEQ_HEAD(name, type) \
331struct name { \
332 struct type *sqx_first; /* first element */ \
333 struct type **sqx_last; /* addr of last next element */ \
334 unsigned long sqx_cookie; \
335}
336
337#define XSIMPLEQ_ENTRY(type) \
338struct { \
339 struct type *sqx_next; /* next element */ \
340}
341
342/*
343 * XOR Simple queue access methods.
344 */
345#define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \
346 (unsigned long)(ptr)))
347#define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first))
348#define XSIMPLEQ_END(head) NULL
349#define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head))
350#define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next))
351
352
353#define XSIMPLEQ_FOREACH(var, head, field) \
354 for ((var) = XSIMPLEQ_FIRST(head); \
355 (var) != XSIMPLEQ_END(head); \
356 (var) = XSIMPLEQ_NEXT(head, var, field))
357
358#define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \
359 for ((var) = XSIMPLEQ_FIRST(head); \
360 (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \
361 (var) = (tvar))
362
363/*
364 * XOR Simple queue functions.
365 */
366#define XSIMPLEQ_INIT(head) do { \
367 arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \
368 (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \
369 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
370} while (0)
371
372#define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \
373 if (((elm)->field.sqx_next = (head)->sqx_first) == \
374 XSIMPLEQ_XOR(head, NULL)) \
375 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
376 (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \
377} while (0)
378
379#define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \
380 (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \
381 *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \
382 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
383} while (0)
384
385#define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \
386 if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \
387 XSIMPLEQ_XOR(head, NULL)) \
388 (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
389 (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \
390} while (0)
391
392#define XSIMPLEQ_REMOVE_HEAD(head, field) do { \
393 if (((head)->sqx_first = XSIMPLEQ_XOR(head, \
394 (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \
395 (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \
396} while (0)
397
398#define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \
399 if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \
400 (elm)->field.sqx_next)->field.sqx_next) \
401 == XSIMPLEQ_XOR(head, NULL)) \
402 (head)->sqx_last = \
403 XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \
404} while (0)
405
406
407/*
408 * Tail queue definitions.
409 */
410#define TAILQ_HEAD(name, type) \
411struct name { \
412 struct type *tqh_first; /* first element */ \
413 struct type **tqh_last; /* addr of last next element */ \
414}
415
416#define TAILQ_HEAD_INITIALIZER(head) \
417 { NULL, &(head).tqh_first }
418
419#define TAILQ_ENTRY(type) \
420struct { \
421 struct type *tqe_next; /* next element */ \
422 struct type **tqe_prev; /* address of previous next element */ \
423}
424
425/*
426 * Tail queue access methods.
427 */
428#define TAILQ_FIRST(head) ((head)->tqh_first)
429#define TAILQ_END(head) NULL
430#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
431#define TAILQ_LAST(head, headname) \
432 (*(((struct headname *)((head)->tqh_last))->tqh_last))
433/* XXX */
434#define TAILQ_PREV(elm, headname, field) \
435 (*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
436#define TAILQ_EMPTY(head) \
437 (TAILQ_FIRST(head) == TAILQ_END(head))
438
439#define TAILQ_FOREACH(var, head, field) \
440 for((var) = TAILQ_FIRST(head); \
441 (var) != TAILQ_END(head); \
442 (var) = TAILQ_NEXT(var, field))
443
444#define TAILQ_FOREACH_SAFE(var, head, field, tvar) \
445 for ((var) = TAILQ_FIRST(head); \
446 (var) != TAILQ_END(head) && \
447 ((tvar) = TAILQ_NEXT(var, field), 1); \
448 (var) = (tvar))
449
450
451#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
452 for((var) = TAILQ_LAST(head, headname); \
453 (var) != TAILQ_END(head); \
454 (var) = TAILQ_PREV(var, headname, field))
455
456#define TAILQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \
457 for ((var) = TAILQ_LAST(head, headname); \
458 (var) != TAILQ_END(head) && \
459 ((tvar) = TAILQ_PREV(var, headname, field), 1); \
460 (var) = (tvar))
461
462/*
463 * Tail queue functions.
464 */
465#define TAILQ_INIT(head) do { \
466 (head)->tqh_first = NULL; \
467 (head)->tqh_last = &(head)->tqh_first; \
468} while (0)
469
470#define TAILQ_INSERT_HEAD(head, elm, field) do { \
471 if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
472 (head)->tqh_first->field.tqe_prev = \
473 &(elm)->field.tqe_next; \
474 else \
475 (head)->tqh_last = &(elm)->field.tqe_next; \
476 (head)->tqh_first = (elm); \
477 (elm)->field.tqe_prev = &(head)->tqh_first; \
478} while (0)
479
480#define TAILQ_INSERT_TAIL(head, elm, field) do { \
481 (elm)->field.tqe_next = NULL; \
482 (elm)->field.tqe_prev = (head)->tqh_last; \
483 *(head)->tqh_last = (elm); \
484 (head)->tqh_last = &(elm)->field.tqe_next; \
485} while (0)
486
487#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
488 if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
489 (elm)->field.tqe_next->field.tqe_prev = \
490 &(elm)->field.tqe_next; \
491 else \
492 (head)->tqh_last = &(elm)->field.tqe_next; \
493 (listelm)->field.tqe_next = (elm); \
494 (elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
495} while (0)
496
497#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
498 (elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
499 (elm)->field.tqe_next = (listelm); \
500 *(listelm)->field.tqe_prev = (elm); \
501 (listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
502} while (0)
503
504#define TAILQ_REMOVE(head, elm, field) do { \
505 if (((elm)->field.tqe_next) != NULL) \
506 (elm)->field.tqe_next->field.tqe_prev = \
507 (elm)->field.tqe_prev; \
508 else \
509 (head)->tqh_last = (elm)->field.tqe_prev; \
510 *(elm)->field.tqe_prev = (elm)->field.tqe_next; \
511 _Q_INVALIDATE((elm)->field.tqe_prev); \
512 _Q_INVALIDATE((elm)->field.tqe_next); \
513} while (0)
514
515#define TAILQ_REPLACE(head, elm, elm2, field) do { \
516 if (((elm2)->field.tqe_next = (elm)->field.tqe_next) != NULL) \
517 (elm2)->field.tqe_next->field.tqe_prev = \
518 &(elm2)->field.tqe_next; \
519 else \
520 (head)->tqh_last = &(elm2)->field.tqe_next; \
521 (elm2)->field.tqe_prev = (elm)->field.tqe_prev; \
522 *(elm2)->field.tqe_prev = (elm2); \
523 _Q_INVALIDATE((elm)->field.tqe_prev); \
524 _Q_INVALIDATE((elm)->field.tqe_next); \
525} while (0)
526
527#define TAILQ_CONCAT(head1, head2, field) do { \
528 if (!TAILQ_EMPTY(head2)) { \
529 *(head1)->tqh_last = (head2)->tqh_first; \
530 (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
531 (head1)->tqh_last = (head2)->tqh_last; \
532 TAILQ_INIT((head2)); \
533 } \
534} while (0)
535
536#endif /* !_SYS_QUEUE_H_ */
diff --git a/include/compat/sys/tree.h b/include/compat/sys/tree.h
new file mode 100644
index 0000000..ffcac90
--- /dev/null
+++ b/include/compat/sys/tree.h
@@ -0,0 +1,1006 @@
1/* $OpenBSD: tree.h,v 1.29 2017/07/30 19:27:20 deraadt Exp $ */
2/*
3 * Copyright 2002 Niels Provos <provos@citi.umich.edu>
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#ifndef _SYS_TREE_H_
28#define _SYS_TREE_H_
29
30#include <sys/_null.h>
31
32/*
33 * This file defines data structures for different types of trees:
34 * splay trees and red-black trees.
35 *
36 * A splay tree is a self-organizing data structure. Every operation
37 * on the tree causes a splay to happen. The splay moves the requested
38 * node to the root of the tree and partly rebalances it.
39 *
40 * This has the benefit that request locality causes faster lookups as
41 * the requested nodes move to the top of the tree. On the other hand,
42 * every lookup causes memory writes.
43 *
44 * The Balance Theorem bounds the total access time for m operations
45 * and n inserts on an initially empty tree as O((m + n)lg n). The
46 * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
47 *
48 * A red-black tree is a binary search tree with the node color as an
49 * extra attribute. It fulfills a set of conditions:
50 * - every search path from the root to a leaf consists of the
51 * same number of black nodes,
52 * - each red node (except for the root) has a black parent,
53 * - each leaf node is black.
54 *
55 * Every operation on a red-black tree is bounded as O(lg n).
56 * The maximum height of a red-black tree is 2lg (n+1).
57 */
58
59#define SPLAY_HEAD(name, type) \
60struct name { \
61 struct type *sph_root; /* root of the tree */ \
62}
63
64#define SPLAY_INITIALIZER(root) \
65 { NULL }
66
67#define SPLAY_INIT(root) do { \
68 (root)->sph_root = NULL; \
69} while (0)
70
71#define SPLAY_ENTRY(type) \
72struct { \
73 struct type *spe_left; /* left element */ \
74 struct type *spe_right; /* right element */ \
75}
76
77#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
78#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
79#define SPLAY_ROOT(head) (head)->sph_root
80#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
81
82/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
83#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
84 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
85 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
86 (head)->sph_root = tmp; \
87} while (0)
88
89#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
90 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
91 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
92 (head)->sph_root = tmp; \
93} while (0)
94
95#define SPLAY_LINKLEFT(head, tmp, field) do { \
96 SPLAY_LEFT(tmp, field) = (head)->sph_root; \
97 tmp = (head)->sph_root; \
98 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
99} while (0)
100
101#define SPLAY_LINKRIGHT(head, tmp, field) do { \
102 SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
103 tmp = (head)->sph_root; \
104 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
105} while (0)
106
107#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
108 SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
109 SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
110 SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
111 SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
112} while (0)
113
114/* Generates prototypes and inline functions */
115
116#define SPLAY_PROTOTYPE(name, type, field, cmp) \
117void name##_SPLAY(struct name *, struct type *); \
118void name##_SPLAY_MINMAX(struct name *, int); \
119struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
120struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
121 \
122/* Finds the node with the same key as elm */ \
123static __unused __inline struct type * \
124name##_SPLAY_FIND(struct name *head, struct type *elm) \
125{ \
126 if (SPLAY_EMPTY(head)) \
127 return(NULL); \
128 name##_SPLAY(head, elm); \
129 if ((cmp)(elm, (head)->sph_root) == 0) \
130 return (head->sph_root); \
131 return (NULL); \
132} \
133 \
134static __unused __inline struct type * \
135name##_SPLAY_NEXT(struct name *head, struct type *elm) \
136{ \
137 name##_SPLAY(head, elm); \
138 if (SPLAY_RIGHT(elm, field) != NULL) { \
139 elm = SPLAY_RIGHT(elm, field); \
140 while (SPLAY_LEFT(elm, field) != NULL) { \
141 elm = SPLAY_LEFT(elm, field); \
142 } \
143 } else \
144 elm = NULL; \
145 return (elm); \
146} \
147 \
148static __unused __inline struct type * \
149name##_SPLAY_MIN_MAX(struct name *head, int val) \
150{ \
151 name##_SPLAY_MINMAX(head, val); \
152 return (SPLAY_ROOT(head)); \
153}
154
155/* Main splay operation.
156 * Moves node close to the key of elm to top
157 */
158#define SPLAY_GENERATE(name, type, field, cmp) \
159struct type * \
160name##_SPLAY_INSERT(struct name *head, struct type *elm) \
161{ \
162 if (SPLAY_EMPTY(head)) { \
163 SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
164 } else { \
165 int __comp; \
166 name##_SPLAY(head, elm); \
167 __comp = (cmp)(elm, (head)->sph_root); \
168 if(__comp < 0) { \
169 SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
170 SPLAY_RIGHT(elm, field) = (head)->sph_root; \
171 SPLAY_LEFT((head)->sph_root, field) = NULL; \
172 } else if (__comp > 0) { \
173 SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
174 SPLAY_LEFT(elm, field) = (head)->sph_root; \
175 SPLAY_RIGHT((head)->sph_root, field) = NULL; \
176 } else \
177 return ((head)->sph_root); \
178 } \
179 (head)->sph_root = (elm); \
180 return (NULL); \
181} \
182 \
183struct type * \
184name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
185{ \
186 struct type *__tmp; \
187 if (SPLAY_EMPTY(head)) \
188 return (NULL); \
189 name##_SPLAY(head, elm); \
190 if ((cmp)(elm, (head)->sph_root) == 0) { \
191 if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
192 (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
193 } else { \
194 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
195 (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
196 name##_SPLAY(head, elm); \
197 SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
198 } \
199 return (elm); \
200 } \
201 return (NULL); \
202} \
203 \
204void \
205name##_SPLAY(struct name *head, struct type *elm) \
206{ \
207 struct type __node, *__left, *__right, *__tmp; \
208 int __comp; \
209\
210 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
211 __left = __right = &__node; \
212\
213 while ((__comp = (cmp)(elm, (head)->sph_root))) { \
214 if (__comp < 0) { \
215 __tmp = SPLAY_LEFT((head)->sph_root, field); \
216 if (__tmp == NULL) \
217 break; \
218 if ((cmp)(elm, __tmp) < 0){ \
219 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
220 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
221 break; \
222 } \
223 SPLAY_LINKLEFT(head, __right, field); \
224 } else if (__comp > 0) { \
225 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
226 if (__tmp == NULL) \
227 break; \
228 if ((cmp)(elm, __tmp) > 0){ \
229 SPLAY_ROTATE_LEFT(head, __tmp, field); \
230 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
231 break; \
232 } \
233 SPLAY_LINKRIGHT(head, __left, field); \
234 } \
235 } \
236 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
237} \
238 \
239/* Splay with either the minimum or the maximum element \
240 * Used to find minimum or maximum element in tree. \
241 */ \
242void name##_SPLAY_MINMAX(struct name *head, int __comp) \
243{ \
244 struct type __node, *__left, *__right, *__tmp; \
245\
246 SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
247 __left = __right = &__node; \
248\
249 while (1) { \
250 if (__comp < 0) { \
251 __tmp = SPLAY_LEFT((head)->sph_root, field); \
252 if (__tmp == NULL) \
253 break; \
254 if (__comp < 0){ \
255 SPLAY_ROTATE_RIGHT(head, __tmp, field); \
256 if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
257 break; \
258 } \
259 SPLAY_LINKLEFT(head, __right, field); \
260 } else if (__comp > 0) { \
261 __tmp = SPLAY_RIGHT((head)->sph_root, field); \
262 if (__tmp == NULL) \
263 break; \
264 if (__comp > 0) { \
265 SPLAY_ROTATE_LEFT(head, __tmp, field); \
266 if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
267 break; \
268 } \
269 SPLAY_LINKRIGHT(head, __left, field); \
270 } \
271 } \
272 SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
273}
274
275#define SPLAY_NEGINF -1
276#define SPLAY_INF 1
277
278#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
279#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
280#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
281#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
282#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
283 : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
284#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
285 : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
286
287#define SPLAY_FOREACH(x, name, head) \
288 for ((x) = SPLAY_MIN(name, head); \
289 (x) != NULL; \
290 (x) = SPLAY_NEXT(name, head, x))
291
292/* Macros that define a red-black tree */
293#define RB_HEAD(name, type) \
294struct name { \
295 struct type *rbh_root; /* root of the tree */ \
296}
297
298#define RB_INITIALIZER(root) \
299 { NULL }
300
301#define RB_INIT(root) do { \
302 (root)->rbh_root = NULL; \
303} while (0)
304
305#define RB_BLACK 0
306#define RB_RED 1
307#define RB_ENTRY(type) \
308struct { \
309 struct type *rbe_left; /* left element */ \
310 struct type *rbe_right; /* right element */ \
311 struct type *rbe_parent; /* parent element */ \
312 int rbe_color; /* node color */ \
313}
314
315#define RB_LEFT(elm, field) (elm)->field.rbe_left
316#define RB_RIGHT(elm, field) (elm)->field.rbe_right
317#define RB_PARENT(elm, field) (elm)->field.rbe_parent
318#define RB_COLOR(elm, field) (elm)->field.rbe_color
319#define RB_ROOT(head) (head)->rbh_root
320#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
321
322#define RB_SET(elm, parent, field) do { \
323 RB_PARENT(elm, field) = parent; \
324 RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
325 RB_COLOR(elm, field) = RB_RED; \
326} while (0)
327
328#define RB_SET_BLACKRED(black, red, field) do { \
329 RB_COLOR(black, field) = RB_BLACK; \
330 RB_COLOR(red, field) = RB_RED; \
331} while (0)
332
333#ifndef RB_AUGMENT
334#define RB_AUGMENT(x) do {} while (0)
335#endif
336
337#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
338 (tmp) = RB_RIGHT(elm, field); \
339 if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
340 RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
341 } \
342 RB_AUGMENT(elm); \
343 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
344 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
345 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
346 else \
347 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
348 } else \
349 (head)->rbh_root = (tmp); \
350 RB_LEFT(tmp, field) = (elm); \
351 RB_PARENT(elm, field) = (tmp); \
352 RB_AUGMENT(tmp); \
353 if ((RB_PARENT(tmp, field))) \
354 RB_AUGMENT(RB_PARENT(tmp, field)); \
355} while (0)
356
357#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
358 (tmp) = RB_LEFT(elm, field); \
359 if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
360 RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
361 } \
362 RB_AUGMENT(elm); \
363 if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
364 if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
365 RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
366 else \
367 RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
368 } else \
369 (head)->rbh_root = (tmp); \
370 RB_RIGHT(tmp, field) = (elm); \
371 RB_PARENT(elm, field) = (tmp); \
372 RB_AUGMENT(tmp); \
373 if ((RB_PARENT(tmp, field))) \
374 RB_AUGMENT(RB_PARENT(tmp, field)); \
375} while (0)
376
377/* Generates prototypes and inline functions */
378#define RB_PROTOTYPE(name, type, field, cmp) \
379 RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
380#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
381 RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
382#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
383attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
384attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
385attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
386attr struct type *name##_RB_INSERT(struct name *, struct type *); \
387attr struct type *name##_RB_FIND(struct name *, struct type *); \
388attr struct type *name##_RB_NFIND(struct name *, struct type *); \
389attr struct type *name##_RB_NEXT(struct type *); \
390attr struct type *name##_RB_PREV(struct type *); \
391attr struct type *name##_RB_MINMAX(struct name *, int); \
392 \
393
394/* Main rb operation.
395 * Moves node close to the key of elm to top
396 */
397#define RB_GENERATE(name, type, field, cmp) \
398 RB_GENERATE_INTERNAL(name, type, field, cmp,)
399#define RB_GENERATE_STATIC(name, type, field, cmp) \
400 RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
401#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
402attr void \
403name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
404{ \
405 struct type *parent, *gparent, *tmp; \
406 while ((parent = RB_PARENT(elm, field)) && \
407 RB_COLOR(parent, field) == RB_RED) { \
408 gparent = RB_PARENT(parent, field); \
409 if (parent == RB_LEFT(gparent, field)) { \
410 tmp = RB_RIGHT(gparent, field); \
411 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
412 RB_COLOR(tmp, field) = RB_BLACK; \
413 RB_SET_BLACKRED(parent, gparent, field);\
414 elm = gparent; \
415 continue; \
416 } \
417 if (RB_RIGHT(parent, field) == elm) { \
418 RB_ROTATE_LEFT(head, parent, tmp, field);\
419 tmp = parent; \
420 parent = elm; \
421 elm = tmp; \
422 } \
423 RB_SET_BLACKRED(parent, gparent, field); \
424 RB_ROTATE_RIGHT(head, gparent, tmp, field); \
425 } else { \
426 tmp = RB_LEFT(gparent, field); \
427 if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
428 RB_COLOR(tmp, field) = RB_BLACK; \
429 RB_SET_BLACKRED(parent, gparent, field);\
430 elm = gparent; \
431 continue; \
432 } \
433 if (RB_LEFT(parent, field) == elm) { \
434 RB_ROTATE_RIGHT(head, parent, tmp, field);\
435 tmp = parent; \
436 parent = elm; \
437 elm = tmp; \
438 } \
439 RB_SET_BLACKRED(parent, gparent, field); \
440 RB_ROTATE_LEFT(head, gparent, tmp, field); \
441 } \
442 } \
443 RB_COLOR(head->rbh_root, field) = RB_BLACK; \
444} \
445 \
446attr void \
447name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
448{ \
449 struct type *tmp; \
450 while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
451 elm != RB_ROOT(head)) { \
452 if (RB_LEFT(parent, field) == elm) { \
453 tmp = RB_RIGHT(parent, field); \
454 if (RB_COLOR(tmp, field) == RB_RED) { \
455 RB_SET_BLACKRED(tmp, parent, field); \
456 RB_ROTATE_LEFT(head, parent, tmp, field);\
457 tmp = RB_RIGHT(parent, field); \
458 } \
459 if ((RB_LEFT(tmp, field) == NULL || \
460 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
461 (RB_RIGHT(tmp, field) == NULL || \
462 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
463 RB_COLOR(tmp, field) = RB_RED; \
464 elm = parent; \
465 parent = RB_PARENT(elm, field); \
466 } else { \
467 if (RB_RIGHT(tmp, field) == NULL || \
468 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
469 struct type *oleft; \
470 if ((oleft = RB_LEFT(tmp, field)))\
471 RB_COLOR(oleft, field) = RB_BLACK;\
472 RB_COLOR(tmp, field) = RB_RED; \
473 RB_ROTATE_RIGHT(head, tmp, oleft, field);\
474 tmp = RB_RIGHT(parent, field); \
475 } \
476 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
477 RB_COLOR(parent, field) = RB_BLACK; \
478 if (RB_RIGHT(tmp, field)) \
479 RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
480 RB_ROTATE_LEFT(head, parent, tmp, field);\
481 elm = RB_ROOT(head); \
482 break; \
483 } \
484 } else { \
485 tmp = RB_LEFT(parent, field); \
486 if (RB_COLOR(tmp, field) == RB_RED) { \
487 RB_SET_BLACKRED(tmp, parent, field); \
488 RB_ROTATE_RIGHT(head, parent, tmp, field);\
489 tmp = RB_LEFT(parent, field); \
490 } \
491 if ((RB_LEFT(tmp, field) == NULL || \
492 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
493 (RB_RIGHT(tmp, field) == NULL || \
494 RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
495 RB_COLOR(tmp, field) = RB_RED; \
496 elm = parent; \
497 parent = RB_PARENT(elm, field); \
498 } else { \
499 if (RB_LEFT(tmp, field) == NULL || \
500 RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
501 struct type *oright; \
502 if ((oright = RB_RIGHT(tmp, field)))\
503 RB_COLOR(oright, field) = RB_BLACK;\
504 RB_COLOR(tmp, field) = RB_RED; \
505 RB_ROTATE_LEFT(head, tmp, oright, field);\
506 tmp = RB_LEFT(parent, field); \
507 } \
508 RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
509 RB_COLOR(parent, field) = RB_BLACK; \
510 if (RB_LEFT(tmp, field)) \
511 RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
512 RB_ROTATE_RIGHT(head, parent, tmp, field);\
513 elm = RB_ROOT(head); \
514 break; \
515 } \
516 } \
517 } \
518 if (elm) \
519 RB_COLOR(elm, field) = RB_BLACK; \
520} \
521 \
522attr struct type * \
523name##_RB_REMOVE(struct name *head, struct type *elm) \
524{ \
525 struct type *child, *parent, *old = elm; \
526 int color; \
527 if (RB_LEFT(elm, field) == NULL) \
528 child = RB_RIGHT(elm, field); \
529 else if (RB_RIGHT(elm, field) == NULL) \
530 child = RB_LEFT(elm, field); \
531 else { \
532 struct type *left; \
533 elm = RB_RIGHT(elm, field); \
534 while ((left = RB_LEFT(elm, field))) \
535 elm = left; \
536 child = RB_RIGHT(elm, field); \
537 parent = RB_PARENT(elm, field); \
538 color = RB_COLOR(elm, field); \
539 if (child) \
540 RB_PARENT(child, field) = parent; \
541 if (parent) { \
542 if (RB_LEFT(parent, field) == elm) \
543 RB_LEFT(parent, field) = child; \
544 else \
545 RB_RIGHT(parent, field) = child; \
546 RB_AUGMENT(parent); \
547 } else \
548 RB_ROOT(head) = child; \
549 if (RB_PARENT(elm, field) == old) \
550 parent = elm; \
551 (elm)->field = (old)->field; \
552 if (RB_PARENT(old, field)) { \
553 if (RB_LEFT(RB_PARENT(old, field), field) == old)\
554 RB_LEFT(RB_PARENT(old, field), field) = elm;\
555 else \
556 RB_RIGHT(RB_PARENT(old, field), field) = elm;\
557 RB_AUGMENT(RB_PARENT(old, field)); \
558 } else \
559 RB_ROOT(head) = elm; \
560 RB_PARENT(RB_LEFT(old, field), field) = elm; \
561 if (RB_RIGHT(old, field)) \
562 RB_PARENT(RB_RIGHT(old, field), field) = elm; \
563 if (parent) { \
564 left = parent; \
565 do { \
566 RB_AUGMENT(left); \
567 } while ((left = RB_PARENT(left, field))); \
568 } \
569 goto color; \
570 } \
571 parent = RB_PARENT(elm, field); \
572 color = RB_COLOR(elm, field); \
573 if (child) \
574 RB_PARENT(child, field) = parent; \
575 if (parent) { \
576 if (RB_LEFT(parent, field) == elm) \
577 RB_LEFT(parent, field) = child; \
578 else \
579 RB_RIGHT(parent, field) = child; \
580 RB_AUGMENT(parent); \
581 } else \
582 RB_ROOT(head) = child; \
583color: \
584 if (color == RB_BLACK) \
585 name##_RB_REMOVE_COLOR(head, parent, child); \
586 return (old); \
587} \
588 \
589/* Inserts a node into the RB tree */ \
590attr struct type * \
591name##_RB_INSERT(struct name *head, struct type *elm) \
592{ \
593 struct type *tmp; \
594 struct type *parent = NULL; \
595 int comp = 0; \
596 tmp = RB_ROOT(head); \
597 while (tmp) { \
598 parent = tmp; \
599 comp = (cmp)(elm, parent); \
600 if (comp < 0) \
601 tmp = RB_LEFT(tmp, field); \
602 else if (comp > 0) \
603 tmp = RB_RIGHT(tmp, field); \
604 else \
605 return (tmp); \
606 } \
607 RB_SET(elm, parent, field); \
608 if (parent != NULL) { \
609 if (comp < 0) \
610 RB_LEFT(parent, field) = elm; \
611 else \
612 RB_RIGHT(parent, field) = elm; \
613 RB_AUGMENT(parent); \
614 } else \
615 RB_ROOT(head) = elm; \
616 name##_RB_INSERT_COLOR(head, elm); \
617 return (NULL); \
618} \
619 \
620/* Finds the node with the same key as elm */ \
621attr struct type * \
622name##_RB_FIND(struct name *head, struct type *elm) \
623{ \
624 struct type *tmp = RB_ROOT(head); \
625 int comp; \
626 while (tmp) { \
627 comp = cmp(elm, tmp); \
628 if (comp < 0) \
629 tmp = RB_LEFT(tmp, field); \
630 else if (comp > 0) \
631 tmp = RB_RIGHT(tmp, field); \
632 else \
633 return (tmp); \
634 } \
635 return (NULL); \
636} \
637 \
638/* Finds the first node greater than or equal to the search key */ \
639attr struct type * \
640name##_RB_NFIND(struct name *head, struct type *elm) \
641{ \
642 struct type *tmp = RB_ROOT(head); \
643 struct type *res = NULL; \
644 int comp; \
645 while (tmp) { \
646 comp = cmp(elm, tmp); \
647 if (comp < 0) { \
648 res = tmp; \
649 tmp = RB_LEFT(tmp, field); \
650 } \
651 else if (comp > 0) \
652 tmp = RB_RIGHT(tmp, field); \
653 else \
654 return (tmp); \
655 } \
656 return (res); \
657} \
658 \
659/* ARGSUSED */ \
660attr struct type * \
661name##_RB_NEXT(struct type *elm) \
662{ \
663 if (RB_RIGHT(elm, field)) { \
664 elm = RB_RIGHT(elm, field); \
665 while (RB_LEFT(elm, field)) \
666 elm = RB_LEFT(elm, field); \
667 } else { \
668 if (RB_PARENT(elm, field) && \
669 (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
670 elm = RB_PARENT(elm, field); \
671 else { \
672 while (RB_PARENT(elm, field) && \
673 (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
674 elm = RB_PARENT(elm, field); \
675 elm = RB_PARENT(elm, field); \
676 } \
677 } \
678 return (elm); \
679} \
680 \
681/* ARGSUSED */ \
682attr struct type * \
683name##_RB_PREV(struct type *elm) \
684{ \
685 if (RB_LEFT(elm, field)) { \
686 elm = RB_LEFT(elm, field); \
687 while (RB_RIGHT(elm, field)) \
688 elm = RB_RIGHT(elm, field); \
689 } else { \
690 if (RB_PARENT(elm, field) && \
691 (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
692 elm = RB_PARENT(elm, field); \
693 else { \
694 while (RB_PARENT(elm, field) && \
695 (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
696 elm = RB_PARENT(elm, field); \
697 elm = RB_PARENT(elm, field); \
698 } \
699 } \
700 return (elm); \
701} \
702 \
703attr struct type * \
704name##_RB_MINMAX(struct name *head, int val) \
705{ \
706 struct type *tmp = RB_ROOT(head); \
707 struct type *parent = NULL; \
708 while (tmp) { \
709 parent = tmp; \
710 if (val < 0) \
711 tmp = RB_LEFT(tmp, field); \
712 else \
713 tmp = RB_RIGHT(tmp, field); \
714 } \
715 return (parent); \
716}
717
718#define RB_NEGINF -1
719#define RB_INF 1
720
721#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
722#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
723#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
724#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
725#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
726#define RB_PREV(name, x, y) name##_RB_PREV(y)
727#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
728#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
729
730#define RB_FOREACH(x, name, head) \
731 for ((x) = RB_MIN(name, head); \
732 (x) != NULL; \
733 (x) = name##_RB_NEXT(x))
734
735#define RB_FOREACH_SAFE(x, name, head, y) \
736 for ((x) = RB_MIN(name, head); \
737 ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
738 (x) = (y))
739
740#define RB_FOREACH_REVERSE(x, name, head) \
741 for ((x) = RB_MAX(name, head); \
742 (x) != NULL; \
743 (x) = name##_RB_PREV(x))
744
745#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
746 for ((x) = RB_MAX(name, head); \
747 ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
748 (x) = (y))
749
750
751/*
752 * Copyright (c) 2016 David Gwynne <dlg@openbsd.org>
753 *
754 * Permission to use, copy, modify, and distribute this software for any
755 * purpose with or without fee is hereby granted, provided that the above
756 * copyright notice and this permission notice appear in all copies.
757 *
758 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
759 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
760 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
761 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
762 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
763 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
764 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
765 */
766
767struct rb_type {
768 int (*t_compare)(const void *, const void *);
769 void (*t_augment)(void *);
770 unsigned int t_offset; /* offset of rb_entry in type */
771};
772
773struct rb_tree {
774 struct rb_entry *rbt_root;
775};
776
777struct rb_entry {
778 struct rb_entry *rbt_parent;
779 struct rb_entry *rbt_left;
780 struct rb_entry *rbt_right;
781 unsigned int rbt_color;
782};
783
784#define RBT_HEAD(_name, _type) \
785struct _name { \
786 struct rb_tree rbh_root; \
787}
788
789#define RBT_ENTRY(_type) struct rb_entry
790
791static inline void
792_rb_init(struct rb_tree *rbt)
793{
794 rbt->rbt_root = NULL;
795}
796
797static inline int
798_rb_empty(struct rb_tree *rbt)
799{
800 return (rbt->rbt_root == NULL);
801}
802
803void *_rb_insert(const struct rb_type *, struct rb_tree *, void *);
804void *_rb_remove(const struct rb_type *, struct rb_tree *, void *);
805void *_rb_find(const struct rb_type *, struct rb_tree *, const void *);
806void *_rb_nfind(const struct rb_type *, struct rb_tree *, const void *);
807void *_rb_root(const struct rb_type *, struct rb_tree *);
808void *_rb_min(const struct rb_type *, struct rb_tree *);
809void *_rb_max(const struct rb_type *, struct rb_tree *);
810void *_rb_next(const struct rb_type *, void *);
811void *_rb_prev(const struct rb_type *, void *);
812void *_rb_left(const struct rb_type *, void *);
813void *_rb_right(const struct rb_type *, void *);
814void *_rb_parent(const struct rb_type *, void *);
815void _rb_set_left(const struct rb_type *, void *, void *);
816void _rb_set_right(const struct rb_type *, void *, void *);
817void _rb_set_parent(const struct rb_type *, void *, void *);
818void _rb_poison(const struct rb_type *, void *, unsigned long);
819int _rb_check(const struct rb_type *, void *, unsigned long);
820
821#define RBT_INITIALIZER(_head) { { NULL } }
822
823#define RBT_PROTOTYPE(_name, _type, _field, _cmp) \
824extern const struct rb_type *const _name##_RBT_TYPE; \
825 \
826__unused static inline void \
827_name##_RBT_INIT(struct _name *head) \
828{ \
829 _rb_init(&head->rbh_root); \
830} \
831 \
832__unused static inline struct _type * \
833_name##_RBT_INSERT(struct _name *head, struct _type *elm) \
834{ \
835 return _rb_insert(_name##_RBT_TYPE, &head->rbh_root, elm); \
836} \
837 \
838__unused static inline struct _type * \
839_name##_RBT_REMOVE(struct _name *head, struct _type *elm) \
840{ \
841 return _rb_remove(_name##_RBT_TYPE, &head->rbh_root, elm); \
842} \
843 \
844__unused static inline struct _type * \
845_name##_RBT_FIND(struct _name *head, const struct _type *key) \
846{ \
847 return _rb_find(_name##_RBT_TYPE, &head->rbh_root, key); \
848} \
849 \
850__unused static inline struct _type * \
851_name##_RBT_NFIND(struct _name *head, const struct _type *key) \
852{ \
853 return _rb_nfind(_name##_RBT_TYPE, &head->rbh_root, key); \
854} \
855 \
856__unused static inline struct _type * \
857_name##_RBT_ROOT(struct _name *head) \
858{ \
859 return _rb_root(_name##_RBT_TYPE, &head->rbh_root); \
860} \
861 \
862__unused static inline int \
863_name##_RBT_EMPTY(struct _name *head) \
864{ \
865 return _rb_empty(&head->rbh_root); \
866} \
867 \
868__unused static inline struct _type * \
869_name##_RBT_MIN(struct _name *head) \
870{ \
871 return _rb_min(_name##_RBT_TYPE, &head->rbh_root); \
872} \
873 \
874__unused static inline struct _type * \
875_name##_RBT_MAX(struct _name *head) \
876{ \
877 return _rb_max(_name##_RBT_TYPE, &head->rbh_root); \
878} \
879 \
880__unused static inline struct _type * \
881_name##_RBT_NEXT(struct _type *elm) \
882{ \
883 return _rb_next(_name##_RBT_TYPE, elm); \
884} \
885 \
886__unused static inline struct _type * \
887_name##_RBT_PREV(struct _type *elm) \
888{ \
889 return _rb_prev(_name##_RBT_TYPE, elm); \
890} \
891 \
892__unused static inline struct _type * \
893_name##_RBT_LEFT(struct _type *elm) \
894{ \
895 return _rb_left(_name##_RBT_TYPE, elm); \
896} \
897 \
898__unused static inline struct _type * \
899_name##_RBT_RIGHT(struct _type *elm) \
900{ \
901 return _rb_right(_name##_RBT_TYPE, elm); \
902} \
903 \
904__unused static inline struct _type * \
905_name##_RBT_PARENT(struct _type *elm) \
906{ \
907 return _rb_parent(_name##_RBT_TYPE, elm); \
908} \
909 \
910__unused static inline void \
911_name##_RBT_SET_LEFT(struct _type *elm, struct _type *left) \
912{ \
913 return _rb_set_left(_name##_RBT_TYPE, elm, left); \
914} \
915 \
916__unused static inline void \
917_name##_RBT_SET_RIGHT(struct _type *elm, struct _type *right) \
918{ \
919 return _rb_set_right(_name##_RBT_TYPE, elm, right); \
920} \
921 \
922__unused static inline void \
923_name##_RBT_SET_PARENT(struct _type *elm, struct _type *parent) \
924{ \
925 return _rb_set_parent(_name##_RBT_TYPE, elm, parent); \
926} \
927 \
928__unused static inline void \
929_name##_RBT_POISON(struct _type *elm, unsigned long poison) \
930{ \
931 return _rb_poison(_name##_RBT_TYPE, elm, poison); \
932} \
933 \
934__unused static inline int \
935_name##_RBT_CHECK(struct _type *elm, unsigned long poison) \
936{ \
937 return _rb_check(_name##_RBT_TYPE, elm, poison); \
938}
939
940#define RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _aug) \
941static int \
942_name##_RBT_COMPARE(const void *lptr, const void *rptr) \
943{ \
944 const struct _type *l = lptr, *r = rptr; \
945 return _cmp(l, r); \
946} \
947static const struct rb_type _name##_RBT_INFO = { \
948 _name##_RBT_COMPARE, \
949 _aug, \
950 offsetof(struct _type, _field), \
951}; \
952const struct rb_type *const _name##_RBT_TYPE = &_name##_RBT_INFO
953
954#define RBT_GENERATE_AUGMENT(_name, _type, _field, _cmp, _aug) \
955static void \
956_name##_RBT_AUGMENT(void *ptr) \
957{ \
958 struct _type *p = ptr; \
959 return _aug(p); \
960} \
961RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, _name##_RBT_AUGMENT)
962
963#define RBT_GENERATE(_name, _type, _field, _cmp) \
964 RBT_GENERATE_INTERNAL(_name, _type, _field, _cmp, NULL)
965
966#define RBT_INIT(_name, _head) _name##_RBT_INIT(_head)
967#define RBT_INSERT(_name, _head, _elm) _name##_RBT_INSERT(_head, _elm)
968#define RBT_REMOVE(_name, _head, _elm) _name##_RBT_REMOVE(_head, _elm)
969#define RBT_FIND(_name, _head, _key) _name##_RBT_FIND(_head, _key)
970#define RBT_NFIND(_name, _head, _key) _name##_RBT_NFIND(_head, _key)
971#define RBT_ROOT(_name, _head) _name##_RBT_ROOT(_head)
972#define RBT_EMPTY(_name, _head) _name##_RBT_EMPTY(_head)
973#define RBT_MIN(_name, _head) _name##_RBT_MIN(_head)
974#define RBT_MAX(_name, _head) _name##_RBT_MAX(_head)
975#define RBT_NEXT(_name, _elm) _name##_RBT_NEXT(_elm)
976#define RBT_PREV(_name, _elm) _name##_RBT_PREV(_elm)
977#define RBT_LEFT(_name, _elm) _name##_RBT_LEFT(_elm)
978#define RBT_RIGHT(_name, _elm) _name##_RBT_RIGHT(_elm)
979#define RBT_PARENT(_name, _elm) _name##_RBT_PARENT(_elm)
980#define RBT_SET_LEFT(_name, _elm, _l) _name##_RBT_SET_LEFT(_elm, _l)
981#define RBT_SET_RIGHT(_name, _elm, _r) _name##_RBT_SET_RIGHT(_elm, _r)
982#define RBT_SET_PARENT(_name, _elm, _p) _name##_RBT_SET_PARENT(_elm, _p)
983#define RBT_POISON(_name, _elm, _p) _name##_RBT_POISON(_elm, _p)
984#define RBT_CHECK(_name, _elm, _p) _name##_RBT_CHECK(_elm, _p)
985
986#define RBT_FOREACH(_e, _name, _head) \
987 for ((_e) = RBT_MIN(_name, (_head)); \
988 (_e) != NULL; \
989 (_e) = RBT_NEXT(_name, (_e)))
990
991#define RBT_FOREACH_SAFE(_e, _name, _head, _n) \
992 for ((_e) = RBT_MIN(_name, (_head)); \
993 (_e) != NULL && ((_n) = RBT_NEXT(_name, (_e)), 1); \
994 (_e) = (_n))
995
996#define RBT_FOREACH_REVERSE(_e, _name, _head) \
997 for ((_e) = RBT_MAX(_name, (_head)); \
998 (_e) != NULL; \
999 (_e) = RBT_PREV(_name, (_e)))
1000
1001#define RBT_FOREACH_REVERSE_SAFE(_e, _name, _head, _n) \
1002 for ((_e) = RBT_MAX(_name, (_head)); \
1003 (_e) != NULL && ((_n) = RBT_PREV(_name, (_e)), 1); \
1004 (_e) = (_n))
1005
1006#endif /* _SYS_TREE_H_ */
diff --git a/libtls.pc.in b/libtls.pc.in
index 82a6a71..0d4e625 100644
--- a/libtls.pc.in
+++ b/libtls.pc.in
@@ -9,8 +9,7 @@ Name: LibreSSL-libtls
9Description: Secure communications using the TLS socket protocol. 9Description: Secure communications using the TLS socket protocol.
10Version: @VERSION@ 10Version: @VERSION@
11Requires: 11Requires:
12Requires.private: libcrypto libssl
13Conflicts: 12Conflicts:
14Libs: -L${libdir} -ltls 13Libs: -L${libdir} -ltls
15Libs.private: @LIBS@ -lcrypto -lssl @PLATFORM_LDADD@ 14Libs.private: @LIBS@ @PLATFORM_LDADD@
16Cflags: -I${includedir} 15Cflags: -I${includedir}
diff --git a/m4/ax_add_fortify_source.m4 b/m4/ax_add_fortify_source.m4
new file mode 100644
index 0000000..7e15312
--- /dev/null
+++ b/m4/ax_add_fortify_source.m4
@@ -0,0 +1,80 @@
1# ===========================================================================
2# https://www.gnu.org/software/autoconf-archive/ax_add_fortify_source.html
3# ===========================================================================
4#
5# SYNOPSIS
6#
7# AX_ADD_FORTIFY_SOURCE
8#
9# DESCRIPTION
10#
11# Check whether -D_FORTIFY_SOURCE=2 can be added to CPPFLAGS without macro
12# redefinition warnings, other cpp warnings or linker. Some distributions
13# (such as Gentoo Linux) enable _FORTIFY_SOURCE globally in their
14# compilers, leading to unnecessary warnings in the form of
15#
16# <command-line>:0:0: error: "_FORTIFY_SOURCE" redefined [-Werror]
17# <built-in>: note: this is the location of the previous definition
18#
19# which is a problem if -Werror is enabled. This macro checks whether
20# _FORTIFY_SOURCE is already defined, and if not, adds -D_FORTIFY_SOURCE=2
21# to CPPFLAGS.
22#
23# Newer mingw-w64 msys2 package comes with a bug in
24# headers-git-7.0.0.5546.d200317d-1. It broke -D_FORTIFY_SOURCE support,
25# and would need -lssp or -fstack-protector. See
26# https://github.com/msys2/MINGW-packages/issues/5803. Try to actually
27# link it.
28#
29# LICENSE
30#
31# Copyright (c) 2017 David Seifert <soap@gentoo.org>
32# Copyright (c) 2019 Reini Urban <rurban@cpan.org>
33#
34# Copying and distribution of this file, with or without modification, are
35# permitted in any medium without royalty provided the copyright notice
36# and this notice are preserved. This file is offered as-is, without any
37# warranty.
38
39#serial 4
40
41AC_DEFUN([AX_ADD_FORTIFY_SOURCE],[
42 ac_save_cflags=$CFLAGS
43 ac_cwerror_flag=yes
44 AX_CHECK_COMPILE_FLAG([-Werror],[CFLAGS="$CFLAGS -Werror"])
45 AC_MSG_CHECKING([whether to add -D_FORTIFY_SOURCE=2 to CPPFLAGS])
46 AC_LINK_IFELSE([
47 AC_LANG_PROGRAM([],
48 [[
49 #ifndef _FORTIFY_SOURCE
50 return 0;
51 #else
52 this_is_an_error;
53 #endif
54 ]]
55 )],
56 AC_LINK_IFELSE([
57 AC_LANG_SOURCE([[
58 #define _FORTIFY_SOURCE 2
59 #include <string.h>
60 int main() {
61 char *s = " ";
62 strcpy(s, "x");
63 return strlen(s)-1;
64 }
65 ]]
66 )],
67 [
68 AC_MSG_RESULT([yes])
69 CFLAGS=$ac_save_cflags
70 CPPFLAGS="$CPPFLAGS -D_FORTIFY_SOURCE=2"
71 ], [
72 AC_MSG_RESULT([no])
73 CFLAGS=$ac_save_cflags
74 ],
75 ),
76 [
77 AC_MSG_RESULT([no])
78 CFLAGS=$ac_save_cflags
79 ])
80])
diff --git a/m4/ax_check_compile_flag.m4 b/m4/ax_check_compile_flag.m4
new file mode 100644
index 0000000..bd753b3
--- /dev/null
+++ b/m4/ax_check_compile_flag.m4
@@ -0,0 +1,53 @@
1# ===========================================================================
2# https://www.gnu.org/software/autoconf-archive/ax_check_compile_flag.html
3# ===========================================================================
4#
5# SYNOPSIS
6#
7# AX_CHECK_COMPILE_FLAG(FLAG, [ACTION-SUCCESS], [ACTION-FAILURE], [EXTRA-FLAGS], [INPUT])
8#
9# DESCRIPTION
10#
11# Check whether the given FLAG works with the current language's compiler
12# or gives an error. (Warnings, however, are ignored)
13#
14# ACTION-SUCCESS/ACTION-FAILURE are shell commands to execute on
15# success/failure.
16#
17# If EXTRA-FLAGS is defined, it is added to the current language's default
18# flags (e.g. CFLAGS) when the check is done. The check is thus made with
19# the flags: "CFLAGS EXTRA-FLAGS FLAG". This can for example be used to
20# force the compiler to issue an error when a bad flag is given.
21#
22# INPUT gives an alternative input source to AC_COMPILE_IFELSE.
23#
24# NOTE: Implementation based on AX_CFLAGS_GCC_OPTION. Please keep this
25# macro in sync with AX_CHECK_{PREPROC,LINK}_FLAG.
26#
27# LICENSE
28#
29# Copyright (c) 2008 Guido U. Draheim <guidod@gmx.de>
30# Copyright (c) 2011 Maarten Bosmans <mkbosmans@gmail.com>
31#
32# Copying and distribution of this file, with or without modification, are
33# permitted in any medium without royalty provided the copyright notice
34# and this notice are preserved. This file is offered as-is, without any
35# warranty.
36
37#serial 6
38
39AC_DEFUN([AX_CHECK_COMPILE_FLAG],
40[AC_PREREQ(2.64)dnl for _AC_LANG_PREFIX and AS_VAR_IF
41AS_VAR_PUSHDEF([CACHEVAR],[ax_cv_check_[]_AC_LANG_ABBREV[]flags_$4_$1])dnl
42AC_CACHE_CHECK([whether _AC_LANG compiler accepts $1], CACHEVAR, [
43 ax_check_save_flags=$[]_AC_LANG_PREFIX[]FLAGS
44 _AC_LANG_PREFIX[]FLAGS="$[]_AC_LANG_PREFIX[]FLAGS $4 $1"
45 AC_COMPILE_IFELSE([m4_default([$5],[AC_LANG_PROGRAM()])],
46 [AS_VAR_SET(CACHEVAR,[yes])],
47 [AS_VAR_SET(CACHEVAR,[no])])
48 _AC_LANG_PREFIX[]FLAGS=$ax_check_save_flags])
49AS_VAR_IF(CACHEVAR,yes,
50 [m4_default([$2], :)],
51 [m4_default([$3], :)])
52AS_VAR_POPDEF([CACHEVAR])dnl
53])dnl AX_CHECK_COMPILE_FLAGS
diff --git a/m4/check-hardening-options.m4 b/m4/check-hardening-options.m4
index 3ffdb1a..869f00b 100644
--- a/m4/check-hardening-options.m4
+++ b/m4/check-hardening-options.m4
@@ -73,7 +73,7 @@ AC_DEFUN([CHECK_C_HARDENING_OPTIONS], [
73 CHECK_CFLAG([[-fno-strict-overflow]]) 73 CHECK_CFLAG([[-fno-strict-overflow]])
74 74
75 # _FORTIFY_SOURCE replaces builtin functions with safer versions. 75 # _FORTIFY_SOURCE replaces builtin functions with safer versions.
76 CHECK_CFLAG([[-D_FORTIFY_SOURCE=2]]) 76 AX_ADD_FORTIFY_SOURCE
77 77
78 # Enable read only relocations 78 # Enable read only relocations
79 CHECK_LDFLAG([[-Wl,-z,relro]]) 79 CHECK_LDFLAG([[-Wl,-z,relro]])
diff --git a/man/links b/man/links
index 337d3d8..c01e8fa 100644
--- a/man/links
+++ b/man/links
@@ -374,6 +374,14 @@ BUF_MEM_new.3,BUF_MEM_grow.3
374BUF_MEM_new.3,BUF_MEM_grow_clean.3 374BUF_MEM_new.3,BUF_MEM_grow_clean.3
375BUF_MEM_new.3,BUF_reverse.3 375BUF_MEM_new.3,BUF_reverse.3
376BUF_MEM_new.3,BUF_strdup.3 376BUF_MEM_new.3,BUF_strdup.3
377CMAC_Init.3,CMAC_CTX_cleanup.3
378CMAC_Init.3,CMAC_CTX_copy.3
379CMAC_Init.3,CMAC_CTX_free.3
380CMAC_Init.3,CMAC_CTX_get0_cipher_ctx.3
381CMAC_Init.3,CMAC_CTX_new.3
382CMAC_Init.3,CMAC_Final.3
383CMAC_Init.3,CMAC_Update.3
384CMAC_Init.3,CMAC_resume.3
377CMS_ContentInfo_new.3,CMS_ContentInfo_free.3 385CMS_ContentInfo_new.3,CMS_ContentInfo_free.3
378CMS_ContentInfo_new.3,CMS_ContentInfo_print_ctx.3 386CMS_ContentInfo_new.3,CMS_ContentInfo_print_ctx.3
379CMS_ContentInfo_new.3,CMS_ReceiptRequest_free.3 387CMS_ContentInfo_new.3,CMS_ReceiptRequest_free.3
@@ -432,6 +440,11 @@ CRYPTO_set_ex_data.3,CRYPTO_free_ex_data.3
432CRYPTO_set_ex_data.3,CRYPTO_get_ex_data.3 440CRYPTO_set_ex_data.3,CRYPTO_get_ex_data.3
433CRYPTO_set_ex_data.3,CRYPTO_get_ex_new_index.3 441CRYPTO_set_ex_data.3,CRYPTO_get_ex_new_index.3
434CRYPTO_set_ex_data.3,CRYPTO_new_ex_data.3 442CRYPTO_set_ex_data.3,CRYPTO_new_ex_data.3
443ChaCha.3,CRYPTO_chacha_20.3
444ChaCha.3,CRYPTO_hchacha_20.3
445ChaCha.3,CRYPTO_xchacha_20.3
446ChaCha.3,ChaCha_set_iv.3
447ChaCha.3,ChaCha_set_key.3
435DES_set_key.3,DES_cbc_cksum.3 448DES_set_key.3,DES_cbc_cksum.3
436DES_set_key.3,DES_cfb64_encrypt.3 449DES_set_key.3,DES_cfb64_encrypt.3
437DES_set_key.3,DES_cfb_encrypt.3 450DES_set_key.3,DES_cfb_encrypt.3
@@ -1257,11 +1270,16 @@ OPENSSL_sk_new.3,sk_zero.3
1257OpenSSL_add_all_algorithms.3,EVP_cleanup.3 1270OpenSSL_add_all_algorithms.3,EVP_cleanup.3
1258OpenSSL_add_all_algorithms.3,OpenSSL_add_all_ciphers.3 1271OpenSSL_add_all_algorithms.3,OpenSSL_add_all_ciphers.3
1259OpenSSL_add_all_algorithms.3,OpenSSL_add_all_digests.3 1272OpenSSL_add_all_algorithms.3,OpenSSL_add_all_digests.3
1273PEM_ASN1_read.3,PEM_ASN1_read_bio.3
1274PEM_ASN1_read.3,d2i_of_void.3
1275PEM_X509_INFO_read.3,PEM_X509_INFO_read_bio.3
1276PEM_read.3,PEM_def_callback.3
1260PEM_read.3,PEM_do_header.3 1277PEM_read.3,PEM_do_header.3
1261PEM_read.3,PEM_get_EVP_CIPHER_INFO.3 1278PEM_read.3,PEM_get_EVP_CIPHER_INFO.3
1262PEM_read.3,PEM_read_bio.3 1279PEM_read.3,PEM_read_bio.3
1263PEM_read.3,PEM_write.3 1280PEM_read.3,PEM_write.3
1264PEM_read.3,PEM_write_bio.3 1281PEM_read.3,PEM_write_bio.3
1282PEM_read.3,pem_password_cb.3
1265PEM_read_SSL_SESSION.3,PEM_read_bio_SSL_SESSION.3 1283PEM_read_SSL_SESSION.3,PEM_read_bio_SSL_SESSION.3
1266PEM_read_SSL_SESSION.3,PEM_write_SSL_SESSION.3 1284PEM_read_SSL_SESSION.3,PEM_write_SSL_SESSION.3
1267PEM_read_SSL_SESSION.3,PEM_write_bio_SSL_SESSION.3 1285PEM_read_SSL_SESSION.3,PEM_write_bio_SSL_SESSION.3
@@ -1354,7 +1372,6 @@ PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_AUX.3
1354PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_CRL.3 1372PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_CRL.3
1355PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_REQ.3 1373PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_REQ.3
1356PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_REQ_NEW.3 1374PEM_read_bio_PrivateKey.3,PEM_write_bio_X509_REQ_NEW.3
1357PEM_read_bio_PrivateKey.3,pem_password_cb.3
1358PKCS12_SAFEBAG_new.3,PKCS12_BAGS_free.3 1375PKCS12_SAFEBAG_new.3,PKCS12_BAGS_free.3
1359PKCS12_SAFEBAG_new.3,PKCS12_BAGS_new.3 1376PKCS12_SAFEBAG_new.3,PKCS12_BAGS_new.3
1360PKCS12_SAFEBAG_new.3,PKCS12_SAFEBAG_free.3 1377PKCS12_SAFEBAG_new.3,PKCS12_SAFEBAG_free.3
@@ -1362,6 +1379,15 @@ PKCS12_new.3,PKCS12_MAC_DATA_free.3
1362PKCS12_new.3,PKCS12_MAC_DATA_new.3 1379PKCS12_new.3,PKCS12_MAC_DATA_new.3
1363PKCS12_new.3,PKCS12_free.3 1380PKCS12_new.3,PKCS12_free.3
1364PKCS5_PBKDF2_HMAC.3,PKCS5_PBKDF2_HMAC_SHA1.3 1381PKCS5_PBKDF2_HMAC.3,PKCS5_PBKDF2_HMAC_SHA1.3
1382PKCS7_add_attribute.3,PKCS7_add0_attrib_signing_time.3
1383PKCS7_add_attribute.3,PKCS7_add1_attrib_digest.3
1384PKCS7_add_attribute.3,PKCS7_add_attrib_content_type.3
1385PKCS7_add_attribute.3,PKCS7_add_attrib_smimecap.3
1386PKCS7_add_attribute.3,PKCS7_add_signed_attribute.3
1387PKCS7_add_attribute.3,PKCS7_get_attribute.3
1388PKCS7_add_attribute.3,PKCS7_get_signed_attribute.3
1389PKCS7_add_attribute.3,PKCS7_set_attributes.3
1390PKCS7_add_attribute.3,PKCS7_set_signed_attributes.3
1365PKCS7_new.3,PKCS7_DIGEST_free.3 1391PKCS7_new.3,PKCS7_DIGEST_free.3
1366PKCS7_new.3,PKCS7_DIGEST_new.3 1392PKCS7_new.3,PKCS7_DIGEST_new.3
1367PKCS7_new.3,PKCS7_ENCRYPT_free.3 1393PKCS7_new.3,PKCS7_ENCRYPT_free.3
@@ -2030,26 +2056,37 @@ X509_digest.3,X509_REQ_digest.3
2030X509_digest.3,X509_pubkey_digest.3 2056X509_digest.3,X509_pubkey_digest.3
2031X509_get0_notBefore.3,X509_CRL_get0_lastUpdate.3 2057X509_get0_notBefore.3,X509_CRL_get0_lastUpdate.3
2032X509_get0_notBefore.3,X509_CRL_get0_nextUpdate.3 2058X509_get0_notBefore.3,X509_CRL_get0_nextUpdate.3
2059X509_get0_notBefore.3,X509_CRL_get_lastUpdate.3
2060X509_get0_notBefore.3,X509_CRL_get_nextUpdate.3
2033X509_get0_notBefore.3,X509_CRL_set1_lastUpdate.3 2061X509_get0_notBefore.3,X509_CRL_set1_lastUpdate.3
2034X509_get0_notBefore.3,X509_CRL_set1_nextUpdate.3 2062X509_get0_notBefore.3,X509_CRL_set1_nextUpdate.3
2063X509_get0_notBefore.3,X509_CRL_set_lastUpdate.3
2064X509_get0_notBefore.3,X509_CRL_set_nextUpdate.3
2035X509_get0_notBefore.3,X509_get0_notAfter.3 2065X509_get0_notBefore.3,X509_get0_notAfter.3
2066X509_get0_notBefore.3,X509_get_notAfter.3
2067X509_get0_notBefore.3,X509_get_notBefore.3
2036X509_get0_notBefore.3,X509_getm_notAfter.3 2068X509_get0_notBefore.3,X509_getm_notAfter.3
2037X509_get0_notBefore.3,X509_getm_notBefore.3 2069X509_get0_notBefore.3,X509_getm_notBefore.3
2038X509_get0_notBefore.3,X509_set1_notAfter.3 2070X509_get0_notBefore.3,X509_set1_notAfter.3
2039X509_get0_notBefore.3,X509_set1_notBefore.3 2071X509_get0_notBefore.3,X509_set1_notBefore.3
2072X509_get0_notBefore.3,X509_set_notAfter.3
2073X509_get0_notBefore.3,X509_set_notBefore.3
2040X509_get0_signature.3,X509_CRL_get0_signature.3 2074X509_get0_signature.3,X509_CRL_get0_signature.3
2041X509_get0_signature.3,X509_CRL_get_signature_nid.3 2075X509_get0_signature.3,X509_CRL_get_signature_nid.3
2042X509_get0_signature.3,X509_REQ_get0_signature.3 2076X509_get0_signature.3,X509_REQ_get0_signature.3
2043X509_get0_signature.3,X509_REQ_get_signature_nid.3 2077X509_get0_signature.3,X509_REQ_get_signature_nid.3
2044X509_get0_signature.3,X509_get0_tbs_sigalg.3 2078X509_get0_signature.3,X509_get0_tbs_sigalg.3
2045X509_get0_signature.3,X509_get_signature_nid.3 2079X509_get0_signature.3,X509_get_signature_nid.3
2080X509_get0_signature.3,X509_get_signature_type.3
2046X509_get1_email.3,X509_email_free.3 2081X509_get1_email.3,X509_email_free.3
2047X509_get1_email.3,X509_get1_ocsp.3 2082X509_get1_email.3,X509_get1_ocsp.3
2048X509_get_pubkey.3,X509_REQ_get_pubkey.3 2083X509_get_pubkey.3,X509_REQ_get_pubkey.3
2049X509_get_pubkey.3,X509_REQ_set_pubkey.3 2084X509_get_pubkey.3,X509_REQ_set_pubkey.3
2050X509_get_pubkey.3,X509_get0_pubkey.3 2085X509_get_pubkey.3,X509_get0_pubkey.3
2086X509_get_pubkey.3,X509_get0_pubkey_bitstr.3
2051X509_get_pubkey.3,X509_get_X509_PUBKEY.3 2087X509_get_pubkey.3,X509_get_X509_PUBKEY.3
2052X509_get_pubkey.3,X509_set_pubkey.3 2088X509_get_pubkey.3,X509_set_pubkey.3
2089X509_get_serialNumber.3,X509_get0_serialNumber.3
2053X509_get_serialNumber.3,X509_set_serialNumber.3 2090X509_get_serialNumber.3,X509_set_serialNumber.3
2054X509_get_subject_name.3,X509_CRL_get_issuer.3 2091X509_get_subject_name.3,X509_CRL_get_issuer.3
2055X509_get_subject_name.3,X509_CRL_set_issuer_name.3 2092X509_get_subject_name.3,X509_CRL_set_issuer_name.3
@@ -2444,6 +2481,7 @@ d2i_X509_SIG.3,i2d_PKCS8_bio.3
2444d2i_X509_SIG.3,i2d_PKCS8_fp.3 2481d2i_X509_SIG.3,i2d_PKCS8_fp.3
2445d2i_X509_SIG.3,i2d_X509_SIG.3 2482d2i_X509_SIG.3,i2d_X509_SIG.3
2446des_read_pw.3,EVP_read_pw_string.3 2483des_read_pw.3,EVP_read_pw_string.3
2484des_read_pw.3,EVP_read_pw_string_min.3
2447des_read_pw.3,des_read_pw_string.3 2485des_read_pw.3,des_read_pw_string.3
2448get_rfc3526_prime_8192.3,BN_get_rfc2409_prime_1024.3 2486get_rfc3526_prime_8192.3,BN_get_rfc2409_prime_1024.3
2449get_rfc3526_prime_8192.3,BN_get_rfc2409_prime_768.3 2487get_rfc3526_prime_8192.3,BN_get_rfc2409_prime_768.3
diff --git a/patches/aeadtest.c.patch b/patches/aeadtest.c.patch
index a7b3fca..4f7319d 100644
--- a/patches/aeadtest.c.patch
+++ b/patches/aeadtest.c.patch
@@ -1,9 +1,9 @@
1--- tests/aeadtest.c.orig 2018-07-24 21:59:17.000000000 -0500 1--- tests/aeadtest.c.orig Sat Jan 26 12:39:05 2019
2+++ tests/aeadtest.c 2018-11-07 18:44:43.000000000 -0600 2+++ tests/aeadtest.c Fri Sep 4 04:04:26 2020
3@@ -76,6 +76,12 @@ 3@@ -79,6 +79,12 @@
4 4
5 #define BUF_MAX 1024 5 #define BUF_MAX 1024
6 6
7+#ifdef _MSC_VER 7+#ifdef _MSC_VER
8+#ifdef IN 8+#ifdef IN
9+#undef IN 9+#undef IN
diff --git a/patches/handshake_table.c.patch b/patches/handshake_table.c.patch
index 46f2adb..b0a9f5b 100644
--- a/patches/handshake_table.c.patch
+++ b/patches/handshake_table.c.patch
@@ -1,6 +1,6 @@
1--- tests/handshake_table.c.orig Mon May 4 23:28:43 2020 1--- tests/handshake_table.c.orig Sat Aug 22 18:51:52 2020
2+++ tests/handshake_table.c Mon May 4 23:29:50 2020 2+++ tests/handshake_table.c Fri Sep 4 04:04:26 2020
3@@ -477,6 +477,7 @@ 3@@ -479,6 +479,7 @@
4 unsigned int depth = 0; 4 unsigned int depth = 0;
5 int ch, graphviz = 0, print = 0; 5 int ch, graphviz = 0, print = 0;
6 6
@@ -8,7 +8,7 @@
8 while ((ch = getopt(argc, argv, "Cg")) != -1) { 8 while ((ch = getopt(argc, argv, "Cg")) != -1) {
9 switch (ch) { 9 switch (ch) {
10 case 'C': 10 case 'C':
11@@ -494,6 +495,7 @@ 11@@ -496,6 +497,7 @@
12 12
13 if (argc != 0) 13 if (argc != 0)
14 usage(); 14 usage();
diff --git a/patches/openssl.c.patch b/patches/openssl.c.patch
index c41f25b..2c2a3da 100644
--- a/patches/openssl.c.patch
+++ b/patches/openssl.c.patch
@@ -1,6 +1,6 @@
1--- apps/openssl/openssl.c.orig Fri Dec 14 01:44:33 2018 1--- apps/openssl/openssl.c.orig Thu Nov 7 18:19:01 2019
2+++ apps/openssl/openssl.c Sat Jan 19 22:19:23 2019 2+++ apps/openssl/openssl.c Fri Sep 4 04:04:26 2020
3@@ -350,7 +350,9 @@ 3@@ -360,7 +360,9 @@
4 static void 4 static void
5 openssl_startup(void) 5 openssl_startup(void)
6 { 6 {
diff --git a/patches/tlsexttest.c.patch b/patches/tlsexttest.c.patch
index 35092c5..70a7efb 100644
--- a/patches/tlsexttest.c.patch
+++ b/patches/tlsexttest.c.patch
@@ -1,6 +1,6 @@
1--- tests/tlsexttest.c.orig Mon Jul 6 03:17:51 2020 1--- tests/tlsexttest.c.orig Sat Aug 22 18:51:52 2020
2+++ tests/tlsexttest.c Mon Jul 6 03:45:00 2020 2+++ tests/tlsexttest.c Fri Sep 4 04:04:26 2020
3@@ -1657,7 +1657,9 @@ 3@@ -1658,7 +1658,9 @@
4 }; 4 };
5 5
6 static unsigned char tlsext_sni_server[] = { 6 static unsigned char tlsext_sni_server[] = {
@@ -10,7 +10,7 @@
10 10
11 static int 11 static int
12 test_tlsext_sni_client(void) 12 test_tlsext_sni_client(void)
13@@ -1820,9 +1822,9 @@ 13@@ -1821,9 +1823,9 @@
14 if (!CBB_finish(&cbb, &data, &dlen)) 14 if (!CBB_finish(&cbb, &data, &dlen))
15 errx(1, "failed to finish CBB"); 15 errx(1, "failed to finish CBB");
16 16
@@ -22,7 +22,7 @@
22 goto err; 22 goto err;
23 } 23 }
24 24
25@@ -1831,14 +1833,14 @@ 25@@ -1832,14 +1834,14 @@
26 fprintf(stderr, "received:\n"); 26 fprintf(stderr, "received:\n");
27 hexdump(data, dlen); 27 hexdump(data, dlen);
28 fprintf(stderr, "test data:\n"); 28 fprintf(stderr, "test data:\n");
@@ -39,8 +39,8 @@
39 if (!tlsext_sni_client_parse(ssl, SSL_TLSEXT_MSG_SH, &cbs, &alert)) { 39 if (!tlsext_sni_client_parse(ssl, SSL_TLSEXT_MSG_SH, &cbs, &alert)) {
40 FAIL("failed to parse server SNI\n"); 40 FAIL("failed to parse server SNI\n");
41 goto err; 41 goto err;
42@@ -2722,7 +2724,10 @@ 42@@ -2723,7 +2725,10 @@
43 0x02, 0x01, 0x02, 0x03, 43 0x04, 0x03, 0x02, 0x01, 0x02, 0x03,
44 }; 44 };
45 45
46-unsigned char tlsext_clienthello_disabled[] = {}; 46-unsigned char tlsext_clienthello_disabled[] = {};
@@ -51,7 +51,7 @@
51 51
52 static int 52 static int
53 test_tlsext_clienthello_build(void) 53 test_tlsext_clienthello_build(void)
54@@ -2787,18 +2792,18 @@ 54@@ -2788,18 +2793,18 @@
55 if (!CBB_finish(&cbb, &data, &dlen)) 55 if (!CBB_finish(&cbb, &data, &dlen))
56 errx(1, "failed to finish CBB"); 56 errx(1, "failed to finish CBB");
57 57
diff --git a/ssl/CMakeLists.txt b/ssl/CMakeLists.txt
index 39f8192..015cb62 100644
--- a/ssl/CMakeLists.txt
+++ b/ssl/CMakeLists.txt
@@ -38,6 +38,7 @@ set(
38 ssl_versions.c 38 ssl_versions.c
39 t1_enc.c 39 t1_enc.c
40 t1_lib.c 40 t1_lib.c
41 tls12_record_layer.c
41 tls13_buffer.c 42 tls13_buffer.c
42 tls13_client.c 43 tls13_client.c
43 tls13_error.c 44 tls13_error.c
diff --git a/ssl/Makefile.am b/ssl/Makefile.am
index a7bb8a3..4c4e594 100644
--- a/ssl/Makefile.am
+++ b/ssl/Makefile.am
@@ -6,6 +6,15 @@ EXTRA_DIST = VERSION
6EXTRA_DIST += CMakeLists.txt 6EXTRA_DIST += CMakeLists.txt
7EXTRA_DIST += ssl.sym 7EXTRA_DIST += ssl.sym
8 8
9CLEANFILES = libssl_la_objects.mk
10
11EXTRA_libssl_la_DEPENDENCIES = libssl_la_objects.mk
12
13libssl_la_objects.mk: Makefile
14 @echo "libssl_la_objects= $(libssl_la_OBJECTS)" \
15 | sed 's/ */ $$\(abs_top_builddir\)\/ssl\//g' \
16 > libssl_la_objects.mk
17
9libssl_la_LDFLAGS = -version-info @LIBSSL_VERSION@ -no-undefined -export-symbols $(top_srcdir)/ssl/ssl.sym 18libssl_la_LDFLAGS = -version-info @LIBSSL_VERSION@ -no-undefined -export-symbols $(top_srcdir)/ssl/ssl.sym
10libssl_la_LIBADD = $(abs_top_builddir)/crypto/libcrypto.la $(PLATFORM_LDADD) 19libssl_la_LIBADD = $(abs_top_builddir)/crypto/libcrypto.la $(PLATFORM_LDADD)
11 20
@@ -47,6 +56,7 @@ libssl_la_SOURCES += ssl_txt.c
47libssl_la_SOURCES += ssl_versions.c 56libssl_la_SOURCES += ssl_versions.c
48libssl_la_SOURCES += t1_enc.c 57libssl_la_SOURCES += t1_enc.c
49libssl_la_SOURCES += t1_lib.c 58libssl_la_SOURCES += t1_lib.c
59libssl_la_SOURCES += tls12_record_layer.c
50libssl_la_SOURCES += tls13_buffer.c 60libssl_la_SOURCES += tls13_buffer.c
51libssl_la_SOURCES += tls13_client.c 61libssl_la_SOURCES += tls13_client.c
52libssl_la_SOURCES += tls13_error.c 62libssl_la_SOURCES += tls13_error.c
diff --git a/tests/CMakeLists.txt b/tests/CMakeLists.txt
index 787c955..13dd005 100644
--- a/tests/CMakeLists.txt
+++ b/tests/CMakeLists.txt
@@ -2,6 +2,7 @@ include_directories(
2 . 2 .
3 ../crypto/modes 3 ../crypto/modes
4 ../crypto/asn1 4 ../crypto/asn1
5 ../crypto/x509
5 ../ssl 6 ../ssl
6 ../tls 7 ../tls
7 ../apps/openssl 8 ../apps/openssl
@@ -123,10 +124,12 @@ if(NOT BUILD_SHARED_LIBS)
123 add_test(cipher_list cipher_list) 124 add_test(cipher_list cipher_list)
124endif() 125endif()
125 126
126# cipherstest 127if(NOT BUILD_SHARED_LIBS)
127add_executable(cipherstest cipherstest.c) 128 # cipherstest
128target_link_libraries(cipherstest ${OPENSSL_LIBS}) 129 add_executable(cipherstest cipherstest.c)
129add_test(cipherstest cipherstest) 130 target_link_libraries(cipherstest ${OPENSSL_LIBS})
131 add_test(cipherstest cipherstest)
132endif()
130 133
131# clienttest 134# clienttest
132# disabled 135# disabled
@@ -144,6 +147,13 @@ add_executable(configtest configtest.c)
144target_link_libraries(configtest ${OPENSSL_LIBS}) 147target_link_libraries(configtest ${OPENSSL_LIBS})
145add_test(configtest configtest) 148add_test(configtest configtest)
146 149
150# constraints
151if(NOT BUILD_SHARED_LIBS)
152 add_executable(constraints constraints.c)
153 target_link_libraries(constraints ${OPENSSL_LIBS})
154 add_test(constraints constraints)
155endif()
156
147# cts128test 157# cts128test
148add_executable(cts128test cts128test.c) 158add_executable(cts128test cts128test.c)
149target_link_libraries(cts128test ${OPENSSL_LIBS}) 159target_link_libraries(cts128test ${OPENSSL_LIBS})
@@ -533,6 +543,16 @@ add_executable(x25519test x25519test.c)
533target_link_libraries(x25519test ${OPENSSL_LIBS}) 543target_link_libraries(x25519test ${OPENSSL_LIBS})
534add_test(x25519test x25519test) 544add_test(x25519test x25519test)
535 545
546# x509attribute
547add_executable(x509attribute x509attribute.c)
548target_link_libraries(x509attribute ${OPENSSL_LIBS})
549add_test(x509attribute x509attribute)
550
551# x509_info
552add_executable(x509_info x509_info.c)
553target_link_libraries(x509_info ${OPENSSL_LIBS})
554add_test(x509_info x509_info)
555
536# x509name 556# x509name
537add_executable(x509name x509name.c) 557add_executable(x509name x509name.c)
538target_link_libraries(x509name ${OPENSSL_LIBS}) 558target_link_libraries(x509name ${OPENSSL_LIBS})
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 86db040..34f088a 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -2,6 +2,7 @@ include $(top_srcdir)/Makefile.am.common
2 2
3AM_CPPFLAGS += -I $(top_srcdir)/crypto/modes 3AM_CPPFLAGS += -I $(top_srcdir)/crypto/modes
4AM_CPPFLAGS += -I $(top_srcdir)/crypto/asn1 4AM_CPPFLAGS += -I $(top_srcdir)/crypto/asn1
5AM_CPPFLAGS += -I $(top_srcdir)/crypto/x509
5AM_CPPFLAGS += -I $(top_srcdir)/ssl 6AM_CPPFLAGS += -I $(top_srcdir)/ssl
6AM_CPPFLAGS += -I $(top_srcdir)/tls 7AM_CPPFLAGS += -I $(top_srcdir)/tls
7AM_CPPFLAGS += -I $(top_srcdir)/apps/openssl 8AM_CPPFLAGS += -I $(top_srcdir)/apps/openssl
@@ -146,6 +147,11 @@ TESTS += configtest
146check_PROGRAMS += configtest 147check_PROGRAMS += configtest
147configtest_SOURCES = configtest.c 148configtest_SOURCES = configtest.c
148 149
150# constraints
151TESTS += constraints
152check_PROGRAMS += constraints
153constraints_SOURCES = constraints.c
154
149# cts128test 155# cts128test
150TESTS += cts128test 156TESTS += cts128test
151check_PROGRAMS += cts128test 157check_PROGRAMS += cts128test
@@ -473,6 +479,16 @@ TESTS += x25519test
473check_PROGRAMS += x25519test 479check_PROGRAMS += x25519test
474x25519test_SOURCES = x25519test.c 480x25519test_SOURCES = x25519test.c
475 481
482# x509attribute
483TESTS += x509attribute
484check_PROGRAMS += x509attribute
485x509attribute_SOURCES = x509attribute.c
486
487# x509_info
488TESTS += x509_info
489check_PROGRAMS += x509_info
490x509_info_SOURCES = x509_info.c
491
476# x509name 492# x509name
477TESTS += x509name 493TESTS += x509name
478check_PROGRAMS += x509name 494check_PROGRAMS += x509name
diff --git a/tls/Makefile.am b/tls/Makefile.am
index 942abf9..4cea3a2 100644
--- a/tls/Makefile.am
+++ b/tls/Makefile.am
@@ -1,5 +1,8 @@
1include $(top_srcdir)/Makefile.am.common 1include $(top_srcdir)/Makefile.am.common
2 2
3-include $(abs_top_builddir)/crypto/libcrypto_la_objects.mk
4-include $(abs_top_builddir)/ssl/libssl_la_objects.mk
5
3lib_LTLIBRARIES = libtls.la 6lib_LTLIBRARIES = libtls.la
4 7
5EXTRA_DIST = VERSION 8EXTRA_DIST = VERSION
@@ -7,8 +10,10 @@ EXTRA_DIST += CMakeLists.txt
7EXTRA_DIST += tls.sym 10EXTRA_DIST += tls.sym
8 11
9libtls_la_LDFLAGS = -version-info @LIBTLS_VERSION@ -no-undefined -export-symbols $(top_srcdir)/tls/tls.sym 12libtls_la_LDFLAGS = -version-info @LIBTLS_VERSION@ -no-undefined -export-symbols $(top_srcdir)/tls/tls.sym
10libtls_la_LIBADD = $(abs_top_builddir)/ssl/libssl.la 13libtls_la_LIBADD = $(libcrypto_la_objects)
11libtls_la_LIBADD += $(abs_top_builddir)/crypto/libcrypto.la 14libtls_la_LIBADD += $(libcompat_la_objects)
15libtls_la_LIBADD += $(libcompatnoopt_la_objects)
16libtls_la_LIBADD += $(libssl_la_objects)
12libtls_la_LIBADD += $(PLATFORM_LDADD) 17libtls_la_LIBADD += $(PLATFORM_LDADD)
13 18
14libtls_la_CPPFLAGS = $(AM_CPPFLAGS) 19libtls_la_CPPFLAGS = $(AM_CPPFLAGS)
diff --git a/update.sh b/update.sh
index afff2f4..0ed7834 100755
--- a/update.sh
+++ b/update.sh
@@ -115,7 +115,7 @@ copy_hdrs $libcrypto_src "stack/stack.h lhash/lhash.h stack/safestack.h
115 objects/objects.h asn1/asn1.h bn/bn.h ec/ec.h ecdsa/ecdsa.h 115 objects/objects.h asn1/asn1.h bn/bn.h ec/ec.h ecdsa/ecdsa.h
116 ecdh/ecdh.h rsa/rsa.h sha/sha.h x509/x509_vfy.h pkcs7/pkcs7.h pem/pem.h 116 ecdh/ecdh.h rsa/rsa.h sha/sha.h x509/x509_vfy.h pkcs7/pkcs7.h pem/pem.h
117 pem/pem2.h hkdf/hkdf.h hmac/hmac.h rand/rand.h md5/md5.h 117 pem/pem2.h hkdf/hkdf.h hmac/hmac.h rand/rand.h md5/md5.h
118 x509/x509v3.h conf/conf.h ocsp/ocsp.h 118 x509/x509v3.h x509/x509_verify.h conf/conf.h ocsp/ocsp.h
119 aes/aes.h modes/modes.h asn1/asn1t.h dso/dso.h bf/blowfish.h 119 aes/aes.h modes/modes.h asn1/asn1t.h dso/dso.h bf/blowfish.h
120 bio/bio.h cast/cast.h cmac/cmac.h cms/cms.h conf/conf_api.h des/des.h dh/dh.h 120 bio/bio.h cast/cast.h cmac/cmac.h cms/cms.h conf/conf_api.h des/des.h dh/dh.h
121 dsa/dsa.h engine/engine.h ui/ui.h pkcs12/pkcs12.h ts/ts.h 121 dsa/dsa.h engine/engine.h ui/ui.h pkcs12/pkcs12.h ts/ts.h
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-25 08:18:11 +0000