I fixed a couple of issues with my previous patch, but it appears I
still don't understand the rules around allocating/de-allocating chunks,
especially in the presence of rollback, which means that the freelist
still gets out of sync.
--
You received this message because you are subscribed to the Google Groups "H2
Database" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/h2-database?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
Index: src/main/org/h2/mvstore/Chunk.java
===================================================================
--- src/main/org/h2/mvstore/Chunk.java (revision 4708)
+++ src/main/org/h2/mvstore/Chunk.java (working copy)
@@ -42,7 +42,7 @@
int length;
/**
- * The number of pages.
+ * The number of times the page has been written.
*/
int pageCount;
Index: src/main/org/h2/mvstore/FreeSpaceList.java
===================================================================
--- src/main/org/h2/mvstore/FreeSpaceList.java (revision 0)
+++ src/main/org/h2/mvstore/FreeSpaceList.java (working copy)
@@ -0,0 +1,139 @@
+package org.h2.mvstore;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class FreeSpaceList {
+
+ // the first 2 pages are occupied by the file header
+ private static final int FIRST_FREE_PAGE = 3;
+
+ private List<PageRange> freeSpaceList = new ArrayList<PageRange>();
+
+ public FreeSpaceList() {
+ freeSpaceList.add(new PageRange(FIRST_FREE_PAGE, Integer.MAX_VALUE));
+ }
+
+ private static final class PageRange {
+ /** the start point, in pages */
+ public long start;
+ /** the length, in pages */
+ public int length;
+
+ public PageRange(long start, int length) {
+ this.start = start;
+ this.length = length;
+ }
+
+ @Override
+ public String toString() {
+ return "start:" + start + " length:" + length;
+ }
+ }
+
+ /**
+ * @return position in pages
+ */
+ public synchronized long allocatePages(long length) {
+ long required = (length / MVStore.BLOCK_SIZE) + 1;
+ System.out.println("allocatePages : required " + required);
+ for (PageRange pr : freeSpaceList) {
+ if (pr.length >= required) {
+ return pr.start;
+ }
+ }
+ throw new IllegalStateException("could not find a free page to
allocate");
+ }
+
+ public synchronized void markUsed(Chunk c) {
+ long chunkStart = c.start / MVStore.BLOCK_SIZE;
+ int required = (c.length / MVStore.BLOCK_SIZE) + 1;
+ System.out.println("markUsed : chunk ID: " + c.id + " chunkStart:" +
chunkStart + " required:" + required);
+ PageRange found = null;
+ int i = 0;
+ for (PageRange pr : freeSpaceList) {
+ if (pr.start <= chunkStart) {
+ found = pr;
+ break;
+ }
+ i++;
+ }
+ if (found == null) {
+ throw new IllegalStateException("cannot find spot to mark chunk as
used in free list, " + c.toString());
+ }
+ if (found.start == chunkStart) {
+ // if the used-chunk is at the beginning of a free-space-range
+ found.start += required;
+ } else if (found.start + found.length == chunkStart + required) {
+ // if the used-chunk is at the end of a free-space-range
+ found.length -= required;
+ } else {
+ // it's in the middle, so split the existing entry
+ int length1 = (int) (chunkStart - found.start);
+ long start2 = chunkStart + required;
+ int length2 = (int) (found.start + found.length - chunkStart -
required);
+
+ found.length = length1;
+ PageRange newRange = new PageRange(start2, length2);
+ freeSpaceList.add(i, newRange);
+ }
+ }
+
+ public synchronized void markFree(Chunk c) {
+ long chunkStart = c.start / MVStore.BLOCK_SIZE;
+ int required = (c.length / MVStore.BLOCK_SIZE) + 1;
+ System.out.println("markFree : chunk ID: " + c.id + " chunkStart:" +
chunkStart + " required:" + required);
+ PageRange found = null;
+ int i = 0;
+ for (PageRange pr : freeSpaceList) {
+ if (pr.start > chunkStart) {
+ found = pr;
+ break;
+ }
+ i++;
+ }
+ if (found == null) {
+ throw new IllegalStateException("cannot find spot to mark chunk as
unused in free list, " + c.toString());
+ }
+ if (chunkStart + required + 1 == found.start) {
+ // if the used-chunk is adjacent to the beginning of a
+ // free-space-range
+ found.start = chunkStart;
+ found.length += required;
+ // compactify-free-list: merge the previous entry into this one if
+ // they are now adjacent
+ if (i > 0) {
+ PageRange previous = freeSpaceList.get(i - 1);
+ if (previous.start + previous.length + 1 == found.start) {
+ previous.length += found.length;
+ freeSpaceList.remove(i);
+ }
+ }
+ return;
+ }
+ if (i > 0) {
+ // if the used-chunk is adjacent to the end of a free-space-range
+ PageRange previous = freeSpaceList.get(i - 1);
+ if (previous.start + previous.length + 1 == chunkStart) {
+ previous.length += required;
+ // compactify-free-list: merge the next entry into this one if
+ // they are now adjacent
+ if (previous.start + previous.length + 1 == found.start) {
+ previous.length += found.length;
+ freeSpaceList.remove(i);
+ }
+ return;
+ }
+ }
+
+ // it is between 2 entries, so add a new one
+ PageRange newRange = new PageRange(chunkStart, required);
+ freeSpaceList.add(i, newRange);
+ }
+
+ public synchronized void clear() {
+ System.out.println("clear");
+ freeSpaceList.clear();
+ freeSpaceList.add(new PageRange(FIRST_FREE_PAGE, Integer.MAX_VALUE));
+ }
+}
Index: src/main/org/h2/mvstore/MVStore.java
===================================================================
--- src/main/org/h2/mvstore/MVStore.java (revision 4708)
+++ src/main/org/h2/mvstore/MVStore.java (working copy)
@@ -12,12 +12,12 @@
import java.nio.channels.FileLock;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
+import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import org.h2.compress.CompressLZF;
import org.h2.compress.Compressor;
@@ -148,7 +148,12 @@
*/
private final ConcurrentHashMap<Integer, Chunk> chunks =
new ConcurrentHashMap<Integer, Chunk>();
+ /**
+ * The list of free spaces between the chunks.
+ */
+ private FreeSpaceList freeSpaceList = new FreeSpaceList();
+
/**
* The map of temporarily freed entries in the chunks. The key is the
* unsaved version, the value is the map of chunks. The maps of chunks
@@ -564,6 +569,11 @@
lastChunkId = Math.max(c.id, lastChunkId);
chunks.put(c.id, c);
}
+ // rebuild the free space list
+ freeSpaceList.clear();
+ for (Chunk c : chunks.values()) {
+ freeSpaceList.markUsed(c);
+ }
}
private void readFileHeader() {
@@ -694,6 +704,7 @@
}
meta = null;
chunks.clear();
+ freeSpaceList.clear();
cache.clear();
maps.clear();
} catch (Exception e) {
@@ -845,7 +856,7 @@
}
applyFreedChunks(storeVersion);
- ArrayList<Integer> removedChunks = New.arrayList();
+ Set<Integer> removedChunks = New.hashSet();
// do it twice, because changing the meta table
// could cause a chunk to become empty
for (int i = 0; i < 2; i++) {
@@ -900,7 +911,7 @@
buff.limit(length);
long fileLength = getFileLengthUsed();
- long filePos = reuseSpace ? allocateChunk(length) : fileLength;
+ long filePos = reuseSpace ? allocateChunk(chunkLength) : fileLength;
boolean storeAtEndOfFile = filePos + length >= fileLength;
// need to keep old chunks
@@ -908,11 +919,13 @@
// by an old version
// so empty space is not reused too early
for (int x : removedChunks) {
+ freeSpaceList.markFree(chunks.get(x));
chunks.remove(x);
}
c.start = filePos;
c.length = chunkLength;
+ freeSpaceList.markUsed(c);
c.metaRootPos = meta.getRoot().getPos();
buff.position(0);
c.writeHeader(buff);
@@ -1024,33 +1037,7 @@
}
private long allocateChunk(long length) {
- BitSet set = new BitSet();
- set.set(0);
- set.set(1);
- for (Chunk c : chunks.values()) {
- if (c.start == Long.MAX_VALUE) {
- continue;
- }
- int first = (int) (c.start / BLOCK_SIZE);
- int last = (int) ((c.start + c.length) / BLOCK_SIZE);
- set.set(first, last + 2);
- }
- int required = (int) (length / BLOCK_SIZE) + 1;
- for (int i = 0; i < set.size(); i++) {
- if (!set.get(i)) {
- boolean ok = true;
- for (int j = 0; j < required; j++) {
- if (set.get(i + j)) {
- ok = false;
- break;
- }
- }
- if (ok) {
- return i * BLOCK_SIZE;
- }
- }
- }
- return set.size() * BLOCK_SIZE;
+ return freeSpaceList.allocatePages(length) * BLOCK_SIZE;
}
/**
@@ -1488,6 +1475,7 @@
}
meta.clear();
chunks.clear();
+ freeSpaceList.clear();
maps.clear();
synchronized (freedChunks) {
freedChunks.clear();
@@ -1517,6 +1505,7 @@
revertTemp(version);
loadFromFile = true;
do {
+ freeSpaceList.markFree(chunks.get(lastChunkId));
last = chunks.remove(lastChunkId);
lastChunkId--;
} while (last.version > version && chunks.size() > 0);
Index: src/test/org/h2/test/store/TestMVStore.java
===================================================================
--- src/test/org/h2/test/store/TestMVStore.java (revision 4708)
+++ src/test/org/h2/test/store/TestMVStore.java (working copy)
@@ -79,6 +79,10 @@
testIterate();
testCloseTwice();
testSimple();
+ // this test will run out of memory on a 32-bit VM
+ if ("64".equals(System.getProperty("sun.arch.data.model"))) {
+ testLargerThan2G();
+ }
}
private void testAtomicOperations() {
@@ -1392,7 +1396,33 @@
}
s.close();
}
+
+ private void testLargerThan2G() {
+ String fileName = getBaseDir() + "/testLargerThan2G.h3";
+ FileUtils.delete(fileName);
+
+ MVStore store = new
MVStore.Builder().cacheSize(800).fileName(fileName).writeBufferSize(0).writeDelay(-1)
+ .open();
+ MVMap<String, String> map = store.openMap("test");
+ int totalWrite = 15000000;
+ int lineStored = 0;
+ while (lineStored <= totalWrite) {
+ lineStored++;
+ String actualKey = lineStored + " just for length
hhhhhhhhhhhhhhhhh" + lineStored;
+ String value = "Just a a string that is kinda longgggggggggggg but
not too much AAAAAAAAAAAAAAAAAAAAA hhhhhhhhhhhhhhhhhh"
+ + lineStored;
+
+ map.put(actualKey, value);
+
+ if (lineStored % 1000000 == 0) {
+ store.store();
+ }
+ }
+ store.store();
+ store.close();
+ }
+
/**
* Open a store for the given file name, using a small page size.
*
