/* -*- mode: c; c-basic-offset: 4; indent-tabs-mode: nil -*- */
/*
* 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.
*/
/*
* Copyright (c) 1999, 2015, Oracle and/or its affiliates. All rights reserved.
*/
/*
* $Id: util_ordering.c 23457 2009-12-08 00:04:48Z tlyu $
*/
/*
* functions to check sequence numbers for replay and sequencing
*/
#include "gssapiP_generic.h"
#include <string.h>
#define QUEUE_LENGTH 20
typedef struct _queue {
int do_replay;
int do_sequence;
int start;
int length;
uint64_t firstnum;
/* Stored as deltas from firstnum. This way, the high bit won't
overflow unless we've actually gone through 2**n messages, or
gotten something *way* out of sequence. */
uint64_t elem[QUEUE_LENGTH];
/* All ones for 64-bit sequence numbers; 32 ones for 32-bit
sequence numbers. */
uint64_t 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)])
/*
* Solaris Kerberos: begin
* 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(uint64_t n1, uint64_t n2, uint64_t mask)
{
int bigger;
uint64_t diff;
uint64_t 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);
}
/* Solaris Kerberos: end */
static void
queue_insert(queue *q, int after, uint64_t 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, uint64_t seqnum,
int do_replay, int do_sequence, int wide_nums)
{
queue *q;
if ((q = (queue *) malloc(sizeof(queue))) == NULL)
return(ENOMEM);
/* This stops valgrind from complaining about writing uninitialized
data if the caller exports the context and writes it to a file.
We don't actually use those bytes at all, but valgrind still
complains. */
(void) memset(q, 0xfe, sizeof(*q));
q->do_replay = do_replay;
q->do_sequence = do_sequence;
q->mask = wide_nums ? ~(uint64_t)0 : 0xffffffffUL;
q->start = 0;
q->length = 1;
q->firstnum = seqnum;
q->elem[q->start] = ((uint64_t)0 - 1) & q->mask;
*vqueue = (void *) q;
return(0);
}
gss_int32
g_order_check(void **vqueue, uint64_t seqnum)
{
queue *q;
int i;
uint64_t 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 */
/* Solaris Kerberos: using after */
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) */
/* Solaris Kerberos */
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; i<q->start+q->length-1; i++) {
if (seqnum == QELEM(q,i))
return(GSS_S_DUPLICATE_TOKEN);
/* Solaris Kerberos */
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);
*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)
{
if (*lenremain < sizeof(queue))
return ENOMEM;
(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 (*lenremain < sizeof(queue))
return EINVAL;
if ((q = malloc(sizeof(queue))) == 0)
return ENOMEM;
(void) memcpy(q, *buf, sizeof(queue));
*buf += sizeof(queue);
*lenremain -= sizeof(queue);
*vqueue = q;
return 0;
}