1 /* 2 * Copyright 2007 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 * SUNW15resync 36 * Left this alone (MIT version causes STC gss_verify_mic(6) test failure) 37 * as it has bug fixes that MIT does not yet. 38 */ 39 40 /* 41 * functions to check sequence numbers for replay and sequencing 42 */ 43 44 #include <mechglueP.h> 45 #include <gssapiP_generic.h> 46 47 #define QUEUE_LENGTH 20 48 49 typedef struct _queue { 50 int do_replay; 51 int do_sequence; 52 int start; 53 int length; 54 gssint_uint64 firstnum; 55 gssint_uint64 elem[QUEUE_LENGTH]; 56 gssint_uint64 mask; 57 } queue; 58 59 /* rep invariant: 60 * - the queue is a circular queue. The first element (q->elem[q->start]) 61 * is the oldest. The last element is the newest. 62 */ 63 64 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0])) 65 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)]) 66 67 /* 68 * mask(max) is 2 ** 64 - 1, and half is 2 ** 63. 69 * |-------------------------------|-----------------------------| 70 * 0 half mask 71 * |-------------------------------| 72 * half range ( 2 ** 63 ) 73 * 74 * Here, the distance between n1 and n2 is used, if it falls 75 * in the "half range", normal integer comparison is enough. 76 * 77 * If the distance is bigger than half of the range, one of them must 78 * have passed the 'mask' point while the other one didn't. In this 79 * case, the result should be the reverse of normal comparison, i.e. 80 * the smaller one is considered bigger. 81 * 82 * If we shift the smaller value by adding 'mask' to it, 83 * the distance will be in half range again. 84 * 85 * The assumption is that the out of order event will not 86 * happen too often. If the distance is really bigger than half range, 87 * (1 is expected, but half + 2 arrives) we really don't know if it's a 88 * GAP token or an OLD token that wrapped. 89 */ 90 static int 91 after(gssint_uint64 n1, gssint_uint64 n2, gssint_uint64 mask) 92 { 93 int bigger; 94 gssint_uint64 diff; 95 gssint_uint64 half; 96 97 /* 98 * rule 1: same number. 99 * This may be ambiguous, but the caller of this function, 100 * g_order_check already takes care of it. 101 */ 102 if (n1 == n2) 103 return (0); 104 105 half = 1 + (mask >> 1); 106 107 if (n1 > n2) { 108 diff = n1 - n2; 109 bigger = 1; 110 } else { 111 diff = n2 - n1; 112 bigger = 0; 113 } 114 115 /* rule 2: in the same half range, normal comparison is enough */ 116 if (diff < half) 117 return bigger; 118 119 n1 &= half; 120 121 /* rule 3: different half, and n1 is on upper, n2 is bigger */ 122 /* rule 4: different half, and n1 is on lower, n1 is bigger */ 123 if (n1 != 0) 124 return (0); 125 126 return (1); 127 } 128 129 static void 130 queue_insert(queue *q, int after, gssint_uint64 seqnum) 131 { 132 /* insert. this is not the fastest way, but it's easy, and it's 133 optimized for insert at end, which is the common case */ 134 int i; 135 136 /* common case: at end, after == q->start+q->length-1 */ 137 138 /* move all the elements (after,last] up one slot */ 139 140 for (i=q->start+q->length-1; i>after; i--) 141 QELEM(q,i+1) = QELEM(q,i); 142 143 /* fill in slot after+1 */ 144 145 QELEM(q,after+1) = seqnum; 146 147 /* Either increase the length by one, or move the starting point up 148 one (deleting the first element, which got bashed above), as 149 appropriate. */ 150 151 if (q->length == QSIZE(q)) { 152 q->start++; 153 if (q->start == QSIZE(q)) 154 q->start = 0; 155 } else { 156 q->length++; 157 } 158 } 159 160 gss_int32 161 g_order_init(void **vqueue, gssint_uint64 seqnum, 162 int do_replay, int do_sequence, int wide_nums) 163 { 164 queue *q; 165 166 if ((q = (queue *) MALLOC(sizeof(queue))) == NULL) 167 return (ENOMEM); 168 169 q->do_replay = do_replay; 170 q->do_sequence = do_sequence; 171 q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL; 172 173 q->start = 0; 174 q->length = 1; 175 q->firstnum = seqnum; 176 q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask; 177 178 *vqueue = (void *) q; 179 return (0); 180 } 181 182 gss_int32 183 g_order_check(void **vqueue, gssint_uint64 seqnum) 184 { 185 queue *q; 186 int i; 187 gssint_uint64 expected; 188 189 q = (queue *) (*vqueue); 190 191 if (!q->do_replay && !q->do_sequence) 192 return (GSS_S_COMPLETE); 193 194 /* All checks are done relative to the initial sequence number, to 195 avoid (or at least put off) the pain of wrapping. */ 196 seqnum -= q->firstnum; 197 198 /* 199 * If we're only doing 32-bit values, adjust for that again. 200 * Note that this will probably be the wrong thing to if we get 201 * 2**32 messages sent with 32-bit sequence numbers. 202 */ 203 seqnum &= q->mask; 204 205 /* rule 1: expected sequence number */ 206 expected = (QELEM(q,q->start+q->length-1)+1) & q->mask; 207 if (seqnum == expected) { 208 queue_insert(q, q->start+q->length-1, seqnum); 209 return (GSS_S_COMPLETE); 210 } 211 212 /* rule 2: > expected sequence number */ 213 if (after(seqnum, expected, q->mask)) { 214 queue_insert(q, q->start+q->length-1, seqnum); 215 if (q->do_replay && !q->do_sequence) 216 return (GSS_S_COMPLETE); 217 else 218 return (GSS_S_GAP_TOKEN); 219 } 220 221 /* rule 3: seqnum < seqnum(first) */ 222 if (after(QELEM(q,q->start), seqnum, q->mask)) { 223 if (q->do_replay && !q->do_sequence) 224 return (GSS_S_OLD_TOKEN); 225 else 226 return (GSS_S_UNSEQ_TOKEN); 227 } 228 229 /* rule 4+5: seqnum in [seqnum(first),seqnum(last)] */ 230 231 else { 232 if (seqnum == QELEM(q,q->start+q->length-1)) 233 return (GSS_S_DUPLICATE_TOKEN); 234 235 for (i=q->start; i<q->start+q->length-1; i++) { 236 if (seqnum == QELEM(q,i)) 237 return (GSS_S_DUPLICATE_TOKEN); 238 if (after(seqnum, QELEM(q,i), q->mask) && 239 after(QELEM(q,i+1), seqnum, q->mask)) { 240 queue_insert(q, i, seqnum); 241 if (q->do_replay && !q->do_sequence) 242 return (GSS_S_COMPLETE); 243 else 244 return (GSS_S_UNSEQ_TOKEN); 245 } 246 } 247 } 248 249 /* this should never happen */ 250 return (GSS_S_FAILURE); 251 } 252 253 void 254 g_order_free(void **vqueue) 255 { 256 queue *q; 257 258 q = (queue *) (*vqueue); 259 260 FREE (q, sizeof (queue)); 261 262 *vqueue = NULL; 263 } 264 265 /* 266 * These support functions are for the serialization routines 267 */ 268 269 /*ARGSUSED*/ 270 gss_uint32 271 g_queue_size(void *vqueue, size_t *sizep) 272 { 273 *sizep += sizeof(queue); 274 return (0); 275 } 276 277 gss_uint32 278 g_queue_externalize(void *vqueue, unsigned char **buf, size_t *lenremain) 279 { 280 (void) memcpy(*buf, vqueue, sizeof(queue)); 281 *buf += sizeof(queue); 282 *lenremain -= sizeof(queue); 283 284 return (0); 285 } 286 287 gss_uint32 288 g_queue_internalize(void **vqueue, unsigned char **buf, size_t *lenremain) 289 { 290 void *q; 291 292 if ((q = (void *) MALLOC(sizeof(queue))) == 0) 293 return ENOMEM; 294 (void) memcpy(q, *buf, sizeof(queue)); 295 *buf += sizeof(queue); 296 *lenremain -= sizeof(queue); 297 *vqueue = q; 298 return (0); 299 } 300