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
48typedef 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 */
89static int
90after(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
128static void
129queue_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
159gss_int32
160g_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
181gss_int32
182g_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
253void
254g_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*/
270gss_uint32
271g_queue_size(void *vqueue, size_t *sizep)
272{
273    *sizep += sizeof(queue);
274    return 0;
275}
276
277gss_uint32
278g_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
287gss_uint32
288g_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