2 * Copyright (c) 2010, JANET(UK)
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
16 * 3. Neither the name of JANET(UK) 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.
20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 * AND 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 COPYRIGHT HOLDER 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
33 * Copyright 1993 by OpenVision Technologies, Inc.
35 * Permission to use, copy, modify, distribute, and sell this software
36 * and its documentation for any purpose is hereby granted without fee,
37 * provided that the above copyright notice appears in all copies and
38 * that both that copyright notice and this permission notice appear in
39 * supporting documentation, and that the name of OpenVision not be used
40 * in advertising or publicity pertaining to distribution of the software
41 * without specific, written prior permission. OpenVision makes no
42 * representations about the suitability of this software for any
43 * purpose. It is provided "as is" without express or implied warranty.
45 * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
46 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
47 * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
48 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
49 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
50 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
51 * PERFORMANCE OF THIS SOFTWARE.
55 * $Id: util_ordering.c 23457 2009-12-08 00:04:48Z tlyu $
59 * functions to check sequence numbers for replay and sequencing
62 #include "gssapiP_eap.h"
64 #define QUEUE_LENGTH 20
66 typedef struct _queue {
72 /* Stored as deltas from firstnum. This way, the high bit won't
73 overflow unless we've actually gone through 2**n messages, or
74 gotten something *way* out of sequence. */
75 uint64_t elem[QUEUE_LENGTH];
76 /* All ones for 64-bit sequence numbers; 32 ones for 32-bit
82 * - the queue is a circular queue. The first element (q->elem[q->start])
83 * is the oldest. The last element is the newest.
86 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0]))
87 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)])
90 queue_insert(queue *q, int after, uint64_t seqnum)
92 /* insert. this is not the fastest way, but it's easy, and it's
93 optimized for insert at end, which is the common case */
96 /* common case: at end, after == q->start+q->length-1 */
98 /* move all the elements (after,last] up one slot */
100 for (i=q->start+q->length-1; i>after; i--)
101 QELEM(q,i+1) = QELEM(q,i);
103 /* fill in slot after+1 */
105 QELEM(q,after+1) = seqnum;
107 /* Either increase the length by one, or move the starting point up
108 one (deleting the first element, which got bashed above), as
111 if (q->length == QSIZE(q)) {
113 if (q->start == QSIZE(q))
121 sequenceInit(void **vqueue, uint64_t seqnum,
122 int do_replay, int do_sequence, int wide_nums)
126 if ((q = (queue *) GSSEAP_MALLOC(sizeof(queue))) == NULL)
129 /* This stops valgrind from complaining about writing uninitialized
130 data if the caller exports the context and writes it to a file.
131 We don't actually use those bytes at all, but valgrind still
133 memset(q, 0xfe, sizeof(*q));
135 q->do_replay = do_replay;
136 q->do_sequence = do_sequence;
137 q->mask = wide_nums ? ~(uint64_t)0 : 0xffffffffUL;
141 q->firstnum = seqnum;
142 q->elem[q->start] = ((uint64_t)0 - 1) & q->mask;
144 *vqueue = (void *) q;
149 sequenceCheck(void **vqueue, uint64_t seqnum)
155 q = (queue *) (*vqueue);
157 if (!q->do_replay && !q->do_sequence)
158 return(GSS_S_COMPLETE);
160 /* All checks are done relative to the initial sequence number, to
161 avoid (or at least put off) the pain of wrapping. */
162 seqnum -= q->firstnum;
163 /* If we're only doing 32-bit values, adjust for that again.
165 Note that this will probably be the wrong thing to if we get
166 2**32 messages sent with 32-bit sequence numbers. */
169 /* rule 1: expected sequence number */
171 expected = (QELEM(q,q->start+q->length-1)+1) & q->mask;
172 if (seqnum == expected) {
173 queue_insert(q, q->start+q->length-1, seqnum);
174 return(GSS_S_COMPLETE);
177 /* rule 2: > expected sequence number */
179 if ((seqnum > expected)) {
180 queue_insert(q, q->start+q->length-1, seqnum);
181 if (q->do_replay && !q->do_sequence)
182 return(GSS_S_COMPLETE);
184 return(GSS_S_GAP_TOKEN);
187 /* rule 3: seqnum < seqnum(first) */
189 if ((seqnum < QELEM(q,q->start)) &&
190 /* Is top bit of whatever width we're using set?
192 We used to check for greater than or equal to firstnum, but
193 (1) we've since switched to compute values relative to
194 firstnum, so the lowest we can have is 0, and (2) the effect
195 of the original scheme was highly dependent on whether
196 firstnum was close to either side of 0. (Consider
197 firstnum==0xFFFFFFFE and we miss three packets; the next
198 packet is *new* but would look old.)
200 This check should give us 2**31 or 2**63 messages "new", and
201 just as many "old". That's not quite right either. */
202 (seqnum & (1 + (q->mask >> 1)))
204 if (q->do_replay && !q->do_sequence)
205 return(GSS_S_OLD_TOKEN);
207 return(GSS_S_UNSEQ_TOKEN);
210 /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */
213 if (seqnum == QELEM(q,q->start+q->length-1))
214 return(GSS_S_DUPLICATE_TOKEN);
216 for (i=q->start; i<q->start+q->length-1; i++) {
217 if (seqnum == QELEM(q,i))
218 return(GSS_S_DUPLICATE_TOKEN);
219 if ((seqnum > QELEM(q,i)) && (seqnum < QELEM(q,i+1))) {
220 queue_insert(q, i, seqnum);
221 if (q->do_replay && !q->do_sequence)
222 return(GSS_S_COMPLETE);
224 return(GSS_S_UNSEQ_TOKEN);
229 /* this should never happen */
230 return(GSS_S_FAILURE);
234 sequenceFree(void **vqueue)
238 q = (queue *) (*vqueue);
246 * These support functions are for the serialization routines
249 sequenceSize(void *vqueue)
251 return sizeof(queue);
255 sequenceExternalize(void *vqueue, unsigned char **buf, size_t *lenremain)
257 if (*lenremain < sizeof(queue))
259 memcpy(*buf, vqueue, sizeof(queue));
260 *buf += sizeof(queue);
261 *lenremain -= sizeof(queue);
267 sequenceInternalize(void **vqueue, unsigned char **buf, size_t *lenremain)
271 if (*lenremain < sizeof(queue))
273 if ((q = GSSEAP_MALLOC(sizeof(queue))) == 0)
275 memcpy(q, *buf, sizeof(queue));
276 *buf += sizeof(queue);
277 *lenremain -= sizeof(queue);