/* * Copyright 2008 Sun Microsystems, Inc. All rights reserved. * Use is subject to license terms. */ /* * Copyright 1993 by OpenVision Technologies, Inc. * * Permission to use, copy, modify, distribute, and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appears in all copies and * that both that copyright notice and this permission notice appear in * supporting documentation, and that the name of OpenVision not be used * in advertising or publicity pertaining to distribution of the software * without specific, written prior permission. OpenVision makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR * PERFORMANCE OF THIS SOFTWARE. */ /* * $Id: util_ordering.c 19310 2007-03-29 21:36:38Z tlyu $ */ /* * SUNW15resync * Left this alone (MIT version causes STC gss_verify_mic(6) test failure) * as it has bug fixes that MIT does not yet. */ /* * functions to check sequence numbers for replay and sequencing */ #include "mechglueP.h" #include "gssapiP_generic.h" #define QUEUE_LENGTH 20 typedef struct _queue { int do_replay; int do_sequence; int start; int length; gssint_uint64 firstnum; gssint_uint64 elem[QUEUE_LENGTH]; gssint_uint64 mask; } queue; /* rep invariant: * - the queue is a circular queue. The first element (q->elem[q->start]) * is the oldest. The last element is the newest. */ #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0])) #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)]) /* * mask(max) is 2 ** 64 - 1, and half is 2 ** 63. * |-------------------------------|-----------------------------| * 0 half mask * |-------------------------------| * half range ( 2 ** 63 ) * * Here, the distance between n1 and n2 is used, if it falls * in the "half range", normal integer comparison is enough. * * If the distance is bigger than half of the range, one of them must * have passed the 'mask' point while the other one didn't. In this * case, the result should be the reverse of normal comparison, i.e. * the smaller one is considered bigger. * * If we shift the smaller value by adding 'mask' to it, * the distance will be in half range again. * * The assumption is that the out of order event will not * happen too often. If the distance is really bigger than half range, * (1 is expected, but half + 2 arrives) we really don't know if it's a * GAP token or an OLD token that wrapped. */ static int after(gssint_uint64 n1, gssint_uint64 n2, gssint_uint64 mask) { int bigger; gssint_uint64 diff; gssint_uint64 half; /* * rule 1: same number. * This may be ambiguous, but the caller of this function, * g_order_check already takes care of it. */ if (n1 == n2) return (0); half = 1 + (mask >> 1); if (n1 > n2) { diff = n1 - n2; bigger = 1; } else { diff = n2 - n1; bigger = 0; } /* rule 2: in the same half range, normal comparison is enough */ if (diff < half) return bigger; n1 &= half; /* rule 3: different half, and n1 is on upper, n2 is bigger */ /* rule 4: different half, and n1 is on lower, n1 is bigger */ if (n1 != 0) return (0); return (1); } static void queue_insert(queue *q, int after, gssint_uint64 seqnum) { /* insert. this is not the fastest way, but it's easy, and it's optimized for insert at end, which is the common case */ int i; /* common case: at end, after == q->start+q->length-1 */ /* move all the elements (after,last] up one slot */ for (i=q->start+q->length-1; i>after; i--) QELEM(q,i+1) = QELEM(q,i); /* fill in slot after+1 */ QELEM(q,after+1) = seqnum; /* Either increase the length by one, or move the starting point up one (deleting the first element, which got bashed above), as appropriate. */ if (q->length == QSIZE(q)) { q->start++; if (q->start == QSIZE(q)) q->start = 0; } else { q->length++; } } gss_int32 g_order_init(void **vqueue, gssint_uint64 seqnum, int do_replay, int do_sequence, int wide_nums) { queue *q; if ((q = (queue *) MALLOC(sizeof(queue))) == NULL) return(ENOMEM); q->do_replay = do_replay; q->do_sequence = do_sequence; q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL; q->start = 0; q->length = 1; q->firstnum = seqnum; q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask; *vqueue = (void *) q; return(0); } gss_int32 g_order_check(void **vqueue, gssint_uint64 seqnum) { queue *q; int i; gssint_uint64 expected; q = (queue *) (*vqueue); if (!q->do_replay && !q->do_sequence) return(GSS_S_COMPLETE); /* All checks are done relative to the initial sequence number, to avoid (or at least put off) the pain of wrapping. */ seqnum -= q->firstnum; /* * If we're only doing 32-bit values, adjust for that again. * Note that this will probably be the wrong thing to if we get * 2**32 messages sent with 32-bit sequence numbers. */ seqnum &= q->mask; /* rule 1: expected sequence number */ expected = (QELEM(q,q->start+q->length-1)+1) & q->mask; if (seqnum == expected) { queue_insert(q, q->start+q->length-1, seqnum); return(GSS_S_COMPLETE); } /* rule 2: > expected sequence number */ if (after(seqnum, expected, q->mask)) { queue_insert(q, q->start+q->length-1, seqnum); if (q->do_replay && !q->do_sequence) return(GSS_S_COMPLETE); else return(GSS_S_GAP_TOKEN); } /* rule 3: seqnum < seqnum(first) */ if (after(QELEM(q,q->start), seqnum, q->mask)) { if (q->do_replay && !q->do_sequence) return(GSS_S_OLD_TOKEN); else return(GSS_S_UNSEQ_TOKEN); } /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */ else { if (seqnum == QELEM(q,q->start+q->length-1)) return(GSS_S_DUPLICATE_TOKEN); for (i=q->start; istart+q->length-1; i++) { if (seqnum == QELEM(q,i)) return (GSS_S_DUPLICATE_TOKEN); if (after(seqnum, QELEM(q,i), q->mask) && after(QELEM(q,i+1), seqnum, q->mask)) { queue_insert(q, i, seqnum); if (q->do_replay && !q->do_sequence) return (GSS_S_COMPLETE); else return (GSS_S_UNSEQ_TOKEN); } } } /* this should never happen */ return(GSS_S_FAILURE); } void g_order_free(void **vqueue) { queue *q; q = (queue *) (*vqueue); FREE (q, sizeof (queue)); *vqueue = NULL; } /* * These support functions are for the serialization routines */ /*ARGSUSED*/ gss_uint32 g_queue_size(void *vqueue, size_t *sizep) { *sizep += sizeof(queue); return 0; } gss_uint32 g_queue_externalize(void *vqueue, unsigned char **buf, size_t *lenremain) { (void) memcpy(*buf, vqueue, sizeof(queue)); *buf += sizeof(queue); *lenremain -= sizeof(queue); return 0; } gss_uint32 g_queue_internalize(void **vqueue, unsigned char **buf, size_t *lenremain) { void *q; if ((q = (void *) MALLOC(sizeof(queue))) == 0) return ENOMEM; (void) memcpy(q, *buf, sizeof(queue)); *buf += sizeof(queue); *lenremain -= sizeof(queue); *vqueue = q; return 0; }