diff options
author | Colin Watson <cjwatson@debian.org> | 2020-10-18 12:04:32 +0100 |
---|---|---|
committer | Colin Watson <cjwatson@debian.org> | 2020-10-18 12:04:32 +0100 |
commit | 2b2c99658e3e8ed452e28f88f9cdbcdfb2a461cb (patch) | |
tree | 336445493163aa0370cb7830d97ebd8819b2e2c5 /openbsd-compat | |
parent | 202f5a676221c244cd450086c334c2b59f339e86 (diff) | |
parent | 279261e1ea8150c7c64ab5fe7cb4a4ea17acbb29 (diff) |
Import openssh_8.4p1.orig.tar.gz
Diffstat (limited to 'openbsd-compat')
-rw-r--r-- | openbsd-compat/bcrypt_pbkdf.c | 4 | ||||
-rw-r--r-- | openbsd-compat/memmem.c | 216 | ||||
-rw-r--r-- | openbsd-compat/port-net.c | 7 | ||||
-rw-r--r-- | openbsd-compat/sys-queue.h | 375 |
4 files changed, 349 insertions, 253 deletions
diff --git a/openbsd-compat/bcrypt_pbkdf.c b/openbsd-compat/bcrypt_pbkdf.c index 785234563..62728d38f 100644 --- a/openbsd-compat/bcrypt_pbkdf.c +++ b/openbsd-compat/bcrypt_pbkdf.c | |||
@@ -15,6 +15,8 @@ | |||
15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | 15 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. |
16 | */ | 16 | */ |
17 | 17 | ||
18 | /* OPENBSD ORIGINAL: lib/libutil/bcrypt_pbkdf.c */ | ||
19 | |||
18 | #include "includes.h" | 20 | #include "includes.h" |
19 | 21 | ||
20 | #ifndef HAVE_BCRYPT_PBKDF | 22 | #ifndef HAVE_BCRYPT_PBKDF |
@@ -91,7 +93,7 @@ bcrypt_hash(u_int8_t *sha2pass, u_int8_t *sha2salt, u_int8_t *out) | |||
91 | cdata[i] = Blowfish_stream2word(ciphertext, sizeof(ciphertext), | 93 | cdata[i] = Blowfish_stream2word(ciphertext, sizeof(ciphertext), |
92 | &j); | 94 | &j); |
93 | for (i = 0; i < 64; i++) | 95 | for (i = 0; i < 64; i++) |
94 | blf_enc(&state, cdata, sizeof(cdata) / sizeof(uint64_t)); | 96 | blf_enc(&state, cdata, sizeof(cdata) / (sizeof(uint64_t))); |
95 | 97 | ||
96 | /* copy out */ | 98 | /* copy out */ |
97 | for (i = 0; i < BCRYPT_WORDS; i++) { | 99 | for (i = 0; i < BCRYPT_WORDS; i++) { |
diff --git a/openbsd-compat/memmem.c b/openbsd-compat/memmem.c index 3e5e6b5e6..ac1243eb0 100644 --- a/openbsd-compat/memmem.c +++ b/openbsd-compat/memmem.c | |||
@@ -1,30 +1,26 @@ | |||
1 | /* $OpenBSD: memmem.c,v 1.4 2015/08/31 02:53:57 guenther Exp $ */ | 1 | /* $OpenBSD: memmem.c,v 1.5 2020/04/16 12:39:28 claudio Exp $ */ |
2 | /*- | 2 | |
3 | * Copyright (c) 2005 Pascal Gloor <pascal.gloor@spale.com> | 3 | /* |
4 | * Copyright (c) 2005-2020 Rich Felker, et al. | ||
4 | * | 5 | * |
5 | * Redistribution and use in source and binary forms, with or without | 6 | * Permission is hereby granted, free of charge, to any person obtaining |
6 | * modification, are permitted provided that the following conditions | 7 | * a copy of this software and associated documentation files (the |
7 | * are met: | 8 | * "Software"), to deal in the Software without restriction, including |
8 | * 1. Redistributions of source code must retain the above copyright | 9 | * without limitation the rights to use, copy, modify, merge, publish, |
9 | * notice, this list of conditions and the following disclaimer. | 10 | * distribute, sublicense, and/or sell copies of the Software, and to |
10 | * 2. Redistributions in binary form must reproduce the above copyright | 11 | * permit persons to whom the Software is furnished to do so, subject to |
11 | * notice, this list of conditions and the following disclaimer in the | 12 | * the following conditions: |
12 | * documentation and/or other materials provided with the distribution. | ||
13 | * 3. The name of the author may not be used to endorse or promote | ||
14 | * products derived from this software without specific prior written | ||
15 | * permission. | ||
16 | * | 13 | * |
17 | * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | 14 | * The above copyright notice and this permission notice shall be |
18 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 15 | * included in all copies or substantial portions of the Software. |
19 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | 16 | * |
20 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | 17 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
21 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | 18 | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF |
22 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | 19 | * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. |
23 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | 20 | * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY |
24 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | 21 | * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, |
25 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | 22 | * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE |
26 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | 23 | * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
27 | * SUCH DAMAGE. | ||
28 | */ | 24 | */ |
29 | 25 | ||
30 | #include "includes.h" | 26 | #include "includes.h" |
@@ -32,38 +28,164 @@ | |||
32 | #ifndef HAVE_MEMMEM | 28 | #ifndef HAVE_MEMMEM |
33 | 29 | ||
34 | #include <string.h> | 30 | #include <string.h> |
31 | #ifdef HAVE_STDINT_H | ||
32 | #include <stdint.h> | ||
33 | #endif | ||
34 | |||
35 | static char * | ||
36 | twobyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) | ||
37 | { | ||
38 | uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; | ||
39 | for (h+=2, k-=2; k; k--, hw = hw<<8 | *h++) | ||
40 | if (hw == nw) return (char *)h-2; | ||
41 | return hw == nw ? (char *)h-2 : 0; | ||
42 | } | ||
43 | |||
44 | static char * | ||
45 | threebyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) | ||
46 | { | ||
47 | uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8; | ||
48 | uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8; | ||
49 | for (h+=3, k-=3; k; k--, hw = (hw|*h++)<<8) | ||
50 | if (hw == nw) return (char *)h-3; | ||
51 | return hw == nw ? (char *)h-3 : 0; | ||
52 | } | ||
53 | |||
54 | static char * | ||
55 | fourbyte_memmem(const unsigned char *h, size_t k, const unsigned char *n) | ||
56 | { | ||
57 | uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; | ||
58 | uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; | ||
59 | for (h+=4, k-=4; k; k--, hw = hw<<8 | *h++) | ||
60 | if (hw == nw) return (char *)h-4; | ||
61 | return hw == nw ? (char *)h-4 : 0; | ||
62 | } | ||
63 | |||
64 | #define MAX(a,b) ((a)>(b)?(a):(b)) | ||
65 | #define MIN(a,b) ((a)<(b)?(a):(b)) | ||
66 | |||
67 | #define BITOP(a,b,op) \ | ||
68 | ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) | ||
35 | 69 | ||
36 | /* | 70 | /* |
37 | * Find the first occurrence of the byte string s in byte string l. | 71 | * Maxime Crochemore and Dominique Perrin, Two-way string-matching, |
72 | * Journal of the ACM, 38(3):651-675, July 1991. | ||
38 | */ | 73 | */ |
39 | 74 | static char * | |
40 | void * | 75 | twoway_memmem(const unsigned char *h, const unsigned char *z, |
41 | memmem(const void *l, size_t l_len, const void *s, size_t s_len) | 76 | const unsigned char *n, size_t l) |
42 | { | 77 | { |
43 | const char *cur, *last; | 78 | size_t i, ip, jp, k, p, ms, p0, mem, mem0; |
44 | const char *cl = l; | 79 | size_t byteset[32 / sizeof(size_t)] = { 0 }; |
45 | const char *cs = s; | 80 | size_t shift[256]; |
81 | |||
82 | /* Computing length of needle and fill shift table */ | ||
83 | for (i=0; i<l; i++) | ||
84 | BITOP(byteset, n[i], |=), shift[n[i]] = i+1; | ||
85 | |||
86 | /* Compute maximal suffix */ | ||
87 | ip = -1; jp = 0; k = p = 1; | ||
88 | while (jp+k<l) { | ||
89 | if (n[ip+k] == n[jp+k]) { | ||
90 | if (k == p) { | ||
91 | jp += p; | ||
92 | k = 1; | ||
93 | } else k++; | ||
94 | } else if (n[ip+k] > n[jp+k]) { | ||
95 | jp += k; | ||
96 | k = 1; | ||
97 | p = jp - ip; | ||
98 | } else { | ||
99 | ip = jp++; | ||
100 | k = p = 1; | ||
101 | } | ||
102 | } | ||
103 | ms = ip; | ||
104 | p0 = p; | ||
105 | |||
106 | /* And with the opposite comparison */ | ||
107 | ip = -1; jp = 0; k = p = 1; | ||
108 | while (jp+k<l) { | ||
109 | if (n[ip+k] == n[jp+k]) { | ||
110 | if (k == p) { | ||
111 | jp += p; | ||
112 | k = 1; | ||
113 | } else k++; | ||
114 | } else if (n[ip+k] < n[jp+k]) { | ||
115 | jp += k; | ||
116 | k = 1; | ||
117 | p = jp - ip; | ||
118 | } else { | ||
119 | ip = jp++; | ||
120 | k = p = 1; | ||
121 | } | ||
122 | } | ||
123 | if (ip+1 > ms+1) ms = ip; | ||
124 | else p = p0; | ||
46 | 125 | ||
47 | /* a zero length needle should just return the haystack */ | 126 | /* Periodic needle? */ |
48 | if (s_len == 0) | 127 | if (memcmp(n, n+p, ms+1)) { |
49 | return (void *)cl; | 128 | mem0 = 0; |
129 | p = MAX(ms, l-ms-1) + 1; | ||
130 | } else mem0 = l-p; | ||
131 | mem = 0; | ||
50 | 132 | ||
51 | /* "s" must be smaller or equal to "l" */ | 133 | /* Search loop */ |
52 | if (l_len < s_len) | 134 | for (;;) { |
53 | return NULL; | 135 | /* If remainder of haystack is shorter than needle, done */ |
136 | if (z-h < l) return 0; | ||
137 | |||
138 | /* Check last byte first; advance by shift on mismatch */ | ||
139 | if (BITOP(byteset, h[l-1], &)) { | ||
140 | k = l-shift[h[l-1]]; | ||
141 | if (k) { | ||
142 | if (k < mem) k = mem; | ||
143 | h += k; | ||
144 | mem = 0; | ||
145 | continue; | ||
146 | } | ||
147 | } else { | ||
148 | h += l; | ||
149 | mem = 0; | ||
150 | continue; | ||
151 | } | ||
152 | |||
153 | /* Compare right half */ | ||
154 | for (k=MAX(ms+1,mem); k<l && n[k] == h[k]; k++); | ||
155 | if (k < l) { | ||
156 | h += k-ms; | ||
157 | mem = 0; | ||
158 | continue; | ||
159 | } | ||
160 | /* Compare left half */ | ||
161 | for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); | ||
162 | if (k <= mem) return (char *)h; | ||
163 | h += p; | ||
164 | mem = mem0; | ||
165 | } | ||
166 | } | ||
167 | |||
168 | void * | ||
169 | memmem(const void *h0, size_t k, const void *n0, size_t l) | ||
170 | { | ||
171 | const unsigned char *h = h0, *n = n0; | ||
54 | 172 | ||
55 | /* special case where s_len == 1 */ | 173 | /* Return immediately on empty needle */ |
56 | if (s_len == 1) | 174 | if (!l) return (void *)h; |
57 | return memchr(l, *cs, l_len); | ||
58 | 175 | ||
59 | /* the last position where its possible to find "s" in "l" */ | 176 | /* Return immediately when needle is longer than haystack */ |
60 | last = cl + l_len - s_len; | 177 | if (k<l) return 0; |
61 | 178 | ||
62 | for (cur = cl; cur <= last; cur++) | 179 | /* Use faster algorithms for short needles */ |
63 | if (cur[0] == cs[0] && memcmp(cur, cs, s_len) == 0) | 180 | h = memchr(h0, *n, k); |
64 | return (void *)cur; | 181 | if (!h || l==1) return (void *)h; |
182 | k -= h - (const unsigned char *)h0; | ||
183 | if (k<l) return 0; | ||
184 | if (l==2) return twobyte_memmem(h, k, n); | ||
185 | if (l==3) return threebyte_memmem(h, k, n); | ||
186 | if (l==4) return fourbyte_memmem(h, k, n); | ||
65 | 187 | ||
66 | return NULL; | 188 | return twoway_memmem(h, h+k, n, l); |
67 | } | 189 | } |
68 | DEF_WEAK(memmem); | 190 | DEF_WEAK(memmem); |
69 | #endif /* HAVE_MEMMEM */ | 191 | #endif /* HAVE_MEMMEM */ |
diff --git a/openbsd-compat/port-net.c b/openbsd-compat/port-net.c index 617bffceb..d7d8c6fa1 100644 --- a/openbsd-compat/port-net.c +++ b/openbsd-compat/port-net.c | |||
@@ -209,8 +209,11 @@ sys_tun_open(int tun, int mode, char **ifname) | |||
209 | { | 209 | { |
210 | struct ifreq ifr; | 210 | struct ifreq ifr; |
211 | char name[100]; | 211 | char name[100]; |
212 | int fd = -1, sock, flag; | 212 | int fd = -1, sock; |
213 | const char *tunbase = "tun"; | 213 | const char *tunbase = "tun"; |
214 | #if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF) | ||
215 | int flag; | ||
216 | #endif | ||
214 | 217 | ||
215 | if (ifname != NULL) | 218 | if (ifname != NULL) |
216 | *ifname = NULL; | 219 | *ifname = NULL; |
@@ -247,8 +250,8 @@ sys_tun_open(int tun, int mode, char **ifname) | |||
247 | } | 250 | } |
248 | 251 | ||
249 | /* Turn on tunnel headers */ | 252 | /* Turn on tunnel headers */ |
250 | flag = 1; | ||
251 | #if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF) | 253 | #if defined(TUNSIFHEAD) && !defined(SSH_TUN_PREPEND_AF) |
254 | flag = 1; | ||
252 | if (mode != SSH_TUNMODE_ETHERNET && | 255 | if (mode != SSH_TUNMODE_ETHERNET && |
253 | ioctl(fd, TUNSIFHEAD, &flag) == -1) { | 256 | ioctl(fd, TUNSIFHEAD, &flag) == -1) { |
254 | debug("%s: ioctl(%d, TUNSIFHEAD, 1): %s", __func__, fd, | 257 | debug("%s: ioctl(%d, TUNSIFHEAD, 1): %s", __func__, fd, |
diff --git a/openbsd-compat/sys-queue.h b/openbsd-compat/sys-queue.h index 5108f394c..816c15cd4 100644 --- a/openbsd-compat/sys-queue.h +++ b/openbsd-compat/sys-queue.h | |||
@@ -1,4 +1,4 @@ | |||
1 | /* $OpenBSD: queue.h,v 1.36 2012/04/11 13:29:14 naddy Exp $ */ | 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 $ */ | 2 | /* $NetBSD: queue.h,v 1.11 1996/05/16 05:17:14 mycroft Exp $ */ |
3 | 3 | ||
4 | /* | 4 | /* |
@@ -41,94 +41,97 @@ | |||
41 | * Require for OS/X and other platforms that have old/broken/incomplete | 41 | * Require for OS/X and other platforms that have old/broken/incomplete |
42 | * <sys/queue.h>. | 42 | * <sys/queue.h>. |
43 | */ | 43 | */ |
44 | #undef SLIST_HEAD | 44 | #undef CIRCLEQ_EMPTY |
45 | #undef SLIST_HEAD_INITIALIZER | 45 | #undef CIRCLEQ_END |
46 | #undef SLIST_ENTRY | 46 | #undef CIRCLEQ_ENTRY |
47 | #undef SLIST_FOREACH_PREVPTR | 47 | #undef CIRCLEQ_FIRST |
48 | #undef SLIST_FOREACH_SAFE | 48 | #undef CIRCLEQ_FOREACH |
49 | #undef SLIST_FIRST | 49 | #undef CIRCLEQ_FOREACH_REVERSE |
50 | #undef SLIST_END | 50 | #undef CIRCLEQ_HEAD |
51 | #undef SLIST_EMPTY | 51 | #undef CIRCLEQ_HEAD_INITIALIZER |
52 | #undef SLIST_NEXT | 52 | #undef CIRCLEQ_INIT |
53 | #undef SLIST_FOREACH | 53 | #undef CIRCLEQ_INSERT_AFTER |
54 | #undef SLIST_INIT | 54 | #undef CIRCLEQ_INSERT_BEFORE |
55 | #undef SLIST_INSERT_AFTER | 55 | #undef CIRCLEQ_INSERT_HEAD |
56 | #undef SLIST_INSERT_HEAD | 56 | #undef CIRCLEQ_INSERT_TAIL |
57 | #undef SLIST_REMOVE_HEAD | 57 | #undef CIRCLEQ_LAST |
58 | #undef SLIST_REMOVE_AFTER | 58 | #undef CIRCLEQ_NEXT |
59 | #undef SLIST_REMOVE | 59 | #undef CIRCLEQ_PREV |
60 | #undef SLIST_REMOVE_NEXT | 60 | #undef CIRCLEQ_REMOVE |
61 | #undef LIST_HEAD | 61 | #undef CIRCLEQ_REPLACE |
62 | #undef LIST_HEAD_INITIALIZER | 62 | #undef LIST_EMPTY |
63 | #undef LIST_END | ||
63 | #undef LIST_ENTRY | 64 | #undef LIST_ENTRY |
64 | #undef LIST_FIRST | 65 | #undef LIST_FIRST |
65 | #undef LIST_END | ||
66 | #undef LIST_EMPTY | ||
67 | #undef LIST_NEXT | ||
68 | #undef LIST_FOREACH | 66 | #undef LIST_FOREACH |
69 | #undef LIST_FOREACH_SAFE | 67 | #undef LIST_FOREACH_SAFE |
68 | #undef LIST_HEAD | ||
69 | #undef LIST_HEAD_INITIALIZER | ||
70 | #undef LIST_INIT | 70 | #undef LIST_INIT |
71 | #undef LIST_INSERT_AFTER | 71 | #undef LIST_INSERT_AFTER |
72 | #undef LIST_INSERT_BEFORE | 72 | #undef LIST_INSERT_BEFORE |
73 | #undef LIST_INSERT_HEAD | 73 | #undef LIST_INSERT_HEAD |
74 | #undef LIST_NEXT | ||
74 | #undef LIST_REMOVE | 75 | #undef LIST_REMOVE |
75 | #undef LIST_REPLACE | 76 | #undef LIST_REPLACE |
76 | #undef SIMPLEQ_HEAD | 77 | #undef SIMPLEQ_CONCAT |
77 | #undef SIMPLEQ_HEAD_INITIALIZER | 78 | #undef SIMPLEQ_EMPTY |
79 | #undef SIMPLEQ_END | ||
78 | #undef SIMPLEQ_ENTRY | 80 | #undef SIMPLEQ_ENTRY |
79 | #undef SIMPLEQ_FIRST | 81 | #undef SIMPLEQ_FIRST |
80 | #undef SIMPLEQ_END | ||
81 | #undef SIMPLEQ_EMPTY | ||
82 | #undef SIMPLEQ_NEXT | ||
83 | #undef SIMPLEQ_FOREACH | 82 | #undef SIMPLEQ_FOREACH |
84 | #undef SIMPLEQ_FOREACH_SAFE | 83 | #undef SIMPLEQ_FOREACH_SAFE |
84 | #undef SIMPLEQ_HEAD | ||
85 | #undef SIMPLEQ_HEAD_INITIALIZER | ||
85 | #undef SIMPLEQ_INIT | 86 | #undef SIMPLEQ_INIT |
87 | #undef SIMPLEQ_INSERT_AFTER | ||
86 | #undef SIMPLEQ_INSERT_HEAD | 88 | #undef SIMPLEQ_INSERT_HEAD |
87 | #undef SIMPLEQ_INSERT_TAIL | 89 | #undef SIMPLEQ_INSERT_TAIL |
88 | #undef SIMPLEQ_INSERT_AFTER | 90 | #undef SIMPLEQ_NEXT |
91 | #undef SIMPLEQ_REMOVE_AFTER | ||
89 | #undef SIMPLEQ_REMOVE_HEAD | 92 | #undef SIMPLEQ_REMOVE_HEAD |
90 | #undef TAILQ_HEAD | 93 | #undef SLIST_EMPTY |
91 | #undef TAILQ_HEAD_INITIALIZER | 94 | #undef SLIST_END |
95 | #undef SLIST_ENTRY | ||
96 | #undef SLIST_FIRST | ||
97 | #undef SLIST_FOREACH | ||
98 | #undef SLIST_FOREACH_PREVPTR | ||
99 | #undef SLIST_FOREACH_SAFE | ||
100 | #undef SLIST_HEAD | ||
101 | #undef SLIST_HEAD_INITIALIZER | ||
102 | #undef SLIST_INIT | ||
103 | #undef SLIST_INSERT_AFTER | ||
104 | #undef SLIST_INSERT_HEAD | ||
105 | #undef SLIST_NEXT | ||
106 | #undef SLIST_REMOVE | ||
107 | #undef SLIST_REMOVE_AFTER | ||
108 | #undef SLIST_REMOVE_HEAD | ||
109 | #undef SLIST_REMOVE_NEXT | ||
110 | #undef TAILQ_CONCAT | ||
111 | #undef TAILQ_EMPTY | ||
112 | #undef TAILQ_END | ||
92 | #undef TAILQ_ENTRY | 113 | #undef TAILQ_ENTRY |
93 | #undef TAILQ_FIRST | 114 | #undef TAILQ_FIRST |
94 | #undef TAILQ_END | ||
95 | #undef TAILQ_NEXT | ||
96 | #undef TAILQ_LAST | ||
97 | #undef TAILQ_PREV | ||
98 | #undef TAILQ_EMPTY | ||
99 | #undef TAILQ_FOREACH | 115 | #undef TAILQ_FOREACH |
100 | #undef TAILQ_FOREACH_REVERSE | 116 | #undef TAILQ_FOREACH_REVERSE |
101 | #undef TAILQ_FOREACH_SAFE | ||
102 | #undef TAILQ_FOREACH_REVERSE_SAFE | 117 | #undef TAILQ_FOREACH_REVERSE_SAFE |
118 | #undef TAILQ_FOREACH_SAFE | ||
119 | #undef TAILQ_HEAD | ||
120 | #undef TAILQ_HEAD_INITIALIZER | ||
103 | #undef TAILQ_INIT | 121 | #undef TAILQ_INIT |
104 | #undef TAILQ_INSERT_HEAD | ||
105 | #undef TAILQ_INSERT_TAIL | ||
106 | #undef TAILQ_INSERT_AFTER | 122 | #undef TAILQ_INSERT_AFTER |
107 | #undef TAILQ_INSERT_BEFORE | 123 | #undef TAILQ_INSERT_BEFORE |
124 | #undef TAILQ_INSERT_HEAD | ||
125 | #undef TAILQ_INSERT_TAIL | ||
126 | #undef TAILQ_LAST | ||
127 | #undef TAILQ_NEXT | ||
128 | #undef TAILQ_PREV | ||
108 | #undef TAILQ_REMOVE | 129 | #undef TAILQ_REMOVE |
109 | #undef TAILQ_REPLACE | 130 | #undef TAILQ_REPLACE |
110 | #undef CIRCLEQ_HEAD | ||
111 | #undef CIRCLEQ_HEAD_INITIALIZER | ||
112 | #undef CIRCLEQ_ENTRY | ||
113 | #undef CIRCLEQ_FIRST | ||
114 | #undef CIRCLEQ_LAST | ||
115 | #undef CIRCLEQ_END | ||
116 | #undef CIRCLEQ_NEXT | ||
117 | #undef CIRCLEQ_PREV | ||
118 | #undef CIRCLEQ_EMPTY | ||
119 | #undef CIRCLEQ_FOREACH | ||
120 | #undef CIRCLEQ_FOREACH_REVERSE | ||
121 | #undef CIRCLEQ_INIT | ||
122 | #undef CIRCLEQ_INSERT_AFTER | ||
123 | #undef CIRCLEQ_INSERT_BEFORE | ||
124 | #undef CIRCLEQ_INSERT_HEAD | ||
125 | #undef CIRCLEQ_INSERT_TAIL | ||
126 | #undef CIRCLEQ_REMOVE | ||
127 | #undef CIRCLEQ_REPLACE | ||
128 | 131 | ||
129 | /* | 132 | /* |
130 | * This file defines five types of data structures: singly-linked lists, | 133 | * This file defines five types of data structures: singly-linked lists, |
131 | * lists, simple queues, tail queues, and circular queues. | 134 | * lists, simple queues, tail queues and XOR simple queues. |
132 | * | 135 | * |
133 | * | 136 | * |
134 | * A singly-linked list is headed by a single forward pointer. The elements | 137 | * A singly-linked list is headed by a single forward pointer. The elements |
@@ -148,7 +151,7 @@ | |||
148 | * or after an existing element or at the head of the list. A list | 151 | * or after an existing element or at the head of the list. A list |
149 | * may only be traversed in the forward direction. | 152 | * may only be traversed in the forward direction. |
150 | * | 153 | * |
151 | * A simple queue is headed by a pair of pointers, one the head of the | 154 | * A simple queue is headed by a pair of pointers, one to the head of the |
152 | * list and the other to the tail of the list. The elements are singly | 155 | * list and the other to the tail of the list. The elements are singly |
153 | * linked to save space, so elements can only be removed from the | 156 | * linked to save space, so elements can only be removed from the |
154 | * head of the list. New elements can be added to the list before or after | 157 | * head of the list. New elements can be added to the list before or after |
@@ -162,19 +165,17 @@ | |||
162 | * after an existing element, at the head of the list, or at the end of | 165 | * after an existing element, at the head of the list, or at the end of |
163 | * the list. A tail queue may be traversed in either direction. | 166 | * the list. A tail queue may be traversed in either direction. |
164 | * | 167 | * |
165 | * A circle queue is headed by a pair of pointers, one to the head of the | 168 | * An XOR simple queue is used in the same way as a regular simple queue. |
166 | * list and the other to the tail of the list. The elements are doubly | 169 | * The difference is that the head structure also includes a "cookie" that |
167 | * linked so that an arbitrary element can be removed without a need to | 170 | * is XOR'd with the queue pointer (first, last or next) to generate the |
168 | * traverse the list. New elements can be added to the list before or after | 171 | * real pointer value. |
169 | * an existing element, at the head of the list, or at the end of the list. | ||
170 | * A circle queue may be traversed in either direction, but has a more | ||
171 | * complex end of list detection. | ||
172 | * | 172 | * |
173 | * For details on the use of these macros, see the queue(3) manual page. | 173 | * For details on the use of these macros, see the queue(3) manual page. |
174 | */ | 174 | */ |
175 | 175 | ||
176 | #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) | 176 | #if defined(QUEUE_MACRO_DEBUG) || (defined(_KERNEL) && defined(DIAGNOSTIC)) |
177 | #define _Q_INVALIDATE(a) (a) = ((void *)-1) | 177 | #define _Q_INVALID ((void *)-1) |
178 | #define _Q_INVALIDATE(a) (a) = _Q_INVALID | ||
178 | #else | 179 | #else |
179 | #define _Q_INVALIDATE(a) | 180 | #define _Q_INVALIDATE(a) |
180 | #endif | 181 | #endif |
@@ -186,15 +187,15 @@ | |||
186 | struct name { \ | 187 | struct name { \ |
187 | struct type *slh_first; /* first element */ \ | 188 | struct type *slh_first; /* first element */ \ |
188 | } | 189 | } |
189 | 190 | ||
190 | #define SLIST_HEAD_INITIALIZER(head) \ | 191 | #define SLIST_HEAD_INITIALIZER(head) \ |
191 | { NULL } | 192 | { NULL } |
192 | 193 | ||
193 | #define SLIST_ENTRY(type) \ | 194 | #define SLIST_ENTRY(type) \ |
194 | struct { \ | 195 | struct { \ |
195 | struct type *sle_next; /* next element */ \ | 196 | struct type *sle_next; /* next element */ \ |
196 | } | 197 | } |
197 | 198 | ||
198 | /* | 199 | /* |
199 | * Singly-linked List access methods. | 200 | * Singly-linked List access methods. |
200 | */ | 201 | */ |
@@ -248,8 +249,8 @@ struct { \ | |||
248 | curelm = curelm->field.sle_next; \ | 249 | curelm = curelm->field.sle_next; \ |
249 | curelm->field.sle_next = \ | 250 | curelm->field.sle_next = \ |
250 | curelm->field.sle_next->field.sle_next; \ | 251 | curelm->field.sle_next->field.sle_next; \ |
251 | _Q_INVALIDATE((elm)->field.sle_next); \ | ||
252 | } \ | 252 | } \ |
253 | _Q_INVALIDATE((elm)->field.sle_next); \ | ||
253 | } while (0) | 254 | } while (0) |
254 | 255 | ||
255 | /* | 256 | /* |
@@ -270,7 +271,7 @@ struct { \ | |||
270 | } | 271 | } |
271 | 272 | ||
272 | /* | 273 | /* |
273 | * List access methods | 274 | * List access methods. |
274 | */ | 275 | */ |
275 | #define LIST_FIRST(head) ((head)->lh_first) | 276 | #define LIST_FIRST(head) ((head)->lh_first) |
276 | #define LIST_END(head) NULL | 277 | #define LIST_END(head) NULL |
@@ -407,6 +408,94 @@ struct { \ | |||
407 | (head)->sqh_last = &(elm)->field.sqe_next; \ | 408 | (head)->sqh_last = &(elm)->field.sqe_next; \ |
408 | } while (0) | 409 | } while (0) |
409 | 410 | ||
411 | #define SIMPLEQ_CONCAT(head1, head2) do { \ | ||
412 | if (!SIMPLEQ_EMPTY((head2))) { \ | ||
413 | *(head1)->sqh_last = (head2)->sqh_first; \ | ||
414 | (head1)->sqh_last = (head2)->sqh_last; \ | ||
415 | SIMPLEQ_INIT((head2)); \ | ||
416 | } \ | ||
417 | } while (0) | ||
418 | |||
419 | /* | ||
420 | * XOR Simple queue definitions. | ||
421 | */ | ||
422 | #define XSIMPLEQ_HEAD(name, type) \ | ||
423 | struct name { \ | ||
424 | struct type *sqx_first; /* first element */ \ | ||
425 | struct type **sqx_last; /* addr of last next element */ \ | ||
426 | unsigned long sqx_cookie; \ | ||
427 | } | ||
428 | |||
429 | #define XSIMPLEQ_ENTRY(type) \ | ||
430 | struct { \ | ||
431 | struct type *sqx_next; /* next element */ \ | ||
432 | } | ||
433 | |||
434 | /* | ||
435 | * XOR Simple queue access methods. | ||
436 | */ | ||
437 | #define XSIMPLEQ_XOR(head, ptr) ((__typeof(ptr))((head)->sqx_cookie ^ \ | ||
438 | (unsigned long)(ptr))) | ||
439 | #define XSIMPLEQ_FIRST(head) XSIMPLEQ_XOR(head, ((head)->sqx_first)) | ||
440 | #define XSIMPLEQ_END(head) NULL | ||
441 | #define XSIMPLEQ_EMPTY(head) (XSIMPLEQ_FIRST(head) == XSIMPLEQ_END(head)) | ||
442 | #define XSIMPLEQ_NEXT(head, elm, field) XSIMPLEQ_XOR(head, ((elm)->field.sqx_next)) | ||
443 | |||
444 | |||
445 | #define XSIMPLEQ_FOREACH(var, head, field) \ | ||
446 | for ((var) = XSIMPLEQ_FIRST(head); \ | ||
447 | (var) != XSIMPLEQ_END(head); \ | ||
448 | (var) = XSIMPLEQ_NEXT(head, var, field)) | ||
449 | |||
450 | #define XSIMPLEQ_FOREACH_SAFE(var, head, field, tvar) \ | ||
451 | for ((var) = XSIMPLEQ_FIRST(head); \ | ||
452 | (var) && ((tvar) = XSIMPLEQ_NEXT(head, var, field), 1); \ | ||
453 | (var) = (tvar)) | ||
454 | |||
455 | /* | ||
456 | * XOR Simple queue functions. | ||
457 | */ | ||
458 | #define XSIMPLEQ_INIT(head) do { \ | ||
459 | arc4random_buf(&(head)->sqx_cookie, sizeof((head)->sqx_cookie)); \ | ||
460 | (head)->sqx_first = XSIMPLEQ_XOR(head, NULL); \ | ||
461 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ | ||
462 | } while (0) | ||
463 | |||
464 | #define XSIMPLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
465 | if (((elm)->field.sqx_next = (head)->sqx_first) == \ | ||
466 | XSIMPLEQ_XOR(head, NULL)) \ | ||
467 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
468 | (head)->sqx_first = XSIMPLEQ_XOR(head, (elm)); \ | ||
469 | } while (0) | ||
470 | |||
471 | #define XSIMPLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
472 | (elm)->field.sqx_next = XSIMPLEQ_XOR(head, NULL); \ | ||
473 | *(XSIMPLEQ_XOR(head, (head)->sqx_last)) = XSIMPLEQ_XOR(head, (elm)); \ | ||
474 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
475 | } while (0) | ||
476 | |||
477 | #define XSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
478 | if (((elm)->field.sqx_next = (listelm)->field.sqx_next) == \ | ||
479 | XSIMPLEQ_XOR(head, NULL)) \ | ||
480 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
481 | (listelm)->field.sqx_next = XSIMPLEQ_XOR(head, (elm)); \ | ||
482 | } while (0) | ||
483 | |||
484 | #define XSIMPLEQ_REMOVE_HEAD(head, field) do { \ | ||
485 | if (((head)->sqx_first = XSIMPLEQ_XOR(head, \ | ||
486 | (head)->sqx_first)->field.sqx_next) == XSIMPLEQ_XOR(head, NULL)) \ | ||
487 | (head)->sqx_last = XSIMPLEQ_XOR(head, &(head)->sqx_first); \ | ||
488 | } while (0) | ||
489 | |||
490 | #define XSIMPLEQ_REMOVE_AFTER(head, elm, field) do { \ | ||
491 | if (((elm)->field.sqx_next = XSIMPLEQ_XOR(head, \ | ||
492 | (elm)->field.sqx_next)->field.sqx_next) \ | ||
493 | == XSIMPLEQ_XOR(head, NULL)) \ | ||
494 | (head)->sqx_last = \ | ||
495 | XSIMPLEQ_XOR(head, &(elm)->field.sqx_next); \ | ||
496 | } while (0) | ||
497 | |||
498 | |||
410 | /* | 499 | /* |
411 | * Tail queue definitions. | 500 | * Tail queue definitions. |
412 | */ | 501 | */ |
@@ -425,8 +514,8 @@ struct { \ | |||
425 | struct type **tqe_prev; /* address of previous next element */ \ | 514 | struct type **tqe_prev; /* address of previous next element */ \ |
426 | } | 515 | } |
427 | 516 | ||
428 | /* | 517 | /* |
429 | * tail queue access methods | 518 | * Tail queue access methods. |
430 | */ | 519 | */ |
431 | #define TAILQ_FIRST(head) ((head)->tqh_first) | 520 | #define TAILQ_FIRST(head) ((head)->tqh_first) |
432 | #define TAILQ_END(head) NULL | 521 | #define TAILQ_END(head) NULL |
@@ -527,133 +616,13 @@ struct { \ | |||
527 | _Q_INVALIDATE((elm)->field.tqe_next); \ | 616 | _Q_INVALIDATE((elm)->field.tqe_next); \ |
528 | } while (0) | 617 | } while (0) |
529 | 618 | ||
530 | /* | 619 | #define TAILQ_CONCAT(head1, head2, field) do { \ |
531 | * Circular queue definitions. | 620 | if (!TAILQ_EMPTY(head2)) { \ |
532 | */ | 621 | *(head1)->tqh_last = (head2)->tqh_first; \ |
533 | #define CIRCLEQ_HEAD(name, type) \ | 622 | (head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \ |
534 | struct name { \ | 623 | (head1)->tqh_last = (head2)->tqh_last; \ |
535 | struct type *cqh_first; /* first element */ \ | 624 | TAILQ_INIT((head2)); \ |
536 | struct type *cqh_last; /* last element */ \ | 625 | } \ |
537 | } | ||
538 | |||
539 | #define CIRCLEQ_HEAD_INITIALIZER(head) \ | ||
540 | { CIRCLEQ_END(&head), CIRCLEQ_END(&head) } | ||
541 | |||
542 | #define CIRCLEQ_ENTRY(type) \ | ||
543 | struct { \ | ||
544 | struct type *cqe_next; /* next element */ \ | ||
545 | struct type *cqe_prev; /* previous element */ \ | ||
546 | } | ||
547 | |||
548 | /* | ||
549 | * Circular queue access methods | ||
550 | */ | ||
551 | #define CIRCLEQ_FIRST(head) ((head)->cqh_first) | ||
552 | #define CIRCLEQ_LAST(head) ((head)->cqh_last) | ||
553 | #define CIRCLEQ_END(head) ((void *)(head)) | ||
554 | #define CIRCLEQ_NEXT(elm, field) ((elm)->field.cqe_next) | ||
555 | #define CIRCLEQ_PREV(elm, field) ((elm)->field.cqe_prev) | ||
556 | #define CIRCLEQ_EMPTY(head) \ | ||
557 | (CIRCLEQ_FIRST(head) == CIRCLEQ_END(head)) | ||
558 | |||
559 | #define CIRCLEQ_FOREACH(var, head, field) \ | ||
560 | for((var) = CIRCLEQ_FIRST(head); \ | ||
561 | (var) != CIRCLEQ_END(head); \ | ||
562 | (var) = CIRCLEQ_NEXT(var, field)) | ||
563 | |||
564 | #define CIRCLEQ_FOREACH_SAFE(var, head, field, tvar) \ | ||
565 | for ((var) = CIRCLEQ_FIRST(head); \ | ||
566 | (var) != CIRCLEQ_END(head) && \ | ||
567 | ((tvar) = CIRCLEQ_NEXT(var, field), 1); \ | ||
568 | (var) = (tvar)) | ||
569 | |||
570 | #define CIRCLEQ_FOREACH_REVERSE(var, head, field) \ | ||
571 | for((var) = CIRCLEQ_LAST(head); \ | ||
572 | (var) != CIRCLEQ_END(head); \ | ||
573 | (var) = CIRCLEQ_PREV(var, field)) | ||
574 | |||
575 | #define CIRCLEQ_FOREACH_REVERSE_SAFE(var, head, headname, field, tvar) \ | ||
576 | for ((var) = CIRCLEQ_LAST(head, headname); \ | ||
577 | (var) != CIRCLEQ_END(head) && \ | ||
578 | ((tvar) = CIRCLEQ_PREV(var, headname, field), 1); \ | ||
579 | (var) = (tvar)) | ||
580 | |||
581 | /* | ||
582 | * Circular queue functions. | ||
583 | */ | ||
584 | #define CIRCLEQ_INIT(head) do { \ | ||
585 | (head)->cqh_first = CIRCLEQ_END(head); \ | ||
586 | (head)->cqh_last = CIRCLEQ_END(head); \ | ||
587 | } while (0) | ||
588 | |||
589 | #define CIRCLEQ_INSERT_AFTER(head, listelm, elm, field) do { \ | ||
590 | (elm)->field.cqe_next = (listelm)->field.cqe_next; \ | ||
591 | (elm)->field.cqe_prev = (listelm); \ | ||
592 | if ((listelm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
593 | (head)->cqh_last = (elm); \ | ||
594 | else \ | ||
595 | (listelm)->field.cqe_next->field.cqe_prev = (elm); \ | ||
596 | (listelm)->field.cqe_next = (elm); \ | ||
597 | } while (0) | ||
598 | |||
599 | #define CIRCLEQ_INSERT_BEFORE(head, listelm, elm, field) do { \ | ||
600 | (elm)->field.cqe_next = (listelm); \ | ||
601 | (elm)->field.cqe_prev = (listelm)->field.cqe_prev; \ | ||
602 | if ((listelm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
603 | (head)->cqh_first = (elm); \ | ||
604 | else \ | ||
605 | (listelm)->field.cqe_prev->field.cqe_next = (elm); \ | ||
606 | (listelm)->field.cqe_prev = (elm); \ | ||
607 | } while (0) | ||
608 | |||
609 | #define CIRCLEQ_INSERT_HEAD(head, elm, field) do { \ | ||
610 | (elm)->field.cqe_next = (head)->cqh_first; \ | ||
611 | (elm)->field.cqe_prev = CIRCLEQ_END(head); \ | ||
612 | if ((head)->cqh_last == CIRCLEQ_END(head)) \ | ||
613 | (head)->cqh_last = (elm); \ | ||
614 | else \ | ||
615 | (head)->cqh_first->field.cqe_prev = (elm); \ | ||
616 | (head)->cqh_first = (elm); \ | ||
617 | } while (0) | ||
618 | |||
619 | #define CIRCLEQ_INSERT_TAIL(head, elm, field) do { \ | ||
620 | (elm)->field.cqe_next = CIRCLEQ_END(head); \ | ||
621 | (elm)->field.cqe_prev = (head)->cqh_last; \ | ||
622 | if ((head)->cqh_first == CIRCLEQ_END(head)) \ | ||
623 | (head)->cqh_first = (elm); \ | ||
624 | else \ | ||
625 | (head)->cqh_last->field.cqe_next = (elm); \ | ||
626 | (head)->cqh_last = (elm); \ | ||
627 | } while (0) | ||
628 | |||
629 | #define CIRCLEQ_REMOVE(head, elm, field) do { \ | ||
630 | if ((elm)->field.cqe_next == CIRCLEQ_END(head)) \ | ||
631 | (head)->cqh_last = (elm)->field.cqe_prev; \ | ||
632 | else \ | ||
633 | (elm)->field.cqe_next->field.cqe_prev = \ | ||
634 | (elm)->field.cqe_prev; \ | ||
635 | if ((elm)->field.cqe_prev == CIRCLEQ_END(head)) \ | ||
636 | (head)->cqh_first = (elm)->field.cqe_next; \ | ||
637 | else \ | ||
638 | (elm)->field.cqe_prev->field.cqe_next = \ | ||
639 | (elm)->field.cqe_next; \ | ||
640 | _Q_INVALIDATE((elm)->field.cqe_prev); \ | ||
641 | _Q_INVALIDATE((elm)->field.cqe_next); \ | ||
642 | } while (0) | ||
643 | |||
644 | #define CIRCLEQ_REPLACE(head, elm, elm2, field) do { \ | ||
645 | if (((elm2)->field.cqe_next = (elm)->field.cqe_next) == \ | ||
646 | CIRCLEQ_END(head)) \ | ||
647 | (head).cqh_last = (elm2); \ | ||
648 | else \ | ||
649 | (elm2)->field.cqe_next->field.cqe_prev = (elm2); \ | ||
650 | if (((elm2)->field.cqe_prev = (elm)->field.cqe_prev) == \ | ||
651 | CIRCLEQ_END(head)) \ | ||
652 | (head).cqh_first = (elm2); \ | ||
653 | else \ | ||
654 | (elm2)->field.cqe_prev->field.cqe_next = (elm2); \ | ||
655 | _Q_INVALIDATE((elm)->field.cqe_prev); \ | ||
656 | _Q_INVALIDATE((elm)->field.cqe_next); \ | ||
657 | } while (0) | 626 | } while (0) |
658 | 627 | ||
659 | #endif /* !_FAKE_QUEUE_H_ */ | 628 | #endif /* !_SYS_QUEUE_H_ */ |