1/* 2 * Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26package sun.security.jgss; 27 28import org.ietf.jgss.MessageProp; 29import java.util.LinkedList; 30 31/** 32 * A utility class that implements a number list that keeps track of which 33 * tokens have arrived by storing their token numbers in the list. It helps 34 * detect old tokens, out of sequence tokens, and duplicate tokens. 35 * 36 * Each element of the list is an interval [a, b]. Its existence in the 37 * list implies that all token numbers in the range a, a+1, ..., b-1, b 38 * have arrived. Gaps in arrived token numbers are represented by the 39 * numbers that fall in between two elements of the list. eg. {[a,b], 40 * [c,d]} indicates that the token numbers b+1, ..., c-1 have not arrived 41 * yet. 42 * 43 * The maximum number of intervals that we keep track of is 44 * MAX_INTERVALS. Thus if there are too many gaps, then some of the older 45 * sequence numbers are deleted from the list. The earliest sequence number 46 * that exists in the list is the windowStart. The next expected sequence 47 * number, or expectedNumber, is one greater than the latest sequence 48 * number in the list. 49 * 50 * The list keeps track the first token number that should have arrived 51 * (initNumber) so that it is able to detect if certain numbers occur after 52 * the first valid token number but before windowStart. That would happen 53 * if the number of elements (intervals) exceeds MAX_INTERVALS and some 54 * initial elements had to be deleted. 55 * 56 * The working of the list is optimized for the normal case where the 57 * tokens arrive in sequence. 58 * 59 * @author Mayank Upadhyay 60 * @since 1.4 61 */ 62public class TokenTracker { 63 64 static final int MAX_INTERVALS = 5; 65 66 private int initNumber; 67 private int windowStart; 68 private int expectedNumber; 69 70 private int windowStartIndex = 0; 71 72 private LinkedList<Entry> list = new LinkedList<Entry>(); 73 74 public TokenTracker(int initNumber) { 75 76 this.initNumber = initNumber; 77 this.windowStart = initNumber; 78 this.expectedNumber = initNumber; 79 80 // Make an entry with one less than the expected first token 81 Entry entry = new Entry(initNumber-1); 82 83 list.add(entry); 84 } 85 86 /** 87 * Returns the index for the entry into which this number will fit. If 88 * there is none, it returns the index of the last interval 89 * which precedes this number. It returns -1 if the number needs to be 90 * a in a new interval ahead of the whole list. 91 */ 92 private int getIntervalIndex(int number) { 93 Entry entry = null; 94 int i; 95 // Start from the rear to optimize for the normal case 96 for (i = list.size() - 1; i >= 0; i--) { 97 entry = list.get(i); 98 if (entry.compareTo(number) <= 0) 99 break; 100 } 101 return i; 102 } 103 104 /** 105 * Sets the sequencing and replay information for the given token 106 * number. 107 * 108 * The following represents the number line with positions of 109 * initNumber, windowStart, expectedNumber marked on it. Regions in 110 * between them show the different sequencing and replay state 111 * possibilites for tokens that fall in there. 112 * 113 * (1) windowStart 114 * initNumber expectedNumber 115 * | | 116 * ---|---------------------------|--- 117 * GAP | DUP/UNSEQ | GAP 118 * 119 * 120 * (2) initNumber windowStart expectedNumber 121 * | | | 122 * ---|---------------|--------------|--- 123 * GAP | OLD | DUP/UNSEQ | GAP 124 * 125 * 126 * (3) windowStart 127 * expectedNumber initNumber 128 * | | 129 * ---|---------------------------|--- 130 * DUP/UNSEQ | GAP | DUP/UNSEQ 131 * 132 * 133 * (4) expectedNumber initNumber windowStart 134 * | | | 135 * ---|---------------|--------------|--- 136 * DUP/UNSEQ | GAP | OLD | DUP/UNSEQ 137 * 138 * 139 * 140 * (5) windowStart expectedNumber initNumber 141 * | | | 142 * ---|---------------|--------------|--- 143 * OLD | DUP/UNSEQ | GAP | OLD 144 * 145 * 146 * 147 * (This analysis leaves out the possibility that expectedNumber passes 148 * initNumber after wrapping around. That may be added later.) 149 */ 150 synchronized public final void getProps(int number, MessageProp prop) { 151 152 boolean gap = false; 153 boolean old = false; 154 boolean unsequenced = false; 155 boolean duplicate = false; 156 157 // System.out.println("\n\n=========="); 158 // System.out.println("TokenTracker.getProps(): number=" + number); 159 // System.out.println(toString()); 160 161 int pos = getIntervalIndex(number); 162 Entry entry = null; 163 if (pos != -1) 164 entry = list.get(pos); 165 166 // Optimize for the expected case: 167 168 if (number == expectedNumber) { 169 expectedNumber++; 170 } else { 171 172 // Next trivial case is to check for duplicate 173 if (entry != null && entry.contains(number)) 174 duplicate = true; 175 else { 176 177 if (expectedNumber >= initNumber) { 178 179 // Cases (1) and (2) 180 181 if (number > expectedNumber) { 182 gap = true; 183 } else if (number >= windowStart) { 184 unsequenced = true; 185 } else if (number >= initNumber) { 186 old = true; 187 } else { 188 gap = true; 189 } 190 } else { 191 192 // Cases (3), (4) and (5) 193 194 if (number > expectedNumber) { 195 if (number < initNumber) { 196 gap = true; 197 } else if (windowStart >= initNumber) { 198 if (number >= windowStart) { 199 unsequenced = true; 200 } else 201 old = true; 202 } else { 203 old = true; 204 } 205 } else if (windowStart > expectedNumber) { 206 unsequenced = true; 207 } else if (number < windowStart) { 208 old = true; 209 } else 210 unsequenced = true; 211 } 212 } 213 } 214 215 if (!duplicate && !old) 216 add(number, pos); 217 218 if (gap) 219 expectedNumber = number+1; 220 221 prop.setSupplementaryStates(duplicate, old, unsequenced, gap, 222 0, null); 223 224 // System.out.println("Leaving with state:"); 225 // System.out.println(toString()); 226 // System.out.println("==========\n"); 227 } 228 229 /** 230 * Adds the number to the list just after the entry that is currently 231 * at position prevEntryPos. If prevEntryPos is -1, then the number 232 * will begin a new interval at the front of the list. 233 */ 234 private void add(int number, int prevEntryPos) { 235 236 Entry entry; 237 Entry entryBefore = null; 238 Entry entryAfter = null; 239 240 boolean appended = false; 241 boolean prepended = false; 242 243 if (prevEntryPos != -1) { 244 entryBefore = list.get(prevEntryPos); 245 246 // Can this number simply be added to the previous interval? 247 if (number == (entryBefore.getEnd() + 1)) { 248 entryBefore.setEnd(number); 249 appended = true; 250 } 251 } 252 253 // Now check the interval that follows this number 254 255 int nextEntryPos = prevEntryPos + 1; 256 if ((nextEntryPos) < list.size()) { 257 entryAfter = list.get(nextEntryPos); 258 259 // Can this number simply be added to the next interval? 260 if (number == (entryAfter.getStart() - 1)) { 261 if (!appended) { 262 entryAfter.setStart(number); 263 } else { 264 // Merge the two entries 265 entryAfter.setStart(entryBefore.getStart()); 266 list.remove(prevEntryPos); 267 // Index of any entry following this gets decremented 268 if (windowStartIndex > prevEntryPos) 269 windowStartIndex--; 270 } 271 prepended = true; 272 } 273 } 274 275 if (prepended || appended) 276 return; 277 278 /* 279 * At this point we know that the number will start a new interval 280 * which needs to be added to the list. We might have to recyle an 281 * older entry in the list. 282 */ 283 284 if (list.size() < MAX_INTERVALS) { 285 entry = new Entry(number); 286 if (prevEntryPos < windowStartIndex) 287 windowStartIndex++; // due to the insertion which will happen 288 } else { 289 /* 290 * Delete the entry that marks the start of the current window. 291 * The marker will automatically point to the next entry in the 292 * list when this happens. If the current entry is at the end 293 * of the list then set the marker to the start of the list. 294 */ 295 int oldWindowStartIndex = windowStartIndex; 296 if (windowStartIndex == (list.size() - 1)) 297 windowStartIndex = 0; 298 299 entry = list.remove(oldWindowStartIndex); 300 windowStart = list.get(windowStartIndex).getStart(); 301 entry.setStart(number); 302 entry.setEnd(number); 303 304 if (prevEntryPos >= oldWindowStartIndex) { 305 prevEntryPos--; // due to the deletion that just happened 306 } else { 307 /* 308 * If the start of the current window just moved from the 309 * end of the list to the front of the list, and if the new 310 * entry will be added to the front of the list, then 311 * the new entry is the actual window start. 312 * eg, Consider { [-10, -8], ..., [-6, -3], [3, 9]}. In 313 * this list, suppose the element [3, 9] is the start of 314 * the window and has to be deleted to make place to add 315 * [-12, -12]. The resultant list will be 316 * {[-12, -12], [-10, -8], ..., [-6, -3]} and the new start 317 * of the window should be the element [-12, -12], not 318 * [-10, -8] which succeeded [3, 9] in the old list. 319 */ 320 if (oldWindowStartIndex != windowStartIndex) { 321 // windowStartIndex is 0 at this point 322 if (prevEntryPos == -1) 323 // The new entry is going to the front 324 windowStart = number; 325 } else { 326 // due to the insertion which will happen: 327 windowStartIndex++; 328 } 329 } 330 } 331 332 // Finally we are ready to actually add to the list at index 333 // 'prevEntryPos+1' 334 335 list.add(prevEntryPos+1, entry); 336 } 337 338 public String toString() { 339 StringBuilder sb = new StringBuilder("TokenTracker: "); 340 sb.append(" initNumber=").append(initNumber); 341 sb.append(" windowStart=").append(windowStart); 342 sb.append(" expectedNumber=").append(expectedNumber); 343 sb.append(" windowStartIndex=").append(windowStartIndex); 344 sb.append("\n\tIntervals are: {"); 345 for (int i = 0; i < list.size(); i++) { 346 if (i != 0) 347 sb.append(", "); 348 sb.append(list.get(i).toString()); 349 } 350 sb.append('}'); 351 return sb.toString(); 352 } 353 354 /** 355 * An entry in the list that represents the sequence of received 356 * tokens. Each entry is actaully an interval of numbers, all of which 357 * have been received. 358 */ 359 class Entry { 360 361 private int start; 362 private int end; 363 364 Entry(int number) { 365 start = number; 366 end = number; 367 } 368 369 /** 370 * Returns -1 if this interval represented by this entry precedes 371 * the number, 0 if the number is contained in the interval, 372 * and -1 if the interval occurs after the number. 373 */ 374 final int compareTo(int number) { 375 if (start > number) 376 return 1; 377 else if (end < number) 378 return -1; 379 else 380 return 0; 381 } 382 383 final boolean contains(int number) { 384 return (number >= start && 385 number <= end); 386 } 387 388 final void append(int number) { 389 if (number == (end + 1)) 390 end = number; 391 } 392 393 final void setInterval(int start, int end) { 394 this.start = start; 395 this.end = end; 396 } 397 398 final void setEnd(int end) { 399 this.end = end; 400 } 401 402 final void setStart(int start) { 403 this.start = start; 404 } 405 406 final int getStart() { 407 return start; 408 } 409 410 final int getEnd() { 411 return end; 412 } 413 414 public String toString() { 415 return ("[" + start + ", " + end + "]"); 416 } 417 418 } 419} 420