17c478bd9Sstevel@tonic-gate /*
2159d09a2SMark Phalan * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
37c478bd9Sstevel@tonic-gate * Use is subject to license terms.
47c478bd9Sstevel@tonic-gate */
57c478bd9Sstevel@tonic-gate
67c478bd9Sstevel@tonic-gate
77c478bd9Sstevel@tonic-gate /*
87c478bd9Sstevel@tonic-gate * Copyright 1993 by OpenVision Technologies, Inc.
9*55fea89dSDan Cross *
107c478bd9Sstevel@tonic-gate * Permission to use, copy, modify, distribute, and sell this software
117c478bd9Sstevel@tonic-gate * and its documentation for any purpose is hereby granted without fee,
127c478bd9Sstevel@tonic-gate * provided that the above copyright notice appears in all copies and
137c478bd9Sstevel@tonic-gate * that both that copyright notice and this permission notice appear in
147c478bd9Sstevel@tonic-gate * supporting documentation, and that the name of OpenVision not be used
157c478bd9Sstevel@tonic-gate * in advertising or publicity pertaining to distribution of the software
167c478bd9Sstevel@tonic-gate * without specific, written prior permission. OpenVision makes no
177c478bd9Sstevel@tonic-gate * representations about the suitability of this software for any
187c478bd9Sstevel@tonic-gate * purpose. It is provided "as is" without express or implied warranty.
19*55fea89dSDan Cross *
207c478bd9Sstevel@tonic-gate * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
217c478bd9Sstevel@tonic-gate * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
227c478bd9Sstevel@tonic-gate * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR
237c478bd9Sstevel@tonic-gate * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
247c478bd9Sstevel@tonic-gate * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
257c478bd9Sstevel@tonic-gate * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
267c478bd9Sstevel@tonic-gate * PERFORMANCE OF THIS SOFTWARE.
277c478bd9Sstevel@tonic-gate */
287c478bd9Sstevel@tonic-gate
297c478bd9Sstevel@tonic-gate /*
30159d09a2SMark Phalan * $Id: util_ordering.c 19310 2007-03-29 21:36:38Z tlyu $
317c478bd9Sstevel@tonic-gate */
327c478bd9Sstevel@tonic-gate
33ab9b2e15Sgtb /*
34ab9b2e15Sgtb * SUNW15resync
35ab9b2e15Sgtb * Left this alone (MIT version causes STC gss_verify_mic(6) test failure)
36ab9b2e15Sgtb * as it has bug fixes that MIT does not yet.
37ab9b2e15Sgtb */
38ab9b2e15Sgtb
397c478bd9Sstevel@tonic-gate /*
407c478bd9Sstevel@tonic-gate * functions to check sequence numbers for replay and sequencing
417c478bd9Sstevel@tonic-gate */
427c478bd9Sstevel@tonic-gate
43159d09a2SMark Phalan #include "mechglueP.h"
44159d09a2SMark Phalan #include "gssapiP_generic.h"
457c478bd9Sstevel@tonic-gate
467c478bd9Sstevel@tonic-gate #define QUEUE_LENGTH 20
477c478bd9Sstevel@tonic-gate
487c478bd9Sstevel@tonic-gate typedef struct _queue {
497c478bd9Sstevel@tonic-gate int do_replay;
507c478bd9Sstevel@tonic-gate int do_sequence;
517c478bd9Sstevel@tonic-gate int start;
527c478bd9Sstevel@tonic-gate int length;
537c478bd9Sstevel@tonic-gate gssint_uint64 firstnum;
547c478bd9Sstevel@tonic-gate gssint_uint64 elem[QUEUE_LENGTH];
557c478bd9Sstevel@tonic-gate gssint_uint64 mask;
567c478bd9Sstevel@tonic-gate } queue;
577c478bd9Sstevel@tonic-gate
587c478bd9Sstevel@tonic-gate /* rep invariant:
597c478bd9Sstevel@tonic-gate * - the queue is a circular queue. The first element (q->elem[q->start])
607c478bd9Sstevel@tonic-gate * is the oldest. The last element is the newest.
617c478bd9Sstevel@tonic-gate */
627c478bd9Sstevel@tonic-gate
637c478bd9Sstevel@tonic-gate #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0]))
647c478bd9Sstevel@tonic-gate #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)])
657c478bd9Sstevel@tonic-gate
66220c5023Swyllys /*
67220c5023Swyllys * mask(max) is 2 ** 64 - 1, and half is 2 ** 63.
68220c5023Swyllys * |-------------------------------|-----------------------------|
69220c5023Swyllys * 0 half mask
70220c5023Swyllys * |-------------------------------|
71220c5023Swyllys * half range ( 2 ** 63 )
72220c5023Swyllys *
73220c5023Swyllys * Here, the distance between n1 and n2 is used, if it falls
74220c5023Swyllys * in the "half range", normal integer comparison is enough.
75220c5023Swyllys *
76220c5023Swyllys * If the distance is bigger than half of the range, one of them must
77220c5023Swyllys * have passed the 'mask' point while the other one didn't. In this
78220c5023Swyllys * case, the result should be the reverse of normal comparison, i.e.
79220c5023Swyllys * the smaller one is considered bigger.
80220c5023Swyllys *
81220c5023Swyllys * If we shift the smaller value by adding 'mask' to it,
82220c5023Swyllys * the distance will be in half range again.
83220c5023Swyllys *
84220c5023Swyllys * The assumption is that the out of order event will not
85220c5023Swyllys * happen too often. If the distance is really bigger than half range,
86220c5023Swyllys * (1 is expected, but half + 2 arrives) we really don't know if it's a
87220c5023Swyllys * GAP token or an OLD token that wrapped.
88220c5023Swyllys */
89220c5023Swyllys static int
after(gssint_uint64 n1,gssint_uint64 n2,gssint_uint64 mask)90220c5023Swyllys after(gssint_uint64 n1, gssint_uint64 n2, gssint_uint64 mask)
91220c5023Swyllys {
92220c5023Swyllys int bigger;
93220c5023Swyllys gssint_uint64 diff;
94220c5023Swyllys gssint_uint64 half;
95220c5023Swyllys
96220c5023Swyllys /*
97220c5023Swyllys * rule 1: same number.
98220c5023Swyllys * This may be ambiguous, but the caller of this function,
99220c5023Swyllys * g_order_check already takes care of it.
100220c5023Swyllys */
101220c5023Swyllys if (n1 == n2)
102220c5023Swyllys return (0);
103220c5023Swyllys
104220c5023Swyllys half = 1 + (mask >> 1);
105220c5023Swyllys
106220c5023Swyllys if (n1 > n2) {
107220c5023Swyllys diff = n1 - n2;
108220c5023Swyllys bigger = 1;
109220c5023Swyllys } else {
110220c5023Swyllys diff = n2 - n1;
111220c5023Swyllys bigger = 0;
112220c5023Swyllys }
113220c5023Swyllys
114220c5023Swyllys /* rule 2: in the same half range, normal comparison is enough */
115220c5023Swyllys if (diff < half)
116220c5023Swyllys return bigger;
117220c5023Swyllys
118220c5023Swyllys n1 &= half;
119220c5023Swyllys
120220c5023Swyllys /* rule 3: different half, and n1 is on upper, n2 is bigger */
121220c5023Swyllys /* rule 4: different half, and n1 is on lower, n1 is bigger */
122220c5023Swyllys if (n1 != 0)
123220c5023Swyllys return (0);
124220c5023Swyllys
125220c5023Swyllys return (1);
126220c5023Swyllys }
127220c5023Swyllys
1287c478bd9Sstevel@tonic-gate static void
queue_insert(queue * q,int after,gssint_uint64 seqnum)1297c478bd9Sstevel@tonic-gate queue_insert(queue *q, int after, gssint_uint64 seqnum)
1307c478bd9Sstevel@tonic-gate {
1317c478bd9Sstevel@tonic-gate /* insert. this is not the fastest way, but it's easy, and it's
1327c478bd9Sstevel@tonic-gate optimized for insert at end, which is the common case */
1337c478bd9Sstevel@tonic-gate int i;
1347c478bd9Sstevel@tonic-gate
1357c478bd9Sstevel@tonic-gate /* common case: at end, after == q->start+q->length-1 */
1367c478bd9Sstevel@tonic-gate
1377c478bd9Sstevel@tonic-gate /* move all the elements (after,last] up one slot */
1387c478bd9Sstevel@tonic-gate
1397c478bd9Sstevel@tonic-gate for (i=q->start+q->length-1; i>after; i--)
1407c478bd9Sstevel@tonic-gate QELEM(q,i+1) = QELEM(q,i);
1417c478bd9Sstevel@tonic-gate
1427c478bd9Sstevel@tonic-gate /* fill in slot after+1 */
1437c478bd9Sstevel@tonic-gate
1447c478bd9Sstevel@tonic-gate QELEM(q,after+1) = seqnum;
1457c478bd9Sstevel@tonic-gate
1467c478bd9Sstevel@tonic-gate /* Either increase the length by one, or move the starting point up
1477c478bd9Sstevel@tonic-gate one (deleting the first element, which got bashed above), as
1487c478bd9Sstevel@tonic-gate appropriate. */
1497c478bd9Sstevel@tonic-gate
1507c478bd9Sstevel@tonic-gate if (q->length == QSIZE(q)) {
1517c478bd9Sstevel@tonic-gate q->start++;
1527c478bd9Sstevel@tonic-gate if (q->start == QSIZE(q))
1537c478bd9Sstevel@tonic-gate q->start = 0;
1547c478bd9Sstevel@tonic-gate } else {
1557c478bd9Sstevel@tonic-gate q->length++;
1567c478bd9Sstevel@tonic-gate }
1577c478bd9Sstevel@tonic-gate }
158159d09a2SMark Phalan
1597c478bd9Sstevel@tonic-gate gss_int32
g_order_init(void ** vqueue,gssint_uint64 seqnum,int do_replay,int do_sequence,int wide_nums)1607c478bd9Sstevel@tonic-gate g_order_init(void **vqueue, gssint_uint64 seqnum,
1617c478bd9Sstevel@tonic-gate int do_replay, int do_sequence, int wide_nums)
1627c478bd9Sstevel@tonic-gate {
1637c478bd9Sstevel@tonic-gate queue *q;
1647c478bd9Sstevel@tonic-gate
1657c478bd9Sstevel@tonic-gate if ((q = (queue *) MALLOC(sizeof(queue))) == NULL)
166159d09a2SMark Phalan return(ENOMEM);
1677c478bd9Sstevel@tonic-gate
1687c478bd9Sstevel@tonic-gate q->do_replay = do_replay;
1697c478bd9Sstevel@tonic-gate q->do_sequence = do_sequence;
1707c478bd9Sstevel@tonic-gate q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL;
1717c478bd9Sstevel@tonic-gate
1727c478bd9Sstevel@tonic-gate q->start = 0;
1737c478bd9Sstevel@tonic-gate q->length = 1;
1747c478bd9Sstevel@tonic-gate q->firstnum = seqnum;
1757c478bd9Sstevel@tonic-gate q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask;
1767c478bd9Sstevel@tonic-gate
1777c478bd9Sstevel@tonic-gate *vqueue = (void *) q;
178159d09a2SMark Phalan return(0);
1797c478bd9Sstevel@tonic-gate }
1807c478bd9Sstevel@tonic-gate
1817c478bd9Sstevel@tonic-gate gss_int32
g_order_check(void ** vqueue,gssint_uint64 seqnum)1827c478bd9Sstevel@tonic-gate g_order_check(void **vqueue, gssint_uint64 seqnum)
1837c478bd9Sstevel@tonic-gate {
1847c478bd9Sstevel@tonic-gate queue *q;
1857c478bd9Sstevel@tonic-gate int i;
1867c478bd9Sstevel@tonic-gate gssint_uint64 expected;
187159d09a2SMark Phalan
1887c478bd9Sstevel@tonic-gate q = (queue *) (*vqueue);
1897c478bd9Sstevel@tonic-gate
1907c478bd9Sstevel@tonic-gate if (!q->do_replay && !q->do_sequence)
191159d09a2SMark Phalan return(GSS_S_COMPLETE);
1927c478bd9Sstevel@tonic-gate
1937c478bd9Sstevel@tonic-gate /* All checks are done relative to the initial sequence number, to
194220c5023Swyllys avoid (or at least put off) the pain of wrapping. */
195220c5023Swyllys seqnum -= q->firstnum;
196220c5023Swyllys
1977c478bd9Sstevel@tonic-gate /*
198220c5023Swyllys * If we're only doing 32-bit values, adjust for that again.
199220c5023Swyllys * Note that this will probably be the wrong thing to if we get
200220c5023Swyllys * 2**32 messages sent with 32-bit sequence numbers.
2017c478bd9Sstevel@tonic-gate */
202220c5023Swyllys seqnum &= q->mask;
2037c478bd9Sstevel@tonic-gate
2047c478bd9Sstevel@tonic-gate /* rule 1: expected sequence number */
205159d09a2SMark Phalan
2067c478bd9Sstevel@tonic-gate expected = (QELEM(q,q->start+q->length-1)+1) & q->mask;
207*55fea89dSDan Cross if (seqnum == expected) {
208220c5023Swyllys queue_insert(q, q->start+q->length-1, seqnum);
209159d09a2SMark Phalan return(GSS_S_COMPLETE);
2107c478bd9Sstevel@tonic-gate }
2117c478bd9Sstevel@tonic-gate
2127c478bd9Sstevel@tonic-gate /* rule 2: > expected sequence number */
213220c5023Swyllys if (after(seqnum, expected, q->mask)) {
214220c5023Swyllys queue_insert(q, q->start+q->length-1, seqnum);
215220c5023Swyllys if (q->do_replay && !q->do_sequence)
216159d09a2SMark Phalan return(GSS_S_COMPLETE);
217220c5023Swyllys else
218159d09a2SMark Phalan return(GSS_S_GAP_TOKEN);
2197c478bd9Sstevel@tonic-gate }
2207c478bd9Sstevel@tonic-gate
2217c478bd9Sstevel@tonic-gate /* rule 3: seqnum < seqnum(first) */
222220c5023Swyllys if (after(QELEM(q,q->start), seqnum, q->mask)) {
223220c5023Swyllys if (q->do_replay && !q->do_sequence)
224159d09a2SMark Phalan return(GSS_S_OLD_TOKEN);
2257c478bd9Sstevel@tonic-gate else
226159d09a2SMark Phalan return(GSS_S_UNSEQ_TOKEN);
2277c478bd9Sstevel@tonic-gate }
2287c478bd9Sstevel@tonic-gate
2297c478bd9Sstevel@tonic-gate /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */
2307c478bd9Sstevel@tonic-gate
2317c478bd9Sstevel@tonic-gate else {
2327c478bd9Sstevel@tonic-gate if (seqnum == QELEM(q,q->start+q->length-1))
233159d09a2SMark Phalan return(GSS_S_DUPLICATE_TOKEN);
2347c478bd9Sstevel@tonic-gate
2357c478bd9Sstevel@tonic-gate for (i=q->start; i<q->start+q->length-1; i++) {
236220c5023Swyllys if (seqnum == QELEM(q,i))
237220c5023Swyllys return (GSS_S_DUPLICATE_TOKEN);
238*55fea89dSDan Cross if (after(seqnum, QELEM(q,i), q->mask) &&
239220c5023Swyllys after(QELEM(q,i+1), seqnum, q->mask)) {
240220c5023Swyllys queue_insert(q, i, seqnum);
241220c5023Swyllys if (q->do_replay && !q->do_sequence)
242220c5023Swyllys return (GSS_S_COMPLETE);
243220c5023Swyllys else
244220c5023Swyllys return (GSS_S_UNSEQ_TOKEN);
245220c5023Swyllys }
2467c478bd9Sstevel@tonic-gate }
2477c478bd9Sstevel@tonic-gate }
2487c478bd9Sstevel@tonic-gate
2497c478bd9Sstevel@tonic-gate /* this should never happen */
250159d09a2SMark Phalan return(GSS_S_FAILURE);
2517c478bd9Sstevel@tonic-gate }
2527c478bd9Sstevel@tonic-gate
2537c478bd9Sstevel@tonic-gate void
g_order_free(void ** vqueue)2547c478bd9Sstevel@tonic-gate g_order_free(void **vqueue)
2557c478bd9Sstevel@tonic-gate {
2567c478bd9Sstevel@tonic-gate queue *q;
257*55fea89dSDan Cross
2587c478bd9Sstevel@tonic-gate q = (queue *) (*vqueue);
2597c478bd9Sstevel@tonic-gate
2607c478bd9Sstevel@tonic-gate FREE (q, sizeof (queue));
2617c478bd9Sstevel@tonic-gate
2627c478bd9Sstevel@tonic-gate *vqueue = NULL;
2637c478bd9Sstevel@tonic-gate }
2647c478bd9Sstevel@tonic-gate
2657c478bd9Sstevel@tonic-gate /*
2667c478bd9Sstevel@tonic-gate * These support functions are for the serialization routines
2677c478bd9Sstevel@tonic-gate */
2687c478bd9Sstevel@tonic-gate
2697c478bd9Sstevel@tonic-gate /*ARGSUSED*/
2707c478bd9Sstevel@tonic-gate gss_uint32
g_queue_size(void * vqueue,size_t * sizep)2717c478bd9Sstevel@tonic-gate g_queue_size(void *vqueue, size_t *sizep)
2727c478bd9Sstevel@tonic-gate {
2737c478bd9Sstevel@tonic-gate *sizep += sizeof(queue);
274159d09a2SMark Phalan return 0;
2757c478bd9Sstevel@tonic-gate }
2767c478bd9Sstevel@tonic-gate
2777c478bd9Sstevel@tonic-gate gss_uint32
g_queue_externalize(void * vqueue,unsigned char ** buf,size_t * lenremain)2787c478bd9Sstevel@tonic-gate g_queue_externalize(void *vqueue, unsigned char **buf, size_t *lenremain)
2797c478bd9Sstevel@tonic-gate {
2807c478bd9Sstevel@tonic-gate (void) memcpy(*buf, vqueue, sizeof(queue));
2817c478bd9Sstevel@tonic-gate *buf += sizeof(queue);
2827c478bd9Sstevel@tonic-gate *lenremain -= sizeof(queue);
283*55fea89dSDan Cross
284159d09a2SMark Phalan return 0;
2857c478bd9Sstevel@tonic-gate }
2867c478bd9Sstevel@tonic-gate
2877c478bd9Sstevel@tonic-gate gss_uint32
g_queue_internalize(void ** vqueue,unsigned char ** buf,size_t * lenremain)2887c478bd9Sstevel@tonic-gate g_queue_internalize(void **vqueue, unsigned char **buf, size_t *lenremain)
2897c478bd9Sstevel@tonic-gate {
2907c478bd9Sstevel@tonic-gate void *q;
2917c478bd9Sstevel@tonic-gate
2927c478bd9Sstevel@tonic-gate if ((q = (void *) MALLOC(sizeof(queue))) == 0)
2937c478bd9Sstevel@tonic-gate return ENOMEM;
2947c478bd9Sstevel@tonic-gate (void) memcpy(q, *buf, sizeof(queue));
2957c478bd9Sstevel@tonic-gate *buf += sizeof(queue);
2967c478bd9Sstevel@tonic-gate *lenremain -= sizeof(queue);
2977c478bd9Sstevel@tonic-gate *vqueue = q;
298159d09a2SMark Phalan return 0;
2997c478bd9Sstevel@tonic-gate }
300