[freenet-cvs] r19891 - branches/saltedhashstore/freenet/src/…

Author: j16sdiz
Date: 2008-05-11 10:24:22 +0000 (Sun, 11 May 2008)
New Revision: 19891

Modified:
branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
Log:
Quadratic Probing (datastore resize disabled)


Modified: branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java
===================================================================
--- branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java    2008-05-11 09:08:40 UTC (rev 19890)
+++ branches/saltedhashstore/freenet/src/freenet/store/SaltedHashFreenetStore.java    2008-05-11 10:24:22 UTC (rev 19891)
@@ -126,22 +126,29 @@

    private Entry probeEntry0(byte[] routingKey, long probeStoreSize) throws IOException {
        Entry entry;
-        long offset = getOffsetFromPlainKey(routingKey, probeStoreSize);
+        long[] offset = getOffsetFromPlainKey(routingKey, probeStoreSize);

-        if (!lockEntry(offset)) {
-            Logger.error(this, "can't lock entry: " + offset);
-            return null;
+        for (int i = 0; i < offset.length; i++) {
+            if (logDEBUG)
+                Logger.debug(this, "probing for i=" + i + ", offset=" + offset[i]);
+            
+            if (!lockEntry(offset[i])) {
+                Logger.error(this, "can't lock entry: " + offset[i]);
+                continue;
+            }
+            try {
+                entry = readEntry(offset[i], routingKey);
+            } catch (EOFException e) {
+                // may occur on resize, silent it a bit
+                Logger.error(this, "EOFException on probeEntry", e);
+                return null;
+            } finally {
+                unlockEntry(offset[i]);
+            }
+            if (entry != null)
+                return entry;
        }
-        try {
-            entry = readEntry(offset, routingKey);
-        } catch (EOFException e) {
-            // may occur on resize, silent it a bit
-            Logger.error(this, "EOFException on probeEntry", e);
-            return null;
-        } finally {
-            unlockEntry(offset);
-        }
-        return entry;
+        return null;
    }

    public void put(StorableBlock block, byte[] routingKey, byte[] fullKey, byte[] data, byte[] header,
@@ -163,16 +170,39 @@
        }

        Entry entry = new Entry(routingKey, header, data);
-        if (!lockEntry(entry.getOffset())) {
+        long[] offset = entry.getOffset();
+
+        for (int i = 0; i < offset.length; i++) {
+            if (!lockEntry(offset[i])) {
+                Logger.error(this, "can't lock entry: " + offset[i]);
+                return;
+            }
+            try {
+                if (isFree(offset[i], entry)) {
+                    if (logDEBUG)
+                        Logger.debug(this, "probing, write to i=" + i + ", offset=" + offset[i]);
+                    writeEntry(entry, offset[i]);
+                    incWrites();
+                    return;
+                }
+            } finally {
+                unlockEntry(offset[i]);
+            }
+        }
+
+        // no free blocks?
+        int i = random.nextInt(offset.length);
+        if (!lockEntry(offset[i])) {
            Logger.error(this, "can't lock entry: " + entry.getOffset());
-            incMisses();
            return;
        }
        try {
-            writeEntry(entry);
+            if (logDEBUG)
+                Logger.debug(this, "collision, write to i=" + i + ", offset=" + offset[i]);
+            writeEntry(entry, offset[i]);
            incWrites();
        } finally {
-            unlockEntry(entry.getOffset());
+            unlockEntry(offset[i]);
        }
    }

@@ -235,6 +265,7 @@
        private byte[] data;

        private boolean isEncrypted;
+        public long curOffset;

        /**
         * Create a new entry
@@ -352,7 +383,7 @@
            return block;
        }

-        public long getOffset() {
+        public long[] getOffset() {
            if (digestedRoutingKey != null)
                return getOffsetFromDigestedKey(digestedRoutingKey, storeSize);
            else
@@ -382,7 +413,8 @@
                }
            } else {
                // we do not know the plain key, let's check the digest
-                if (!Arrays.equals(this.digestedRoutingKey, getDigestedRoutingKey(routingKey)))
+                if (!Arrays.equals(this.digestedRoutingKey, SaltedHashFreenetStore.this
+                 .getDigestedRoutingKey(routingKey)))
                    return false;
            }

@@ -411,7 +443,7 @@
            header = cipher.blockEncipher(header, 0, header.length);
            data = cipher.blockEncipher(data, 0, data.length);

-            digestedRoutingKey = getDigestedRoutingKey(plainRoutingKey);
+            getDigestedRoutingKey();
            isEncrypted = true;
        }

@@ -438,6 +470,13 @@
        public boolean isFree() {
            return (flag & ENTRY_FLAG_OCCUPIED) == 0;
        }
+
+        public byte[] getDigestedRoutingKey() {
+            if (digestedRoutingKey != null)
+                return digestedRoutingKey;
+            else
+                return SaltedHashFreenetStore.this.getDigestedRoutingKey(this.plainRoutingKey);
+        }
    }

    /**
@@ -504,6 +543,7 @@
                return null;
        }

+        entry.curOffset = offset;
        return entry;
    }

@@ -516,17 +556,12 @@
     * <li>update the entry with latest store size</li>
     * </ul>
     */
-    private void writeEntry(Entry entry) throws IOException {
+    private void writeEntry(Entry entry, long offset) throws IOException {
        entry.encrypt();

-        long offset = entry.getOffset();
        int split = (int) (offset % FILE_SPLIT);
        long rawOffset = (offset / FILE_SPLIT) * entryTotalLength;

-        if (logMINOR && !isFree(offset)) {
-            Logger.minor(this, "collision, overwritting an entry");
-        }
-
        ByteBuffer bf = entry.toByteBuffer();
        do {
            int status = storeFC[split].write(bf, rawOffset + bf.position());
@@ -554,16 +589,18 @@
    }

    /**
-     * Check if a block is free
+     * Check if a block is free or occupied by a specific routing key
     *
     * @param offset
+     * @param entry
+     * entry, maybe <code>null</code>
     * @throws IOException
     */
-    private boolean isFree(long offset) throws IOException {
+    private boolean isFree(long offset, Entry entry) throws IOException {
        int split = (int) (offset % FILE_SPLIT);
        long rawOffset = (offset / FILE_SPLIT) * entryTotalLength;

-        ByteBuffer bf = ByteBuffer.allocate(0x30 + 0x08);
+        ByteBuffer bf = ByteBuffer.allocate((int) ENTRY_HEADER_LENGTH);

        do {
            int status = storeFC[split].read(bf, rawOffset + bf.position());
@@ -571,7 +608,17 @@
                throw new EOFException();
        } while (bf.hasRemaining());

-        return (bf.getLong(0x30) & ENTRY_FLAG_OCCUPIED) == 0;
+        if ((bf.getLong(0x30) & ENTRY_FLAG_OCCUPIED) == 0) {
+            // free
+            return true;
+        } else if (entry != null) {
+            // check digested key
+            byte[] digestedRoutingKey = new byte[0x20];
+            bf.position(0);
+            bf.get(digestedRoutingKey);
+            return Arrays.equals(digestedRoutingKey, entry.getDigestedRoutingKey());
+        }
+        return false;
    }

    private void flushAndClose() {
@@ -689,7 +736,7 @@
            while (!shutdown) {
                synchronized (cleanerLock) {
                    if (prevStoreSize != 0)
-                        resizeStore();
+                        ; //resizeStore();
                    else
                        estimateStoreSize();

@@ -728,9 +775,11 @@
         */
        private int resizeRound;

-        /**
+        /*-
+         *
+         *
         * Move old entries to new location and resize store
-         */
+         *
        private void resizeStore() {
            ++resizeRound;
            Logger.normal(this, "Starting datastore resize (round " + resizeRound + ")");
@@ -773,7 +822,7 @@

        /**
         * Scan all entries and try to move them
-         */
+         *
        private void moveOldEntry0(boolean queueItem) {
            newEntries = 0;
            oldEntries = 0;
@@ -827,7 +876,7 @@
                        long newOffset = entry.getOffset();

                        if (newOffset == offset) { // lucky!
-                            writeEntry(entry); // write back entry storeSize
+                            lockAndWrite(entry); // write back entry storeSize
                            resolvedEntries++;
                            continue;
                        }
@@ -840,7 +889,7 @@

                            if (newOffsetEntry.isFree()) {
                                // the new offset is freeeeeeee..
-                                writeEntry(entry);
+                                lockAndWrite(entry);
                                freeOffset(offset);
                                resolvedEntries++;
                            } else if (newOffsetEntry.getStoreSize() == storeSize) {
@@ -862,7 +911,7 @@
                                    oldEntries++; // newOffset wasn't counted count it
                                }

-                                writeEntry(entry);
+                                lockAndWrite(entry);
                                freeOffset(offset);
                                resolvedEntries++;
                            }
@@ -896,7 +945,7 @@
         * Put back oldItems with best effort
         *
         * @throws IOException
-         */
+         *
        private void putBackOldItems(FileChannel oldItems) throws IOException {
            while (true) {
                Entry entry = readOldItem(oldItems);
@@ -914,7 +963,7 @@
                    if (isFree(newOffset)) {
                        if (logDEBUG)
                            Logger.debug(this, "Put back old item: " + HexUtil.bytesToHex(entry.digestedRoutingKey));
-                        writeEntry(entry);
+                        lockAndWrite(entry);
                        done = true;
                    } else {
                        if (logDEBUG)
@@ -948,6 +997,7 @@
            bf.flip();
            return new Entry(bf);
        }
+        */

        /**
         * Samples to take on key count estimation
@@ -972,7 +1022,7 @@
            long occupied = 0;
            while (sampled < numSample) {
                try {
-                    if (!isFree(samplePos)) {
+                    if (!isFree(samplePos, null)) {
                        occupied++;
                    }
                    sampled++;
@@ -1173,7 +1223,7 @@
     * @param storeSize
     * @return
     */
-    public long getOffsetFromPlainKey(byte[] plainKey, long storeSize) {
+    public long[] getOffsetFromPlainKey(byte[] plainKey, long storeSize) {
        return getOffsetFromDigestedKey(getDigestedRoutingKey(plainKey), storeSize);
    }

@@ -1184,18 +1234,27 @@
     * @param storeSize
     * @return
     */
-    public long getOffsetFromDigestedKey(byte[] digestedKey, long storeSize) {
-        long keyValue = (((long) (digestedKey[0]) << 0) + //
-         (((long) digestedKey[1]) << 8) + //
-         (((long) digestedKey[3]) << 16) + //
-         (((long) digestedKey[4]) << 24) + //
-         (((long) digestedKey[5]) << 32) + //
-         (((long) digestedKey[6]) << 40) + //
-         (((long) digestedKey[7]) << 48))
-         & Long.MAX_VALUE;
-        return keyValue % storeSize;
+    public long[] getOffsetFromDigestedKey(byte[] digestedKey, long storeSize) {
+        long keyValue = keyToLong(digestedKey);
+        // h + 141 i^2 + 13 i
+        return new long[] {//
+        ((keyValue + 141 * (0 * 0) + 13 * 0) & Long.MAX_VALUE) % storeSize, // i = 0
+         ((keyValue + 141 * (1 * 1) + 13 * 1) & Long.MAX_VALUE) % storeSize, // i = 1
+         ((keyValue + 141 * (2 * 2) + 13 * 2) & Long.MAX_VALUE) % storeSize, // i = 2
+         ((keyValue + 141 * (3 * 3) + 13 * 3) & Long.MAX_VALUE) % storeSize, // i = 3
+        };
    }

+    private long keyToLong(byte[] key) {
+        return (((long) (key[0]) << 0) + //
+         (((long) key[1]) << 8) + //
+         (((long) key[3]) << 16) + //
+         (((long) key[4]) << 24) + //
+         (((long) key[5]) << 32) + //
+         (((long) key[6]) << 40) + //
+        (((long) key[7]) << 48));
+    }
+
    // ------------- Statistics (a.k.a. lies)
    private final Object statLock = new Object();
    private long hits;