util_ordering.c

   1 /*
   2  * Copyright (c) 2010, JANET(UK)
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  *
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  *
  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.
  15  *
  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.
  19  *
  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
  30  * SUCH DAMAGE.
  31  */
  32 /*
  33  * Copyright 1993 by OpenVision Technologies, Inc.
  34  *
  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.
  44  *
  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.
  52  */
  53
  54 /*
  55  * $Id: util_ordering.c 23457 2009-12-08 00:04:48Z tlyu $
  56  */
  57
  58 /*
  59  * functions to check sequence numbers for replay and sequencing
  60  */
  61
  62 #include "gssapiP_eap.h"
  63
  64 #define QUEUE_LENGTH 20
  65
  66 typedef struct _queue {
  67     int do_replay;
  68     int do_sequence;
  69     int start;
  70     int length;
  71     uint64_t firstnum;
  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
  77        sequence numbers.  */
  78     uint64_t mask;
  79 } queue;
  80
  81 /* rep invariant:
  82  *  - the queue is a circular queue.  The first element (q->elem[q->start])
  83  * is the oldest.  The last element is the newest.
  84  */
  85
  86 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0]))
  87 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)])
  88
  89 static void
  90 queue_insert(queue *q, int after, uint64_t seqnum)
  91 {
  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 */
  94     int i;
  95
  96     /* common case: at end, after == q->start+q->length-1 */
  97
  98     /* move all the elements (after,last] up one slot */
  99
 100     for (i = q->start + q->length - 1; i > after; i--)
 101         QELEM(q,i+1) = QELEM(q,i);
 102
 103     /* fill in slot after+1 */
 104
 105     QELEM(q,after+1) = seqnum;
 106
 107     /* Either increase the length by one, or move the starting point up
 108        one (deleting the first element, which got bashed above), as
 109        appropriate. */
 110
 111     if (q->length == QSIZE(q)) {
 112         q->start++;
 113         if (q->start == QSIZE(q))
 114             q->start = 0;
 115     } else {
 116         q->length++;
 117     }
 118 }
 119
 120 OM_uint32
 121 sequenceInit(OM_uint32 *minor,
 122              void **vqueue,
 123              uint64_t seqnum,
 124              int do_replay,
 125              int do_sequence,
 126              int wide_nums)
 127 {
 128     queue *q;
 129
 130     q = (queue *)GSSEAP_CALLOC(1, sizeof(queue));
 131     if (q == NULL) {
 132         *minor = ENOMEM;
 133         return GSS_S_FAILURE;
 134     }
 135
 136     q->do_replay = do_replay;
 137     q->do_sequence = do_sequence;
 138     q->mask = wide_nums ? ~(uint64_t)0 : 0xffffffffUL;
 139
 140     q->start = 0;
 141     q->length = 1;
 142     q->firstnum = seqnum;
 143     q->elem[q->start] = ((uint64_t)0 - 1) & q->mask;
 144
 145     *vqueue = (void *)q;
 146
 147     return GSS_S_COMPLETE;
 148 }
 149
 150 OM_uint32
 151 sequenceCheck(OM_uint32 *minor,
 152               void **vqueue,
 153               uint64_t seqnum)
 154 {
 155     queue *q;
 156     int i;
 157     uint64_t expected;
 158
 159     q = (queue *) (*vqueue);
 160
 161     if (!q->do_replay && !q->do_sequence)
 162         return GSS_S_COMPLETE;
 163
 164     /* All checks are done relative to the initial sequence number, to
 165        avoid (or at least put off) the pain of wrapping.  */
 166     seqnum -= q->firstnum;
 167     /* If we're only doing 32-bit values, adjust for that again.
 168
 169        Note that this will probably be the wrong thing to if we get
 170        2**32 messages sent with 32-bit sequence numbers.  */
 171     seqnum &= q->mask;
 172
 173     /* rule 1: expected sequence number */
 174
 175     expected = (QELEM(q,q->start+q->length-1)+1) & q->mask;
 176     if (seqnum == expected) {
 177         queue_insert(q, q->start+q->length-1, seqnum);
 178         return GSS_S_COMPLETE;
 179     }
 180
 181     /* rule 2: > expected sequence number */
 182
 183     if ((seqnum > expected)) {
 184         queue_insert(q, q->start+q->length-1, seqnum);
 185         if (q->do_replay && !q->do_sequence)
 186             return GSS_S_COMPLETE;
 187         else
 188             return GSS_S_GAP_TOKEN;
 189     }
 190
 191     /* rule 3: seqnum < seqnum(first) */
 192
 193     if ((seqnum < QELEM(q,q->start)) &&
 194         /* Is top bit of whatever width we're using set?
 195
 196            We used to check for greater than or equal to firstnum, but
 197            (1) we've since switched to compute values relative to
 198            firstnum, so the lowest we can have is 0, and (2) the effect
 199            of the original scheme was highly dependent on whether
 200            firstnum was close to either side of 0.  (Consider
 201            firstnum==0xFFFFFFFE and we miss three packets; the next
 202            packet is *new* but would look old.)
 203
 204            This check should give us 2**31 or 2**63 messages "new", and
 205            just as many "old".  That's not quite right either.  */
 206         (seqnum & (1 + (q->mask >> 1)))
 207     ) {
 208         if (q->do_replay && !q->do_sequence)
 209             return GSS_S_OLD_TOKEN;
 210         else
 211             return GSS_S_UNSEQ_TOKEN;
 212     }
 213
 214     /* rule 4+5: seqnum in [seqnum(first),seqnum(last)]  */
 215
 216     else {
 217         if (seqnum == QELEM(q,q->start+q->length - 1))
 218             return GSS_S_DUPLICATE_TOKEN;
 219
 220         for (i = q->start; i < q->start + q->length - 1; i++) {
 221             if (seqnum == QELEM(q,i))
 222                 return GSS_S_DUPLICATE_TOKEN;
 223             if ((seqnum > QELEM(q,i)) && (seqnum < QELEM(q,i+1))) {
 224                 queue_insert(q, i, seqnum);
 225                 if (q->do_replay && !q->do_sequence)
 226                     return GSS_S_COMPLETE;
 227                 else
 228                     return GSS_S_UNSEQ_TOKEN;
 229             }
 230         }
 231     }
 232
 233     /* this should never happen */
 234     return GSS_S_FAILURE;
 235 }
 236
 237 OM_uint32
 238 sequenceFree(OM_uint32 *minor, void **vqueue)
 239 {
 240     queue *q;
 241
 242     q = (queue *) (*vqueue);
 243
 244     GSSEAP_FREE(q);
 245
 246     *vqueue = NULL;
 247
 248     return GSS_S_COMPLETE;
 249 }
 250
 251 /*
 252  * These support functions are for the serialization routines
 253  */
 254 size_t
 255 sequenceSize(void *vqueue)
 256 {
 257     return sizeof(queue);
 258 }
 259
 260 OM_uint32
 261 sequenceExternalize(OM_uint32 *minor,
 262                     void *vqueue,
 263                     unsigned char **buf,
 264                     size_t *lenremain)
 265 {
 266     if (*lenremain < sizeof(queue)) {
 267         *minor = GSSEAP_WRONG_SIZE;
 268         return GSS_S_FAILURE;
 269     }
 270     memcpy(*buf, vqueue, sizeof(queue));
 271     *buf += sizeof(queue);
 272     *lenremain -= sizeof(queue);
 273
 274     return 0;
 275 }
 276
 277 OM_uint32
 278 sequenceInternalize(OM_uint32 *minor,
 279                     void **vqueue,
 280                     unsigned char **buf,
 281                     size_t *lenremain)
 282 {
 283     void *q;
 284
 285     if (*lenremain < sizeof(queue)) {
 286         *minor = GSSEAP_WRONG_SIZE;
 287         return GSS_S_DEFECTIVE_TOKEN;
 288     }
 289
 290     q = GSSEAP_MALLOC(sizeof(queue));
 291     if (q == NULL) {
 292         *minor = ENOMEM;
 293         return GSS_S_FAILURE;
 294     }
 295
 296     memcpy(q, *buf, sizeof(queue));
 297     *buf += sizeof(queue);
 298     *lenremain -= sizeof(queue);
 299     *vqueue = q;
 300
 301     *minor = 0;
 302     return GSS_S_COMPLETE;
 303 }