Back to index...

	/*
	* Copyright (c) 2000, 2006, 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. eg. {[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 of the 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 int initNumber;
	private int windowStart;
	private int expectedNumber;

	private int windowStartIndex = 0;

	private LinkedList<Entry> list = new LinkedList<Entry>();

	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 = null;
	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
	* possibilites 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.)
	*/
	synchronized public final 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 = null;

	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 recyle 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() {
	StringBuffer buf = new StringBuffer("TokenTracker: ");
	buf.append(" initNumber=").append(initNumber);
	buf.append(" windowStart=").append(windowStart);
	buf.append(" expectedNumber=").append(expectedNumber);
	buf.append(" windowStartIndex=").append(windowStartIndex);
	buf.append("\n\tIntervals are: {");
	for (int i = 0; i < list.size(); i++) {
	if (i != 0)
	buf.append(", ");
	buf.append(list.get(i).toString());
	}
	buf.append('}');
	return buf.toString();
	}

	/**
	* An entry in the list that represents the sequence of received
	* tokens. Each entry is actaully an interval of numbers, all of which
	* have been received.
	*/
	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 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 + "]");
	}

	}
	}

Back to index...