mech_eap/util_ordering.c

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