1 /*
2  * JBoss, Home of Professional Open Source.
3  * Copyright 2014 Red Hat, Inc., and individual contributors
4  * as indicated by the @author tags.
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  *     http://www.apache.org/licenses/LICENSE-2.0
11  *
12  *  Unless required by applicable law or agreed to in writing, software
13  *  distributed under the License is distributed on an "AS IS" BASIS,
14  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  *  See the License for the specific language governing permissions and
16  *  limitations under the License.
17  */
18
19 package io.undertow.server.handlers.cache;
20
21 import java.util.concurrent.ConcurrentHashMap;
22 import java.util.concurrent.ConcurrentMap;
23 import java.util.concurrent.atomic.AtomicIntegerFieldUpdater;
24 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
25
26 import io.undertow.util.ConcurrentDirectDeque;
27
28 /**
29  * A non-blocking cache where entries are indexed by a key.
30  * <p>
31  * <p>To reduce contention, entry allocation and eviction execute in a sampling
32  * fashion (entry hits modulo N). Eviction follows an LRU approach (oldest sampled
33  * entries are removed first) when the cache is out of capacity.</p>
34  * <p>
35  *
36  * This cache can also be configured to run in FIFO mode, rather than LRU.
37  *
38  * @author Jason T. Greene
39  * @author Stuart Douglas
40  */
41 public class LRUCache<K, V> {
42     private static final int SAMPLE_INTERVAL = 5;
43
44     /**
45      * Max active entries that are present in the cache.
46      */
47     private final int maxEntries;
48
49     private final ConcurrentMap<K, CacheEntry<K, V>> cache;
50     private final ConcurrentDirectDeque<CacheEntry<K, V>> accessQueue;
51     /**
52      * How long an item can stay in the cache in milliseconds
53      */
54     private final int maxAge;
55     private final boolean fifo;
56
57     public LRUCache(int maxEntries, final int maxAge) {
58         this.maxAge = maxAge;
59         this.cache = new ConcurrentHashMap<>(16);
60         this.accessQueue = ConcurrentDirectDeque.newInstance();
61         this.maxEntries = maxEntries;
62         this.fifo = false;
63     }
64     public LRUCache(int maxEntries, final int maxAge, boolean fifo) {
65         this.maxAge = maxAge;
66         this.cache = new ConcurrentHashMap<>(16);
67         this.accessQueue = ConcurrentDirectDeque.newInstance();
68         this.maxEntries = maxEntries;
69         this.fifo = fifo;
70     }
71
72     public void add(K key, V newValue) {
73         CacheEntry<K, V> value = cache.get(key);
74         if (value == null) {
75             long expires;
76             if(maxAge == -1) {
77                 expires = -1;
78             } else {
79                 expires = System.currentTimeMillis() + maxAge;
80             }
81             value = new CacheEntry<>(key, newValue, expires);
82             CacheEntry result = cache.putIfAbsent(key, value);
83             if (result != null) {
84                 value = result;
85                 value.setValue(newValue);
86             }
87             bumpAccess(value);
88             if (cache.size() > maxEntries) {
89                 //remove the oldest
90                 CacheEntry<K, V> oldest = accessQueue.poll();
91                 if (oldest != value) {
92                     this.remove(oldest.key());
93                 }
94             }
95         }
96     }
97
98     public V get(K key) {
99         CacheEntry<K, V> cacheEntry = cache.get(key);
100         if (cacheEntry == null) {
101             return null;
102         }
103         long expires = cacheEntry.getExpires();
104         if(expires != -1) {
105             if(System.currentTimeMillis() > expires) {
106                 remove(key);
107                 return null;
108             }
109         }
110
111         if(!fifo) {
112             if (cacheEntry.hit() % SAMPLE_INTERVAL == 0) {
113                 bumpAccess(cacheEntry);
114             }
115         }
116
117         return cacheEntry.getValue();
118     }
119
120     private void bumpAccess(CacheEntry<K, V> cacheEntry) {
121         Object prevToken = cacheEntry.claimToken();
122         if (!Boolean.FALSE.equals(prevToken)) {
123             if (prevToken != null) {
124                 accessQueue.removeToken(prevToken);
125             }
126
127             Object token = null;
128             try {
129                 token = accessQueue.offerLastAndReturnToken(cacheEntry);
130             } catch (Throwable t) {
131                 // In case of disaster (OOME), we need to release the claim, so leave it aas null
132             }
133
134             if (!cacheEntry.setToken(token) && token != null) { // Always set if null
135                 accessQueue.removeToken(token);
136             }
137         }
138     }
139
140     public V remove(K key) {
141         CacheEntry<K, V> remove = cache.remove(key);
142         if (remove != null) {
143             Object old = remove.clearToken();
144             if (old != null) {
145                 accessQueue.removeToken(old);
146             }
147             return remove.getValue();
148         } else {
149             return null;
150         }
151     }
152
153     public void clear() {
154         cache.clear();
155         accessQueue.clear();
156     }
157
158     public static final class CacheEntry<K, V> {
159
160         private static final Object CLAIM_TOKEN = new Object();
161
162         private static final AtomicIntegerFieldUpdater<CacheEntry> hitsUpdater = AtomicIntegerFieldUpdater.newUpdater(CacheEntry.class, "hits");
163
164         private static final AtomicReferenceFieldUpdater<CacheEntry, Object> tokenUpdator = AtomicReferenceFieldUpdater.newUpdater(CacheEntry.class, Object.class, "accessToken");
165
166         private final K key;
167         private volatile V value;
168         private final long expires;
169         private volatile int hits = 1;
170         private volatile Object accessToken;
171
172         private CacheEntry(K key, V value, final long expires) {
173             this.key = key;
174             this.value = value;
175             this.expires = expires;
176         }
177
178         public void setValue(final V value) {
179             this.value = value;
180         }
181
182         public V getValue() {
183             return value;
184         }
185
186         public int hit() {
187             for (; ; ) {
188                 int i = hits;
189
190                 if (hitsUpdater.weakCompareAndSet(this, i, ++i)) {
191                     return i;
192                 }
193
194             }
195         }
196
197         public K key() {
198             return key;
199         }
200
201         Object claimToken() {
202             for (; ; ) {
203                 Object current = this.accessToken;
204                 if (current == CLAIM_TOKEN) {
205                     return Boolean.FALSE;
206                 }
207
208                 if (tokenUpdator.compareAndSet(this, current, CLAIM_TOKEN)) {
209                     return current;
210                 }
211             }
212         }
213
214         boolean setToken(Object token) {
215             return tokenUpdator.compareAndSet(this, CLAIM_TOKEN, token);
216         }
217
218         Object clearToken() {
219             Object old = tokenUpdator.getAndSet(this, null);
220             return old == CLAIM_TOKEN ? null : old;
221         }
222
223         public long getExpires() {
224             return expires;
225         }
226     }
227 }
228