1 /*
2 * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
3 * Use is subject to license terms.
4 */
5
6
7 /*
8 * Copyright 1993 by OpenVision Technologies, Inc.
9 *
10 * Permission to use, copy, modify, distribute, and sell this software
11 * and its documentation for any purpose is hereby granted without fee,
12 * provided that the above copyright notice appears in all copies and
13 * that both that copyright notice and this permission notice appear in
14 * supporting documentation, and that the name of OpenVision not be used
15 * in advertising or publicity pertaining to distribution of the software
16 * without specific, written prior permission. OpenVision makes no
17 * representations about the suitability of this software for any
18 * purpose. It is provided "as is" without express or implied warranty.
19 *
20 * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
21 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
22 * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
23 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
24 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
25 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
26 * PERFORMANCE OF THIS SOFTWARE.
27 */
28
29 /*
30 * $Id: util_ordering.c 19310 2007-03-29 21:36:38Z tlyu $
31 */
32
33 /*
34 * SUNW15resync
35 * Left this alone (MIT version causes STC gss_verify_mic(6) test failure)
36 * as it has bug fixes that MIT does not yet.
37 */
38
39 /*
40 * functions to check sequence numbers for replay and sequencing
41 */
42
43 #include "mechglueP.h"
44 #include "gssapiP_generic.h"
45
46 #define QUEUE_LENGTH 20
47
48 typedef struct _queue {
49 int do_replay;
50 int do_sequence;
51 int start;
52 int length;
53 gssint_uint64 firstnum;
54 gssint_uint64 elem[QUEUE_LENGTH];
55 gssint_uint64 mask;
56 } queue;
57
58 /* rep invariant:
59 * - the queue is a circular queue. The first element (q->elem[q->start])
60 * is the oldest. The last element is the newest.
61 */
62
63 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0]))
64 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)])
65
66 /*
67 * mask(max) is 2 ** 64 - 1, and half is 2 ** 63.
68 * |-------------------------------|-----------------------------|
69 * 0 half mask
70 * |-------------------------------|
71 * half range ( 2 ** 63 )
72 *
73 * Here, the distance between n1 and n2 is used, if it falls
74 * in the "half range", normal integer comparison is enough.
75 *
76 * If the distance is bigger than half of the range, one of them must
77 * have passed the 'mask' point while the other one didn't. In this
78 * case, the result should be the reverse of normal comparison, i.e.
79 * the smaller one is considered bigger.
80 *
81 * If we shift the smaller value by adding 'mask' to it,
82 * the distance will be in half range again.
83 *
84 * The assumption is that the out of order event will not
85 * happen too often. If the distance is really bigger than half range,
86 * (1 is expected, but half + 2 arrives) we really don't know if it's a
87 * GAP token or an OLD token that wrapped.
88 */
89 static int
after(gssint_uint64 n1,gssint_uint64 n2,gssint_uint64 mask)90 after(gssint_uint64 n1, gssint_uint64 n2, gssint_uint64 mask)
91 {
92 int bigger;
93 gssint_uint64 diff;
94 gssint_uint64 half;
95
96 /*
97 * rule 1: same number.
98 * This may be ambiguous, but the caller of this function,
99 * g_order_check already takes care of it.
100 */
101 if (n1 == n2)
102 return (0);
103
104 half = 1 + (mask >> 1);
105
106 if (n1 > n2) {
107 diff = n1 - n2;
108 bigger = 1;
109 } else {
110 diff = n2 - n1;
111 bigger = 0;
112 }
113
114 /* rule 2: in the same half range, normal comparison is enough */
115 if (diff < half)
116 return bigger;
117
118 n1 &= half;
119
120 /* rule 3: different half, and n1 is on upper, n2 is bigger */
121 /* rule 4: different half, and n1 is on lower, n1 is bigger */
122 if (n1 != 0)
123 return (0);
124
125 return (1);
126 }
127
128 static void
queue_insert(queue * q,int after,gssint_uint64 seqnum)129 queue_insert(queue *q, int after, gssint_uint64 seqnum)
130 {
131 /* insert. this is not the fastest way, but it's easy, and it's
132 optimized for insert at end, which is the common case */
133 int i;
134
135 /* common case: at end, after == q->start+q->length-1 */
136
137 /* move all the elements (after,last] up one slot */
138
139 for (i=q->start+q->length-1; i>after; i--)
140 QELEM(q,i+1) = QELEM(q,i);
141
142 /* fill in slot after+1 */
143
144 QELEM(q,after+1) = seqnum;
145
146 /* Either increase the length by one, or move the starting point up
147 one (deleting the first element, which got bashed above), as
148 appropriate. */
149
150 if (q->length == QSIZE(q)) {
151 q->start++;
152 if (q->start == QSIZE(q))
153 q->start = 0;
154 } else {
155 q->length++;
156 }
157 }
158
159 gss_int32
g_order_init(void ** vqueue,gssint_uint64 seqnum,int do_replay,int do_sequence,int wide_nums)160 g_order_init(void **vqueue, gssint_uint64 seqnum,
161 int do_replay, int do_sequence, int wide_nums)
162 {
163 queue *q;
164
165 if ((q = (queue *) MALLOC(sizeof(queue))) == NULL)
166 return(ENOMEM);
167
168 q->do_replay = do_replay;
169 q->do_sequence = do_sequence;
170 q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL;
171
172 q->start = 0;
173 q->length = 1;
174 q->firstnum = seqnum;
175 q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask;
176
177 *vqueue = (void *) q;
178 return(0);
179 }
180
181 gss_int32
g_order_check(void ** vqueue,gssint_uint64 seqnum)182 g_order_check(void **vqueue, gssint_uint64 seqnum)
183 {
184 queue *q;
185 int i;
186 gssint_uint64 expected;
187
188 q = (queue *) (*vqueue);
189
190 if (!q->do_replay && !q->do_sequence)
191 return(GSS_S_COMPLETE);
192
193 /* All checks are done relative to the initial sequence number, to
194 avoid (or at least put off) the pain of wrapping. */
195 seqnum -= q->firstnum;
196
197 /*
198 * If we're only doing 32-bit values, adjust for that again.
199 * Note that this will probably be the wrong thing to if we get
200 * 2**32 messages sent with 32-bit sequence numbers.
201 */
202 seqnum &= q->mask;
203
204 /* rule 1: expected sequence number */
205
206 expected = (QELEM(q,q->start+q->length-1)+1) & q->mask;
207 if (seqnum == expected) {
208 queue_insert(q, q->start+q->length-1, seqnum);
209 return(GSS_S_COMPLETE);
210 }
211
212 /* rule 2: > expected sequence number */
213 if (after(seqnum, expected, q->mask)) {
214 queue_insert(q, q->start+q->length-1, seqnum);
215 if (q->do_replay && !q->do_sequence)
216 return(GSS_S_COMPLETE);
217 else
218 return(GSS_S_GAP_TOKEN);
219 }
220
221 /* rule 3: seqnum < seqnum(first) */
222 if (after(QELEM(q,q->start), seqnum, q->mask)) {
223 if (q->do_replay && !q->do_sequence)
224 return(GSS_S_OLD_TOKEN);
225 else
226 return(GSS_S_UNSEQ_TOKEN);
227 }
228
229 /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */
230
231 else {
232 if (seqnum == QELEM(q,q->start+q->length-1))
233 return(GSS_S_DUPLICATE_TOKEN);
234
235 for (i=q->start; i<q->start+q->length-1; i++) {
236 if (seqnum == QELEM(q,i))
237 return (GSS_S_DUPLICATE_TOKEN);
238 if (after(seqnum, QELEM(q,i), q->mask) &&
239 after(QELEM(q,i+1), seqnum, q->mask)) {
240 queue_insert(q, i, seqnum);
241 if (q->do_replay && !q->do_sequence)
242 return (GSS_S_COMPLETE);
243 else
244 return (GSS_S_UNSEQ_TOKEN);
245 }
246 }
247 }
248
249 /* this should never happen */
250 return(GSS_S_FAILURE);
251 }
252
253 void
g_order_free(void ** vqueue)254 g_order_free(void **vqueue)
255 {
256 queue *q;
257
258 q = (queue *) (*vqueue);
259
260 FREE (q, sizeof (queue));
261
262 *vqueue = NULL;
263 }
264
265 /*
266 * These support functions are for the serialization routines
267 */
268
269 /*ARGSUSED*/
270 gss_uint32
g_queue_size(void * vqueue,size_t * sizep)271 g_queue_size(void *vqueue, size_t *sizep)
272 {
273 *sizep += sizeof(queue);
274 return 0;
275 }
276
277 gss_uint32
g_queue_externalize(void * vqueue,unsigned char ** buf,size_t * lenremain)278 g_queue_externalize(void *vqueue, unsigned char **buf, size_t *lenremain)
279 {
280 (void) memcpy(*buf, vqueue, sizeof(queue));
281 *buf += sizeof(queue);
282 *lenremain -= sizeof(queue);
283
284 return 0;
285 }
286
287 gss_uint32
g_queue_internalize(void ** vqueue,unsigned char ** buf,size_t * lenremain)288 g_queue_internalize(void **vqueue, unsigned char **buf, size_t *lenremain)
289 {
290 void *q;
291
292 if ((q = (void *) MALLOC(sizeof(queue))) == 0)
293 return ENOMEM;
294 (void) memcpy(q, *buf, sizeof(queue));
295 *buf += sizeof(queue);
296 *lenremain -= sizeof(queue);
297 *vqueue = q;
298 return 0;
299 }
300