1 /* 2 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 #pragma ident "%Z%%M% %I% %E% SMI" 7 8 /* 9 * Copyright 1993 by OpenVision Technologies, Inc. 10 * 11 * Permission to use, copy, modify, distribute, and sell this software 12 * and its documentation for any purpose is hereby granted without fee, 13 * provided that the above copyright notice appears in all copies and 14 * that both that copyright notice and this permission notice appear in 15 * supporting documentation, and that the name of OpenVision not be used 16 * in advertising or publicity pertaining to distribution of the software 17 * without specific, written prior permission. OpenVision makes no 18 * representations about the suitability of this software for any 19 * purpose. It is provided "as is" without express or implied warranty. 20 * 21 * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 22 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO 23 * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR 24 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF 25 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR 26 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 27 * PERFORMANCE OF THIS SOFTWARE. 28 */ 29 30 /* 31 * $Id: util_ordering.c,v 1.4 1996/10/21 20:17:11 tytso Exp $ 32 */ 33 34 /* 35 * functions to check sequence numbers for replay and sequencing 36 */ 37 38 #include <mechglueP.h> 39 #include <gssapiP_generic.h> 40 41 #define QUEUE_LENGTH 20 42 43 typedef struct _queue { 44 int do_replay; 45 int do_sequence; 46 int start; 47 int length; 48 gssint_uint64 firstnum; 49 gssint_uint64 elem[QUEUE_LENGTH]; 50 gssint_uint64 mask; 51 } queue; 52 53 /* rep invariant: 54 * - the queue is a circular queue. The first element (q->elem[q->start]) 55 * is the oldest. The last element is the newest. 56 */ 57 58 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0])) 59 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)]) 60 61 static void 62 queue_insert(queue *q, int after, gssint_uint64 seqnum) 63 { 64 /* insert. this is not the fastest way, but it's easy, and it's 65 optimized for insert at end, which is the common case */ 66 int i; 67 68 /* common case: at end, after == q->start+q->length-1 */ 69 70 /* move all the elements (after,last] up one slot */ 71 72 for (i=q->start+q->length-1; i>after; i--) 73 QELEM(q,i+1) = QELEM(q,i); 74 75 /* fill in slot after+1 */ 76 77 QELEM(q,after+1) = seqnum; 78 79 /* Either increase the length by one, or move the starting point up 80 one (deleting the first element, which got bashed above), as 81 appropriate. */ 82 83 if (q->length == QSIZE(q)) { 84 q->start++; 85 if (q->start == QSIZE(q)) 86 q->start = 0; 87 } else { 88 q->length++; 89 } 90 } 91 92 gss_int32 93 g_order_init(void **vqueue, gssint_uint64 seqnum, 94 int do_replay, int do_sequence, int wide_nums) 95 { 96 queue *q; 97 98 if ((q = (queue *) MALLOC(sizeof(queue))) == NULL) 99 return(ENOMEM); 100 101 q->do_replay = do_replay; 102 q->do_sequence = do_sequence; 103 q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL; 104 105 q->start = 0; 106 q->length = 1; 107 q->firstnum = seqnum; 108 q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask; 109 110 *vqueue = (void *) q; 111 return(0); 112 } 113 114 gss_int32 115 g_order_check(void **vqueue, gssint_uint64 seqnum) 116 { 117 queue *q; 118 int i; 119 gssint_uint64 expected; 120 121 q = (queue *) (*vqueue); 122 123 if (!q->do_replay && !q->do_sequence) 124 return(GSS_S_COMPLETE); 125 126 /* All checks are done relative to the initial sequence number, to 127 avoid (or at least put off) the pain of wrapping. */ 128 129 /* wraparound case */ 130 if (seqnum < q->firstnum) { 131 /* if 32 bit, put seqnum into 64 bit range */ 132 if (q->mask != ~(gssint_uint64)0) { 133 seqnum |= 0x100000000ULL; 134 seqnum -= q->firstnum; 135 } else { 136 /* 137 * 64 bit wraparound, just add the number of 138 * elements before the wraparound point 139 * to get the normalized seqnum. 140 */ 141 seqnum += (~(gssint_uint64)0) - q->firstnum; 142 } 143 } else { 144 /* 145 * Normally (as long as seqnum >= firstnum), just subtract 146 * the firstnum to get the relative 'seqnum'. 147 */ 148 seqnum -= q->firstnum; 149 } 150 151 /* rule 1: expected sequence number */ 152 153 expected = (QELEM(q,q->start+q->length-1)+1) & q->mask; 154 if (seqnum == expected) { 155 queue_insert(q, q->start+q->length-1, seqnum); 156 return(GSS_S_COMPLETE); 157 } 158 159 /* rule 2: > expected sequence number */ 160 161 if ((seqnum > expected)) { 162 queue_insert(q, q->start+q->length-1, seqnum); 163 if (q->do_replay && !q->do_sequence) 164 return(GSS_S_COMPLETE); 165 else 166 return(GSS_S_GAP_TOKEN); 167 } 168 169 /* rule 3: seqnum < seqnum(first) */ 170 if (seqnum < QELEM(q,q->start)) { 171 if (q->do_replay) 172 return(GSS_S_OLD_TOKEN); 173 else 174 return(GSS_S_UNSEQ_TOKEN); 175 } 176 177 /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */ 178 179 else { 180 if (seqnum == QELEM(q,q->start+q->length-1)) 181 return(GSS_S_DUPLICATE_TOKEN); 182 183 for (i=q->start; i<q->start+q->length-1; i++) { 184 if (seqnum == QELEM(q,i)) 185 return(GSS_S_DUPLICATE_TOKEN); 186 if ((seqnum > QELEM(q,i)) && (seqnum < QELEM(q,i+1))) { 187 queue_insert(q, i, seqnum); 188 if (q->do_replay && !q->do_sequence) 189 return(GSS_S_COMPLETE); 190 else 191 return(GSS_S_UNSEQ_TOKEN); 192 } 193 } 194 } 195 196 /* this should never happen */ 197 return(GSS_S_FAILURE); 198 } 199 200 void 201 g_order_free(void **vqueue) 202 { 203 queue *q; 204 205 q = (queue *) (*vqueue); 206 207 FREE (q, sizeof (queue)); 208 209 *vqueue = NULL; 210 } 211 212 /* 213 * These support functions are for the serialization routines 214 */ 215 216 /*ARGSUSED*/ 217 gss_uint32 218 g_queue_size(void *vqueue, size_t *sizep) 219 { 220 *sizep += sizeof(queue); 221 return 0; 222 } 223 224 gss_uint32 225 g_queue_externalize(void *vqueue, unsigned char **buf, size_t *lenremain) 226 { 227 (void) memcpy(*buf, vqueue, sizeof(queue)); 228 *buf += sizeof(queue); 229 *lenremain -= sizeof(queue); 230 231 return 0; 232 } 233 234 gss_uint32 235 g_queue_internalize(void **vqueue, unsigned char **buf, size_t *lenremain) 236 { 237 void *q; 238 239 if ((q = (void *) MALLOC(sizeof(queue))) == 0) 240 return ENOMEM; 241 (void) memcpy(q, *buf, sizeof(queue)); 242 *buf += sizeof(queue); 243 *lenremain -= sizeof(queue); 244 *vqueue = q; 245 return 0; 246 } 247