1/*
2 * Copyright (c) 2000, 2013, 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
26/*
27 *
28 *  (C) Copyright IBM Corp. 1999 All Rights Reserved.
29 *  Copyright 1997 The Open Group Research Institute.  All rights reserved.
30 */
31
32package sun.security.krb5.internal.rcache;
33
34import sun.security.krb5.internal.Krb5;
35
36import java.util.Iterator;
37import java.util.LinkedList;
38import java.util.ListIterator;
39import sun.security.krb5.internal.KerberosTime;
40import sun.security.krb5.internal.KrbApErrException;
41
42/**
43 * This class provides an efficient caching mechanism to store AuthTimeWithHash
44 * from client authenticators. The cache minimizes the memory usage by doing
45 * self-cleanup of expired items in the cache.
46 *
47 * AuthTimeWithHash objects inside a cache are always sorted from big (new) to
48 * small (old) as determined by {@link AuthTimeWithHash#compareTo}. In the most
49 * common case a newcomer should be newer than the first element.
50 *
51 * @author Yanni Zhang
52 */
53public class AuthList {
54
55    private final LinkedList<AuthTimeWithHash> entries;
56    private final int lifespan;
57
58    /**
59     * Constructs a AuthList.
60     */
61    public AuthList(int lifespan) {
62        this.lifespan = lifespan;
63        entries = new LinkedList<>();
64    }
65
66    /**
67     * Puts the authenticator timestamp into the cache in descending order,
68     * and throw an exception if it's already there.
69     */
70    public void put(AuthTimeWithHash t, KerberosTime currentTime)
71            throws KrbApErrException {
72
73        if (entries.isEmpty()) {
74            entries.addFirst(t);
75        } else {
76            AuthTimeWithHash temp = entries.getFirst();
77            int cmp = temp.compareTo(t);
78            if (cmp < 0) {
79                // This is the most common case, newly received authenticator
80                // has larger timestamp.
81                entries.addFirst(t);
82            } else if (cmp == 0) {
83                throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);
84            } else {
85                //unless client clock being re-adjusted.
86                ListIterator<AuthTimeWithHash> it = entries.listIterator(1);
87                boolean found = false;
88                while (it.hasNext()) {
89                    temp = it.next();
90                    cmp = temp.compareTo(t);
91                    if (cmp < 0) {
92                        // Find an older one, put in front of it
93                        entries.add(entries.indexOf(temp), t);
94                        found = true;
95                        break;
96                    } else if (cmp == 0) {
97                        throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);
98                    }
99                }
100                if (!found) {
101                    // All is newer than the newcomer. Sigh.
102                    entries.addLast(t);
103                }
104            }
105        }
106
107        // let us cleanup while we are here
108        long timeLimit = currentTime.getSeconds() - lifespan;
109        ListIterator<AuthTimeWithHash> it = entries.listIterator(0);
110        AuthTimeWithHash temp = null;
111        int index = -1;
112        while (it.hasNext()) {
113            // search expired timestamps.
114            temp = it.next();
115            if (temp.ctime < timeLimit) {
116                index = entries.indexOf(temp);
117                break;
118            }
119        }
120        // It would be nice if LinkedList has a method called truncate(index).
121        if (index > -1) {
122            do {
123                // remove expired timestamps from the list.
124                entries.removeLast();
125            } while(entries.size() > index);
126        }
127    }
128
129    public boolean isEmpty() {
130        return entries.isEmpty();
131    }
132
133    public String toString() {
134        StringBuilder sb = new StringBuilder();
135        Iterator<AuthTimeWithHash> iter = entries.descendingIterator();
136        int pos = entries.size();
137        while (iter.hasNext()) {
138            AuthTimeWithHash at = iter.next();
139            sb.append('#').append(pos--).append(": ")
140                    .append(at.toString()).append('\n');
141        }
142        return sb.toString();
143    }
144}
145