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 
  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     /**
  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 }