001: /*
002: * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved.
003: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004: *
005: * This code is free software; you can redistribute it and/or modify it
006: * under the terms of the GNU General Public License version 2 only, as
007: * published by the Free Software Foundation. Sun designates this
008: * particular file as subject to the "Classpath" exception as provided
009: * by Sun in the LICENSE file that accompanied this code.
010: *
011: * This code is distributed in the hope that it will be useful, but WITHOUT
012: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
014: * version 2 for more details (a copy is included in the LICENSE file that
015: * accompanied this code).
016: *
017: * You should have received a copy of the GNU General Public License version
018: * 2 along with this work; if not, write to the Free Software Foundation,
019: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
022: * CA 95054 USA or visit www.sun.com if you need additional information or
023: * have any questions.
024: */
025:
026: package sun.security.jgss;
027:
028: import org.ietf.jgss.MessageProp;
029: import java.util.LinkedList;
030:
031: /**
032: * A utility class that implements a number list that keeps track of which
033: * tokens have arrived by storing their token numbers in the list. It helps
034: * detect old tokens, out of sequence tokens, and duplicate tokens.
035: *
036: * Each element of the list is an interval [a, b]. Its existence in the
037: * list implies that all token numbers in the range a, a+1, ..., b-1, b
038: * have arrived. Gaps in arrived token numbers are represented by the
039: * numbers that fall in between two elements of the list. eg. {[a,b],
040: * [c,d]} indicates that the token numbers b+1, ..., c-1 have not arrived
041: * yet.
042: *
043: * The maximum number of intervals that we keep track of is
044: * MAX_INTERVALS. Thus if there are too many gaps, then some of the older
045: * sequence numbers are deleted from the list. The earliest sequence number
046: * that exists in the list is the windowStart. The next expected sequence
047: * number, or expectedNumber, is one greater than the latest sequence
048: * number in the list.
049: *
050: * The list keeps track the first token number that should have arrived
051: * (initNumber) so that it is able to detect if certain numbers occur after
052: * the first valid token number but before windowStart. That would happen
053: * if the number of elements (intervals) exceeds MAX_INTERVALS and some
054: * initial elements had to be deleted.
055: *
056: * The working of the list is optimized for the normal case where the
057: * tokens arrive in sequence.
058: *
059: * @author Mayank Upadhyay
060: * @version 1.15, 05/05/07
061: * @since 1.4
062: */
063: public class TokenTracker {
064:
065: static final int MAX_INTERVALS = 5;
066:
067: private int initNumber;
068: private int windowStart;
069: private int expectedNumber;
070:
071: private int windowStartIndex = 0;
072:
073: private LinkedList<Entry> list = new LinkedList<Entry>();
074:
075: public TokenTracker(int initNumber) {
076:
077: this .initNumber = initNumber;
078: this .windowStart = initNumber;
079: this .expectedNumber = initNumber;
080:
081: // Make an entry with one less than the expected first token
082: Entry entry = new Entry(initNumber - 1);
083:
084: list.add(entry);
085: }
086:
087: /**
088: * Returns the index for the entry into which this number will fit. If
089: * there is none, it returns the index of the last interval
090: * which precedes this number. It returns -1 if the number needs to be
091: * a in a new interval ahead of the whole list.
092: */
093: private int getIntervalIndex(int number) {
094: Entry entry = null;
095: int i;
096: // Start from the rear to optimize for the normal case
097: for (i = list.size() - 1; i >= 0; i--) {
098: entry = list.get(i);
099: if (entry.compareTo(number) <= 0)
100: break;
101: }
102: return i;
103: }
104:
105: /**
106: * Sets the sequencing and replay information for the given token
107: * number.
108: *
109: * The following represents the number line with positions of
110: * initNumber, windowStart, expectedNumber marked on it. Regions in
111: * between them show the different sequencing and replay state
112: * possibilites for tokens that fall in there.
113: *
114: * (1) windowStart
115: * initNumber expectedNumber
116: * | |
117: * ---|---------------------------|---
118: * GAP | DUP/UNSEQ | GAP
119: *
120: *
121: * (2) initNumber windowStart expectedNumber
122: * | | |
123: * ---|---------------|--------------|---
124: * GAP | OLD | DUP/UNSEQ | GAP
125: *
126: *
127: * (3) windowStart
128: * expectedNumber initNumber
129: * | |
130: * ---|---------------------------|---
131: * DUP/UNSEQ | GAP | DUP/UNSEQ
132: *
133: *
134: * (4) expectedNumber initNumber windowStart
135: * | | |
136: * ---|---------------|--------------|---
137: * DUP/UNSEQ | GAP | OLD | DUP/UNSEQ
138: *
139: *
140: *
141: * (5) windowStart expectedNumber initNumber
142: * | | |
143: * ---|---------------|--------------|---
144: * OLD | DUP/UNSEQ | GAP | OLD
145: *
146: *
147: *
148: * (This analysis leaves out the possibility that expectedNumber passes
149: * initNumber after wrapping around. That may be added later.)
150: */
151: synchronized public final void getProps(int number, MessageProp prop) {
152:
153: boolean gap = false;
154: boolean old = false;
155: boolean unsequenced = false;
156: boolean duplicate = false;
157:
158: // System.out.println("\n\n==========");
159: // System.out.println("TokenTracker.getProps(): number=" + number);
160: // System.out.println(toString());
161:
162: int pos = getIntervalIndex(number);
163: Entry entry = null;
164: if (pos != -1)
165: entry = list.get(pos);
166:
167: // Optimize for the expected case:
168:
169: if (number == expectedNumber) {
170: expectedNumber++;
171: } else {
172:
173: // Next trivial case is to check for duplicate
174: if (entry != null && entry.contains(number))
175: duplicate = true;
176: else {
177:
178: if (expectedNumber >= initNumber) {
179:
180: // Cases (1) and (2)
181:
182: if (number > expectedNumber) {
183: gap = true;
184: } else if (number >= windowStart) {
185: unsequenced = true;
186: } else if (number >= initNumber) {
187: old = true;
188: } else {
189: gap = true;
190: }
191: } else {
192:
193: // Cases (3), (4) and (5)
194:
195: if (number > expectedNumber) {
196: if (number < initNumber) {
197: gap = true;
198: } else if (windowStart >= initNumber) {
199: if (number >= windowStart) {
200: unsequenced = true;
201: } else
202: old = true;
203: } else {
204: old = true;
205: }
206: } else if (windowStart > expectedNumber) {
207: unsequenced = true;
208: } else if (number < windowStart) {
209: old = true;
210: } else
211: unsequenced = true;
212: }
213: }
214: }
215:
216: if (!duplicate && !old)
217: add(number, pos);
218:
219: if (gap)
220: expectedNumber = number + 1;
221:
222: prop.setSupplementaryStates(duplicate, old, unsequenced, gap,
223: 0, null);
224:
225: // System.out.println("Leaving with state:");
226: // System.out.println(toString());
227: // System.out.println("==========\n");
228: }
229:
230: /**
231: * Adds the number to the list just after the entry that is currently
232: * at position prevEntryPos. If prevEntryPos is -1, then the number
233: * will begin a new interval at the front of the list.
234: */
235: private void add(int number, int prevEntryPos) {
236:
237: Entry entry;
238: Entry entryBefore = null;
239: Entry entryAfter = null;
240:
241: boolean appended = false;
242: boolean prepended = false;
243:
244: if (prevEntryPos != -1) {
245: entryBefore = list.get(prevEntryPos);
246:
247: // Can this number simply be added to the previous interval?
248: if (number == (entryBefore.getEnd() + 1)) {
249: entryBefore.setEnd(number);
250: appended = true;
251: }
252: }
253:
254: // Now check the interval that follows this number
255:
256: int nextEntryPos = prevEntryPos + 1;
257: if ((nextEntryPos) < list.size()) {
258: entryAfter = list.get(nextEntryPos);
259:
260: // Can this number simply be added to the next interval?
261: if (number == (entryAfter.getStart() - 1)) {
262: if (!appended) {
263: entryAfter.setStart(number);
264: } else {
265: // Merge the two entries
266: entryAfter.setStart(entryBefore.getStart());
267: list.remove(prevEntryPos);
268: // Index of any entry following this gets decremented
269: if (windowStartIndex > prevEntryPos)
270: windowStartIndex--;
271: }
272: prepended = true;
273: }
274: }
275:
276: if (prepended || appended)
277: return;
278:
279: /*
280: * At this point we know that the number will start a new interval
281: * which needs to be added to the list. We might have to recyle an
282: * older entry in the list.
283: */
284:
285: if (list.size() < MAX_INTERVALS) {
286: entry = new Entry(number);
287: if (prevEntryPos < windowStartIndex)
288: windowStartIndex++; // due to the insertion which will happen
289: } else {
290: /*
291: * Delete the entry that marks the start of the current window.
292: * The marker will automatically point to the next entry in the
293: * list when this happens. If the current entry is at the end
294: * of the list then set the marker to the start of the list.
295: */
296: int oldWindowStartIndex = windowStartIndex;
297: if (windowStartIndex == (list.size() - 1))
298: windowStartIndex = 0;
299:
300: entry = list.remove(oldWindowStartIndex);
301: windowStart = list.get(windowStartIndex).getStart();
302: entry.setStart(number);
303: entry.setEnd(number);
304:
305: if (prevEntryPos >= oldWindowStartIndex) {
306: prevEntryPos--; // due to the deletion that just happened
307: } else {
308: /*
309: * If the start of the current window just moved from the
310: * end of the list to the front of the list, and if the new
311: * entry will be added to the front of the list, then
312: * the new entry is the actual window start.
313: * eg, Consider { [-10, -8], ..., [-6, -3], [3, 9]}. In
314: * this list, suppose the element [3, 9] is the start of
315: * the window and has to be deleted to make place to add
316: * [-12, -12]. The resultant list will be
317: * {[-12, -12], [-10, -8], ..., [-6, -3]} and the new start
318: * of the window should be the element [-12, -12], not
319: * [-10, -8] which succeeded [3, 9] in the old list.
320: */
321: if (oldWindowStartIndex != windowStartIndex) {
322: // windowStartIndex is 0 at this point
323: if (prevEntryPos == -1)
324: // The new entry is going to the front
325: windowStart = number;
326: } else {
327: // due to the insertion which will happen:
328: windowStartIndex++;
329: }
330: }
331: }
332:
333: // Finally we are ready to actually add to the list at index
334: // 'prevEntryPos+1'
335:
336: list.add(prevEntryPos + 1, entry);
337: }
338:
339: public String toString() {
340: StringBuffer buf = new StringBuffer("TokenTracker: ");
341: buf.append(" initNumber=").append(initNumber);
342: buf.append(" windowStart=").append(windowStart);
343: buf.append(" expectedNumber=").append(expectedNumber);
344: buf.append(" windowStartIndex=").append(windowStartIndex);
345: buf.append("\n\tIntervals are: {");
346: for (int i = 0; i < list.size(); i++) {
347: if (i != 0)
348: buf.append(", ");
349: buf.append(list.get(i).toString());
350: }
351: buf.append('}');
352: return buf.toString();
353: }
354:
355: /**
356: * An entry in the list that represents the sequence of received
357: * tokens. Each entry is actaully an interval of numbers, all of which
358: * have been received.
359: */
360: class Entry {
361:
362: private int start;
363: private int end;
364:
365: Entry(int number) {
366: start = number;
367: end = number;
368: }
369:
370: /**
371: * Returns -1 if this interval represented by this entry precedes
372: * the number, 0 if the the number is contained in the interval,
373: * and -1 if the interval occurs after the number.
374: */
375: final int compareTo(int number) {
376: if (start > number)
377: return 1;
378: else if (end < number)
379: return -1;
380: else
381: return 0;
382: }
383:
384: final boolean contains(int number) {
385: return (number >= start && 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: }
|