| /* | |
| * Copyright (c) 2000, 2022, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package sun.security.jgss; | |
| import org.ietf.jgss.MessageProp; | |
| import java.util.LinkedList; | |
| /** | |
| * A utility class that implements a number list that keeps track of which | |
| * tokens have arrived by storing their token numbers in the list. It helps | |
| * detect old tokens, out of sequence tokens, and duplicate tokens. | |
| * | |
| * Each element of the list is an interval [a, b]. Its existence in the | |
| * list implies that all token numbers in the range a, a+1, ..., b-1, b | |
| * have arrived. Gaps in arrived token numbers are represented by the | |
| * numbers that fall in between two elements of the list. e.g. {[a,b], | |
| * [c,d]} indicates that the token numbers b+1, ..., c-1 have not arrived | |
| * yet. | |
| * | |
| * The maximum number of intervals that we keep track of is | |
| * MAX_INTERVALS. Thus, if there are too many gaps, then some older | |
| * sequence numbers are deleted from the list. The earliest sequence number | |
| * that exists in the list is the windowStart. The next expected sequence | |
| * number, or expectedNumber, is one greater than the latest sequence | |
| * number in the list. | |
| * | |
| * The list keeps track the first token number that should have arrived | |
| * (initNumber) so that it is able to detect if certain numbers occur after | |
| * the first valid token number but before windowStart. That would happen | |
| * if the number of elements (intervals) exceeds MAX_INTERVALS and some | |
| * initial elements had to be deleted. | |
| * | |
| * The working of the list is optimized for the normal case where the | |
| * tokens arrive in sequence. | |
| * | |
| * @author Mayank Upadhyay | |
| * @since 1.4 | |
| */ | |
| public class TokenTracker { | |
| static final int MAX_INTERVALS = 5; | |
| private final int initNumber; | |
| private int windowStart; | |
| private int expectedNumber; | |
| private int windowStartIndex = 0; | |
| private final LinkedList<Entry> list = new LinkedList<>(); | |
| public TokenTracker(int initNumber) { | |
| this.initNumber = initNumber; | |
| this.windowStart = initNumber; | |
| this.expectedNumber = initNumber; | |
| // Make an entry with one less than the expected first token | |
| Entry entry = new Entry(initNumber - 1); | |
| list.add(entry); | |
| } | |
| /** | |
| * Returns the index for the entry into which this number will fit. If | |
| * there is none, it returns the index of the last interval | |
| * which precedes this number. It returns -1 if the number needs to be | |
| * a in a new interval ahead of the whole list. | |
| */ | |
| private int getIntervalIndex(int number) { | |
| Entry entry; | |
| int i; | |
| // Start from the rear to optimize for the normal case | |
| for (i = list.size() - 1; i >= 0; i--) { | |
| entry = list.get(i); | |
| if (entry.compareTo(number) <= 0) | |
| break; | |
| } | |
| return i; | |
| } | |
| /** | |
| * Sets the sequencing and replay information for the given token | |
| * number. | |
| * | |
| * The following represents the number line with positions of | |
| * initNumber, windowStart, expectedNumber marked on it. Regions in | |
| * between them show the different sequencing and replay state | |
| * possibilities for tokens that fall in there. | |
| * | |
| * (1) windowStart | |
| * initNumber expectedNumber | |
| * | | | |
| * ---|---------------------------|--- | |
| * GAP | DUP/UNSEQ | GAP | |
| * | |
| * | |
| * (2) initNumber windowStart expectedNumber | |
| * | | | | |
| * ---|---------------|--------------|--- | |
| * GAP | OLD | DUP/UNSEQ | GAP | |
| * | |
| * | |
| * (3) windowStart | |
| * expectedNumber initNumber | |
| * | | | |
| * ---|---------------------------|--- | |
| * DUP/UNSEQ | GAP | DUP/UNSEQ | |
| * | |
| * | |
| * (4) expectedNumber initNumber windowStart | |
| * | | | | |
| * ---|---------------|--------------|--- | |
| * DUP/UNSEQ | GAP | OLD | DUP/UNSEQ | |
| * | |
| * | |
| * | |
| * (5) windowStart expectedNumber initNumber | |
| * | | | | |
| * ---|---------------|--------------|--- | |
| * OLD | DUP/UNSEQ | GAP | OLD | |
| * | |
| * | |
| * | |
| * (This analysis leaves out the possibility that expectedNumber passes | |
| * initNumber after wrapping around. That may be added later.) | |
| */ | |
| public final synchronized void getProps(int number, MessageProp prop) { | |
| boolean gap = false; | |
| boolean old = false; | |
| boolean unsequenced = false; | |
| boolean duplicate = false; | |
| // System.out.println("\n\n=========="); | |
| // System.out.println("TokenTracker.getProps(): number=" + number); | |
| // System.out.println(toString()); | |
| int pos = getIntervalIndex(number); | |
| Entry entry = null; | |
| if (pos != -1) | |
| entry = list.get(pos); | |
| // Optimize for the expected case: | |
| if (number == expectedNumber) { | |
| expectedNumber++; | |
| } else { | |
| // Next trivial case is to check for duplicate | |
| if (entry != null && entry.contains(number)) | |
| duplicate = true; | |
| else { | |
| if (expectedNumber >= initNumber) { | |
| // Cases (1) and (2) | |
| if (number > expectedNumber) { | |
| gap = true; | |
| } else if (number >= windowStart) { | |
| unsequenced = true; | |
| } else if (number >= initNumber) { | |
| old = true; | |
| } else { | |
| gap = true; | |
| } | |
| } else { | |
| // Cases (3), (4) and (5) | |
| if (number > expectedNumber) { | |
| if (number < initNumber) { | |
| gap = true; | |
| } else if (windowStart >= initNumber) { | |
| if (number >= windowStart) { | |
| unsequenced = true; | |
| } else | |
| old = true; | |
| } else { | |
| old = true; | |
| } | |
| } else if (windowStart > expectedNumber) { | |
| unsequenced = true; | |
| } else if (number < windowStart) { | |
| old = true; | |
| } else | |
| unsequenced = true; | |
| } | |
| } | |
| } | |
| if (!duplicate && !old) | |
| add(number, pos); | |
| if (gap) | |
| expectedNumber = number+1; | |
| prop.setSupplementaryStates(duplicate, old, unsequenced, gap, | |
| 0, null); | |
| // System.out.println("Leaving with state:"); | |
| // System.out.println(toString()); | |
| // System.out.println("==========\n"); | |
| } | |
| /** | |
| * Adds the number to the list just after the entry that is currently | |
| * at position prevEntryPos. If prevEntryPos is -1, then the number | |
| * will begin a new interval at the front of the list. | |
| */ | |
| private void add(int number, int prevEntryPos) { | |
| Entry entry; | |
| Entry entryBefore = null; | |
| Entry entryAfter; | |
| boolean appended = false; | |
| boolean prepended = false; | |
| if (prevEntryPos != -1) { | |
| entryBefore = list.get(prevEntryPos); | |
| // Can this number simply be added to the previous interval? | |
| if (number == (entryBefore.getEnd() + 1)) { | |
| entryBefore.setEnd(number); | |
| appended = true; | |
| } | |
| } | |
| // Now check the interval that follows this number | |
| int nextEntryPos = prevEntryPos + 1; | |
| if ((nextEntryPos) < list.size()) { | |
| entryAfter = list.get(nextEntryPos); | |
| // Can this number simply be added to the next interval? | |
| if (number == (entryAfter.getStart() - 1)) { | |
| if (!appended) { | |
| entryAfter.setStart(number); | |
| } else { | |
| // Merge the two entries | |
| entryAfter.setStart(entryBefore.getStart()); | |
| list.remove(prevEntryPos); | |
| // Index of any entry following this gets decremented | |
| if (windowStartIndex > prevEntryPos) | |
| windowStartIndex--; | |
| } | |
| prepended = true; | |
| } | |
| } | |
| if (prepended || appended) | |
| return; | |
| /* | |
| * At this point we know that the number will start a new interval | |
| * which needs to be added to the list. We might have to recycle an | |
| * older entry in the list. | |
| */ | |
| if (list.size() < MAX_INTERVALS) { | |
| entry = new Entry(number); | |
| if (prevEntryPos < windowStartIndex) | |
| windowStartIndex++; // due to the insertion which will happen | |
| } else { | |
| /* | |
| * Delete the entry that marks the start of the current window. | |
| * The marker will automatically point to the next entry in the | |
| * list when this happens. If the current entry is at the end | |
| * of the list then set the marker to the start of the list. | |
| */ | |
| int oldWindowStartIndex = windowStartIndex; | |
| if (windowStartIndex == (list.size() - 1)) | |
| windowStartIndex = 0; | |
| entry = list.remove(oldWindowStartIndex); | |
| windowStart = list.get(windowStartIndex).getStart(); | |
| entry.setStart(number); | |
| entry.setEnd(number); | |
| if (prevEntryPos >= oldWindowStartIndex) { | |
| prevEntryPos--; // due to the deletion that just happened | |
| } else { | |
| /* | |
| * If the start of the current window just moved from the | |
| * end of the list to the front of the list, and if the new | |
| * entry will be added to the front of the list, then | |
| * the new entry is the actual window start. | |
| * eg, Consider { [-10, -8], ..., [-6, -3], [3, 9]}. In | |
| * this list, suppose the element [3, 9] is the start of | |
| * the window and has to be deleted to make place to add | |
| * [-12, -12]. The resultant list will be | |
| * {[-12, -12], [-10, -8], ..., [-6, -3]} and the new start | |
| * of the window should be the element [-12, -12], not | |
| * [-10, -8] which succeeded [3, 9] in the old list. | |
| */ | |
| if (oldWindowStartIndex != windowStartIndex) { | |
| // windowStartIndex is 0 at this point | |
| if (prevEntryPos == -1) | |
| // The new entry is going to the front | |
| windowStart = number; | |
| } else { | |
| // due to the insertion which will happen: | |
| windowStartIndex++; | |
| } | |
| } | |
| } | |
| // Finally, we are ready to actually add to the list at index | |
| // 'prevEntryPos+1' | |
| list.add(prevEntryPos+1, entry); | |
| } | |
| public String toString() { | |
| StringBuilder sb = new StringBuilder("TokenTracker: "); | |
| sb.append(" initNumber=").append(initNumber); | |
| sb.append(" windowStart=").append(windowStart); | |
| sb.append(" expectedNumber=").append(expectedNumber); | |
| sb.append(" windowStartIndex=").append(windowStartIndex); | |
| sb.append("\n\tIntervals are: {"); | |
| for (int i = 0; i < list.size(); i++) { | |
| if (i != 0) | |
| sb.append(", "); | |
| sb.append(list.get(i).toString()); | |
| } | |
| sb.append('}'); | |
| return sb.toString(); | |
| } | |
| /** | |
| * An entry in the list that represents the sequence of received | |
| * tokens. Each entry is actually an interval of numbers, all of which | |
| * have been received. | |
| */ | |
| static class Entry { | |
| private int start; | |
| private int end; | |
| Entry(int number) { | |
| start = number; | |
| end = number; | |
| } | |
| /** | |
| * Returns -1 if this interval represented by this entry precedes | |
| * the number, 0 if the number is contained in the interval, | |
| * and -1 if the interval occurs after the number. | |
| */ | |
| final int compareTo(int number) { | |
| if (start > number) | |
| return 1; | |
| else if (end < number) | |
| return -1; | |
| else | |
| return 0; | |
| } | |
| final boolean contains(int number) { | |
| return (number >= start && | |
| number <= end); | |
| } | |
| final void append(int number) { | |
| if (number == (end + 1)) | |
| end = number; | |
| } | |
| final void setInterval(int start, int end) { | |
| this.start = start; | |
| this.end = end; | |
| } | |
| final void setEnd(int end) { | |
| this.end = end; | |
| } | |
| final void setStart(int start) { | |
| this.start = start; | |
| } | |
| final int getStart() { | |
| return start; | |
| } | |
| final int getEnd() { | |
| return end; | |
| } | |
| public String toString() { | |
| return ("[" + start + ", " + end + "]"); | |
| } | |
| } | |
| } |