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