1 /* 2 * Copyright 2008 Sun Microsystems, Inc. All rights reserved. 3 * Use is subject to license terms. 4 */ 5 6 7 /* 8 * Copyright 1993 by OpenVision Technologies, Inc. 9 * 10 * Permission to use, copy, modify, distribute, and sell this software 11 * and its documentation for any purpose is hereby granted without fee, 12 * provided that the above copyright notice appears in all copies and 13 * that both that copyright notice and this permission notice appear in 14 * supporting documentation, and that the name of OpenVision not be used 15 * in advertising or publicity pertaining to distribution of the software 16 * without specific, written prior permission. OpenVision makes no 17 * representations about the suitability of this software for any 18 * purpose. It is provided "as is" without express or implied warranty. 19 * 20 * OPENVISION DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 21 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO 22 * EVENT SHALL OPENVISION BE LIABLE FOR ANY SPECIAL, INDIRECT OR 23 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF 24 * USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR 25 * OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 26 * PERFORMANCE OF THIS SOFTWARE. 27 */ 28 29 /* 30 * $Id: util_ordering.c 19310 2007-03-29 21:36:38Z tlyu $ 31 */ 32 33 /* 34 * SUNW15resync 35 * Left this alone (MIT version causes STC gss_verify_mic(6) test failure) 36 * as it has bug fixes that MIT does not yet. 37 */ 38 39 /* 40 * functions to check sequence numbers for replay and sequencing 41 */ 42 43 #include "mechglueP.h" 44 #include "gssapiP_generic.h" 45 46 #define QUEUE_LENGTH 20 47 48 typedef struct _queue { 49 int do_replay; 50 int do_sequence; 51 int start; 52 int length; 53 gssint_uint64 firstnum; 54 gssint_uint64 elem[QUEUE_LENGTH]; 55 gssint_uint64 mask; 56 } queue; 57 58 /* rep invariant: 59 * - the queue is a circular queue. The first element (q->elem[q->start]) 60 * is the oldest. The last element is the newest. 61 */ 62 63 #define QSIZE(q) (sizeof((q)->elem)/sizeof((q)->elem[0])) 64 #define QELEM(q,i) ((q)->elem[(i)%QSIZE(q)]) 65 66 /* 67 * mask(max) is 2 ** 64 - 1, and half is 2 ** 63. 68 * |-------------------------------|-----------------------------| 69 * 0 half mask 70 * |-------------------------------| 71 * half range ( 2 ** 63 ) 72 * 73 * Here, the distance between n1 and n2 is used, if it falls 74 * in the "half range", normal integer comparison is enough. 75 * 76 * If the distance is bigger than half of the range, one of them must 77 * have passed the 'mask' point while the other one didn't. In this 78 * case, the result should be the reverse of normal comparison, i.e. 79 * the smaller one is considered bigger. 80 * 81 * If we shift the smaller value by adding 'mask' to it, 82 * the distance will be in half range again. 83 * 84 * The assumption is that the out of order event will not 85 * happen too often. If the distance is really bigger than half range, 86 * (1 is expected, but half + 2 arrives) we really don't know if it's a 87 * GAP token or an OLD token that wrapped. 88 */ 89 static int 90 after(gssint_uint64 n1, gssint_uint64 n2, gssint_uint64 mask) 91 { 92 int bigger; 93 gssint_uint64 diff; 94 gssint_uint64 half; 95 96 /* 97 * rule 1: same number. 98 * This may be ambiguous, but the caller of this function, 99 * g_order_check already takes care of it. 100 */ 101 if (n1 == n2) 102 return (0); 103 104 half = 1 + (mask >> 1); 105 106 if (n1 > n2) { 107 diff = n1 - n2; 108 bigger = 1; 109 } else { 110 diff = n2 - n1; 111 bigger = 0; 112 } 113 114 /* rule 2: in the same half range, normal comparison is enough */ 115 if (diff < half) 116 return bigger; 117 118 n1 &= half; 119 120 /* rule 3: different half, and n1 is on upper, n2 is bigger */ 121 /* rule 4: different half, and n1 is on lower, n1 is bigger */ 122 if (n1 != 0) 123 return (0); 124 125 return (1); 126 } 127 128 static void 129 queue_insert(queue *q, int after, gssint_uint64 seqnum) 130 { 131 /* insert. this is not the fastest way, but it's easy, and it's 132 optimized for insert at end, which is the common case */ 133 int i; 134 135 /* common case: at end, after == q->start+q->length-1 */ 136 137 /* move all the elements (after,last] up one slot */ 138 139 for (i=q->start+q->length-1; i>after; i--) 140 QELEM(q,i+1) = QELEM(q,i); 141 142 /* fill in slot after+1 */ 143 144 QELEM(q,after+1) = seqnum; 145 146 /* Either increase the length by one, or move the starting point up 147 one (deleting the first element, which got bashed above), as 148 appropriate. */ 149 150 if (q->length == QSIZE(q)) { 151 q->start++; 152 if (q->start == QSIZE(q)) 153 q->start = 0; 154 } else { 155 q->length++; 156 } 157 } 158 159 gss_int32 160 g_order_init(void **vqueue, gssint_uint64 seqnum, 161 int do_replay, int do_sequence, int wide_nums) 162 { 163 queue *q; 164 165 if ((q = (queue *) MALLOC(sizeof(queue))) == NULL) 166 return(ENOMEM); 167 168 q->do_replay = do_replay; 169 q->do_sequence = do_sequence; 170 q->mask = wide_nums ? ~(gssint_uint64)0 : 0xffffffffUL; 171 172 q->start = 0; 173 q->length = 1; 174 q->firstnum = seqnum; 175 q->elem[q->start] = ((gssint_uint64)0 - 1) & q->mask; 176 177 *vqueue = (void *) q; 178 return(0); 179 } 180 181 gss_int32 182 g_order_check(void **vqueue, gssint_uint64 seqnum) 183 { 184 queue *q; 185 int i; 186 gssint_uint64 expected; 187 188 q = (queue *) (*vqueue); 189 190 if (!q->do_replay && !q->do_sequence) 191 return(GSS_S_COMPLETE); 192 193 /* All checks are done relative to the initial sequence number, to 194 avoid (or at least put off) the pain of wrapping. */ 195 seqnum -= q->firstnum; 196 197 /* 198 * If we're only doing 32-bit values, adjust for that again. 199 * Note that this will probably be the wrong thing to if we get 200 * 2**32 messages sent with 32-bit sequence numbers. 201 */ 202 seqnum &= q->mask; 203 204 /* rule 1: expected sequence number */ 205 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