1 /*
2 * Copyright (c) 2000, 2018, 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
32 package sun.security.krb5.internal.rcache;
33
34 import sun.security.krb5.internal.Krb5;
35
36 import java.util.Iterator;
37 import java.util.LinkedList;
38 import java.util.ListIterator;
39 import sun.security.krb5.internal.KerberosTime;
40 import 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 */
53 public class AuthList {
54
55 private final LinkedList<AuthTimeWithHash> entries;
56 private final int lifespan;
57
58 // entries.getLast().ctime, updated after each cleanup.
59 private volatile int oldestTime = Integer.MIN_VALUE;
60
61 /**
62 * Constructs a AuthList.
63 */
64 public AuthList(int lifespan) {
65 this.lifespan = lifespan;
66 entries = new LinkedList<>();
67 }
68
69 /**
70 * Puts the authenticator timestamp into the cache in descending order,
71 * and throw an exception if it's already there.
72 */
73 public void put(AuthTimeWithHash t, KerberosTime currentTime)
74 throws KrbApErrException {
75
76 if (entries.isEmpty()) {
77 entries.addFirst(t);
78 oldestTime = t.ctime;
79 return;
80 } else {
81 AuthTimeWithHash temp = entries.getFirst();
82 int cmp = temp.compareTo(t);
83 if (cmp < 0) {
84 // This is the most common case, newly received authenticator
85 // has larger timestamp.
86 entries.addFirst(t);
87 } else if (cmp == 0) {
88 throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);
89 } else {
90 //unless client clock being re-adjusted.
91 ListIterator<AuthTimeWithHash> it = entries.listIterator(1);
92 boolean found = false;
93 while (it.hasNext()) {
94 temp = it.next();
95 cmp = temp.compareTo(t);
96 if (cmp < 0) {
97 // Find an older one, put in front of it
98 entries.add(entries.indexOf(temp), t);
99 found = true;
100 break;
101 } else if (cmp == 0) {
102 throw new KrbApErrException(Krb5.KRB_AP_ERR_REPEAT);
103 }
104 }
105 if (!found) {
106 // All is newer than the newcomer. Sigh.
107 entries.addLast(t);
108 }
109 }
110 }
111
112 // let us cleanup while we are here
113 long timeLimit = currentTime.getSeconds() - lifespan;
114 long veryOld = timeLimit - (lifespan > 60 ? 60 : lifespan);
115
116 // Only trigger a cleanup when very old entries exist
117 // (lifespan + 1 min ago). This ensures a cleanup is done
118 // at most every minute.
119 if (oldestTime > veryOld) {
120 return;
121 }
122
123 // and we remove the *enough* old ones (1 lifetime ago)
124 ListIterator<AuthTimeWithHash> it = entries.listIterator(0);
125 AuthTimeWithHash temp;
126 while (it.hasNext()) {
127 // search expired timestamps.
128 temp = it.next();
129 if (temp.ctime < timeLimit) {
130 // It would be nice if ListIterator has a method called stripHere()
131 while (!entries.isEmpty()) {
132 if (entries.removeLast() == temp) {
133 break;
134 }
135 }
136 break;
137 }
138 }
139
140 AuthTimeWithHash last = entries.peekLast();
141 oldestTime = last == null ? Integer.MIN_VALUE : last.ctime;
142 }
143
144 public boolean isEmpty() {
145 return entries.isEmpty();
146 }
147
148 public String toString() {
149 StringBuilder sb = new StringBuilder();
150 Iterator<AuthTimeWithHash> iter = entries.descendingIterator();
151 int pos = entries.size();
152 while (iter.hasNext()) {
153 AuthTimeWithHash at = iter.next();
154 sb.append('#').append(pos--).append(": ")
155 .append(at.toString()).append('\n');
156 }
157 return sb.toString();
158 }
159 }