1 | /* |
2 | * Copyright 2004-2014 H2 Group. Multiple-Licensed under the MPL 2.0, |
3 | * and the EPL 1.0 (http://h2database.com/html/license.html). |
4 | * Initial Developer: H2 Group |
5 | */ |
6 | package org.h2.util; |
7 | |
8 | import java.util.ArrayList; |
9 | import java.util.Collections; |
10 | import java.util.Map; |
11 | import org.h2.engine.Constants; |
12 | import org.h2.engine.SysProperties; |
13 | import org.h2.message.DbException; |
14 | |
15 | /** |
16 | * A cache implementation based on the last recently used (LRU) algorithm. |
17 | */ |
18 | public class CacheLRU implements Cache { |
19 | |
20 | static final String TYPE_NAME = "LRU"; |
21 | |
22 | private final CacheWriter writer; |
23 | |
24 | /** |
25 | * Use First-In-First-Out (don't move recently used items to the front of |
26 | * the queue). |
27 | */ |
28 | private final boolean fifo; |
29 | |
30 | private final CacheObject head = new CacheHead(); |
31 | private final int mask; |
32 | private CacheObject[] values; |
33 | private int recordCount; |
34 | |
35 | /** |
36 | * The number of cache buckets. |
37 | */ |
38 | private final int len; |
39 | |
40 | /** |
41 | * The maximum memory, in words (4 bytes each). |
42 | */ |
43 | private int maxMemory; |
44 | |
45 | /** |
46 | * The current memory used in this cache, in words (4 bytes each). |
47 | */ |
48 | private int memory; |
49 | |
50 | CacheLRU(CacheWriter writer, int maxMemoryKb, boolean fifo) { |
51 | this.writer = writer; |
52 | this.fifo = fifo; |
53 | this.setMaxMemory(maxMemoryKb); |
54 | this.len = MathUtils.nextPowerOf2(maxMemory / 64); |
55 | this.mask = len - 1; |
56 | clear(); |
57 | } |
58 | |
59 | /** |
60 | * Create a cache of the given type and size. |
61 | * |
62 | * @param writer the cache writer |
63 | * @param cacheType the cache type |
64 | * @param cacheSize the size |
65 | * @return the cache object |
66 | */ |
67 | public static Cache getCache(CacheWriter writer, String cacheType, |
68 | int cacheSize) { |
69 | Map<Integer, CacheObject> secondLevel = null; |
70 | if (cacheType.startsWith("SOFT_")) { |
71 | secondLevel = new SoftHashMap<Integer, CacheObject>(); |
72 | cacheType = cacheType.substring("SOFT_".length()); |
73 | } |
74 | Cache cache; |
75 | if (CacheLRU.TYPE_NAME.equals(cacheType)) { |
76 | cache = new CacheLRU(writer, cacheSize, false); |
77 | } else if (CacheTQ.TYPE_NAME.equals(cacheType)) { |
78 | cache = new CacheTQ(writer, cacheSize); |
79 | } else { |
80 | throw DbException.getInvalidValueException("CACHE_TYPE", cacheType); |
81 | } |
82 | if (secondLevel != null) { |
83 | cache = new CacheSecondLevel(cache, secondLevel); |
84 | } |
85 | return cache; |
86 | } |
87 | |
88 | @Override |
89 | public void clear() { |
90 | head.cacheNext = head.cachePrevious = head; |
91 | // first set to null - avoiding out of memory |
92 | values = null; |
93 | values = new CacheObject[len]; |
94 | recordCount = 0; |
95 | memory = len * Constants.MEMORY_POINTER; |
96 | } |
97 | |
98 | @Override |
99 | public void put(CacheObject rec) { |
100 | if (SysProperties.CHECK) { |
101 | int pos = rec.getPos(); |
102 | CacheObject old = find(pos); |
103 | if (old != null) { |
104 | DbException |
105 | .throwInternalError("try to add a record twice at pos " + |
106 | pos); |
107 | } |
108 | } |
109 | int index = rec.getPos() & mask; |
110 | rec.cacheChained = values[index]; |
111 | values[index] = rec; |
112 | recordCount++; |
113 | memory += rec.getMemory(); |
114 | addToFront(rec); |
115 | removeOldIfRequired(); |
116 | } |
117 | |
118 | @Override |
119 | public CacheObject update(int pos, CacheObject rec) { |
120 | CacheObject old = find(pos); |
121 | if (old == null) { |
122 | put(rec); |
123 | } else { |
124 | if (SysProperties.CHECK) { |
125 | if (old != rec) { |
126 | DbException.throwInternalError("old!=record pos:" + pos + |
127 | " old:" + old + " new:" + rec); |
128 | } |
129 | } |
130 | if (!fifo) { |
131 | removeFromLinkedList(rec); |
132 | addToFront(rec); |
133 | } |
134 | } |
135 | return old; |
136 | } |
137 | |
138 | private void removeOldIfRequired() { |
139 | // a small method, to allow inlining |
140 | if (memory >= maxMemory) { |
141 | removeOld(); |
142 | } |
143 | } |
144 | |
145 | private void removeOld() { |
146 | int i = 0; |
147 | ArrayList<CacheObject> changed = New.arrayList(); |
148 | int mem = memory; |
149 | int rc = recordCount; |
150 | boolean flushed = false; |
151 | CacheObject next = head.cacheNext; |
152 | while (true) { |
153 | if (rc <= Constants.CACHE_MIN_RECORDS) { |
154 | break; |
155 | } |
156 | if (changed.size() == 0) { |
157 | if (mem <= maxMemory) { |
158 | break; |
159 | } |
160 | } else { |
161 | if (mem * 4 <= maxMemory * 3) { |
162 | break; |
163 | } |
164 | } |
165 | CacheObject check = next; |
166 | next = check.cacheNext; |
167 | i++; |
168 | if (i >= recordCount) { |
169 | if (!flushed) { |
170 | writer.flushLog(); |
171 | flushed = true; |
172 | i = 0; |
173 | } else { |
174 | // can't remove any record, because the records can not be |
175 | // removed hopefully this does not happen frequently, but it |
176 | // can happen |
177 | writer.getTrace() |
178 | .info("cannot remove records, cache size too small? records:" + |
179 | recordCount + " memory:" + memory); |
180 | break; |
181 | } |
182 | } |
183 | if (SysProperties.CHECK && check == head) { |
184 | DbException.throwInternalError("try to remove head"); |
185 | } |
186 | // we are not allowed to remove it if the log is not yet written |
187 | // (because we need to log before writing the data) |
188 | // also, can't write it if the record is pinned |
189 | if (!check.canRemove()) { |
190 | removeFromLinkedList(check); |
191 | addToFront(check); |
192 | continue; |
193 | } |
194 | rc--; |
195 | mem -= check.getMemory(); |
196 | if (check.isChanged()) { |
197 | changed.add(check); |
198 | } else { |
199 | remove(check.getPos()); |
200 | } |
201 | } |
202 | if (changed.size() > 0) { |
203 | if (!flushed) { |
204 | writer.flushLog(); |
205 | } |
206 | Collections.sort(changed); |
207 | int max = maxMemory; |
208 | int size = changed.size(); |
209 | try { |
210 | // temporary disable size checking, |
211 | // to avoid stack overflow |
212 | maxMemory = Integer.MAX_VALUE; |
213 | for (i = 0; i < size; i++) { |
214 | CacheObject rec = changed.get(i); |
215 | writer.writeBack(rec); |
216 | } |
217 | } finally { |
218 | maxMemory = max; |
219 | } |
220 | for (i = 0; i < size; i++) { |
221 | CacheObject rec = changed.get(i); |
222 | remove(rec.getPos()); |
223 | if (SysProperties.CHECK) { |
224 | if (rec.cacheNext != null) { |
225 | throw DbException.throwInternalError(); |
226 | } |
227 | } |
228 | } |
229 | } |
230 | } |
231 | |
232 | private void addToFront(CacheObject rec) { |
233 | if (SysProperties.CHECK && rec == head) { |
234 | DbException.throwInternalError("try to move head"); |
235 | } |
236 | rec.cacheNext = head; |
237 | rec.cachePrevious = head.cachePrevious; |
238 | rec.cachePrevious.cacheNext = rec; |
239 | head.cachePrevious = rec; |
240 | } |
241 | |
242 | private void removeFromLinkedList(CacheObject rec) { |
243 | if (SysProperties.CHECK && rec == head) { |
244 | DbException.throwInternalError("try to remove head"); |
245 | } |
246 | rec.cachePrevious.cacheNext = rec.cacheNext; |
247 | rec.cacheNext.cachePrevious = rec.cachePrevious; |
248 | // TODO cache: mystery: why is this required? needs more memory if we |
249 | // don't do this |
250 | rec.cacheNext = null; |
251 | rec.cachePrevious = null; |
252 | } |
253 | |
254 | @Override |
255 | public boolean remove(int pos) { |
256 | int index = pos & mask; |
257 | CacheObject rec = values[index]; |
258 | if (rec == null) { |
259 | return false; |
260 | } |
261 | if (rec.getPos() == pos) { |
262 | values[index] = rec.cacheChained; |
263 | } else { |
264 | CacheObject last; |
265 | do { |
266 | last = rec; |
267 | rec = rec.cacheChained; |
268 | if (rec == null) { |
269 | return false; |
270 | } |
271 | } while (rec.getPos() != pos); |
272 | last.cacheChained = rec.cacheChained; |
273 | } |
274 | recordCount--; |
275 | memory -= rec.getMemory(); |
276 | removeFromLinkedList(rec); |
277 | if (SysProperties.CHECK) { |
278 | rec.cacheChained = null; |
279 | CacheObject o = find(pos); |
280 | if (o != null) { |
281 | DbException.throwInternalError("not removed: " + o); |
282 | } |
283 | } |
284 | return true; |
285 | } |
286 | |
287 | @Override |
288 | public CacheObject find(int pos) { |
289 | CacheObject rec = values[pos & mask]; |
290 | while (rec != null && rec.getPos() != pos) { |
291 | rec = rec.cacheChained; |
292 | } |
293 | return rec; |
294 | } |
295 | |
296 | @Override |
297 | public CacheObject get(int pos) { |
298 | CacheObject rec = find(pos); |
299 | if (rec != null) { |
300 | if (!fifo) { |
301 | removeFromLinkedList(rec); |
302 | addToFront(rec); |
303 | } |
304 | } |
305 | return rec; |
306 | } |
307 | |
308 | // private void testConsistency() { |
309 | // int s = size; |
310 | // HashSet set = new HashSet(); |
311 | // for(int i=0; i<values.length; i++) { |
312 | // Record rec = values[i]; |
313 | // if(rec == null) { |
314 | // continue; |
315 | // } |
316 | // set.add(rec); |
317 | // while(rec.chained != null) { |
318 | // rec = rec.chained; |
319 | // set.add(rec); |
320 | // } |
321 | // } |
322 | // Record rec = head.next; |
323 | // while(rec != head) { |
324 | // set.add(rec); |
325 | // rec = rec.next; |
326 | // } |
327 | // rec = head.previous; |
328 | // while(rec != head) { |
329 | // set.add(rec); |
330 | // rec = rec.previous; |
331 | // } |
332 | // if(set.size() != size) { |
333 | // System.out.println("size="+size+" but el.size="+set.size()); |
334 | // } |
335 | // } |
336 | |
337 | @Override |
338 | public ArrayList<CacheObject> getAllChanged() { |
339 | // if(Database.CHECK) { |
340 | // testConsistency(); |
341 | // } |
342 | ArrayList<CacheObject> list = New.arrayList(); |
343 | CacheObject rec = head.cacheNext; |
344 | while (rec != head) { |
345 | if (rec.isChanged()) { |
346 | list.add(rec); |
347 | } |
348 | rec = rec.cacheNext; |
349 | } |
350 | return list; |
351 | } |
352 | |
353 | @Override |
354 | public void setMaxMemory(int maxKb) { |
355 | int newSize = MathUtils.convertLongToInt(maxKb * 1024L / 4); |
356 | maxMemory = newSize < 0 ? 0 : newSize; |
357 | // can not resize, otherwise existing records are lost |
358 | // resize(maxSize); |
359 | removeOldIfRequired(); |
360 | } |
361 | |
362 | @Override |
363 | public int getMaxMemory() { |
364 | return (int) (maxMemory * 4L / 1024); |
365 | } |
366 | |
367 | @Override |
368 | public int getMemory() { |
369 | // CacheObject rec = head.cacheNext; |
370 | // while (rec != head) { |
371 | // System.out.println(rec.getMemory() + " " + |
372 | // MemoryFootprint.getObjectSize(rec) + " " + rec); |
373 | // rec = rec.cacheNext; |
374 | // } |
375 | return (int) (memory * 4L / 1024); |
376 | } |
377 | |
378 | } |