added inodecache

darcs-hash:20040505010557-24bed-059d93f0ecd89f484bc2a33759eb7d40e1bbfaad.gz

diff --git a/src/org/ibex/nestedvm/UnixRuntime.java b/src/org/ibex/nestedvm/UnixRuntime.java
index 5eb9178..42541dd 100644 (file)
--- a/src/org/ibex/nestedvm/UnixRuntime.java
+++ b/src/org/ibex/nestedvm/UnixRuntime.java
@@ -730,7 +730,7 @@ public abstract class UnixRuntime extends Runtime implements Cloneable {
     }
     
     public static class HostFS extends FS {
-        InodeCache inodes = new InodeCache(4096);
+        InodeCache inodes = new InodeCache(4000);
         protected File root;
         public File getRoot() { return root; }
         

diff --git a/src/org/ibex/nestedvm/util/InodeCache.java b/src/org/ibex/nestedvm/util/InodeCache.java
new file mode 100644 (file)
index 0000000..99d2a98
--- /dev/null
+++ b/src/org/ibex/nestedvm/util/InodeCache.java
@@ -0,0 +1,203 @@
+package org.ibex.nestedvm.util;
+
+import java.util.Arrays;
+
+// Based on the various org.xwt.util.* classes by Adam Megacz
+
+public class InodeCache {
+    private static final Object PLACEHOLDER = new Object();
+    private static final short SHORT_PLACEHOLDER = -2;
+    private static final short SHORT_NULL = -1;
+    private static final int LOAD_FACTOR = 2;
+    
+    private final int maxSize;
+    private final int totalSlots;
+    private final int maxUsedSlots;
+    
+    private final Object[] keys;
+    private final short[] next;
+    private final short[] prev;
+    private final short[] inodes;
+    private final short[] reverse;
+    
+    private int size, usedSlots;
+    private short mru, lru;
+    
+    public InodeCache() { this(1024); }
+    public InodeCache(int maxSize) {
+        this.maxSize = maxSize;
+        totalSlots = maxSize*LOAD_FACTOR*2 + 3;
+        maxUsedSlots = totalSlots / LOAD_FACTOR;
+        if(totalSlots > Short.MAX_VALUE) throw new IllegalArgumentException("cache size too large");
+        keys = new Object[totalSlots];
+        next = new short[totalSlots];
+        prev = new short[totalSlots];
+        inodes = new short[totalSlots];
+        reverse = new short[totalSlots];
+        clear();
+    }
+    
+    public final void clear() {
+        size = usedSlots = 0;
+        mru = lru = -1;
+        Arrays.fill(keys,null);
+        Arrays.fill(inodes,SHORT_NULL);
+        Arrays.fill(reverse,SHORT_NULL);
+    }
+    
+    public final short get(Object key) {
+        int hc = key.hashCode() & 0x7fffffff;
+        int dest = hc % totalSlots;
+        int odest = dest;
+        int tries = 1;
+        boolean plus = true;
+        Object k;
+        int placeholder = -1;
+        
+        while((k = keys[dest]) != null) {
+            if(k == PLACEHOLDER) {
+                   if(placeholder == -1) placeholder = dest;
+            } else if(k.equals(key)) {
+                short inode = inodes[dest];
+                if(dest == mru) return inode;
+                if(lru == dest) {
+                    lru = next[lru];
+                } else {
+                    short p = prev[dest];
+                    short n = next[dest];
+                    next[p] = n;
+                    prev[n] = p;
+                }
+                prev[dest] = mru;
+                next[mru] = (short) dest;
+                mru = (short) dest;
+                return inode;
+            }
+            dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
+            if(!plus) tries++;
+            plus = !plus;
+        }
+        
+        // not found
+        int slot;
+        if(placeholder == -1) {
+            // new slot
+            slot = dest;
+            if(usedSlots == maxUsedSlots) {
+                clear();
+                return get(key);
+            }
+            usedSlots++;
+        } else {
+            // reuse a placeholder
+            slot = placeholder;
+        }
+        
+        if(size == maxSize) {
+            // cache is full
+            keys[lru] = PLACEHOLDER;
+            inodes[lru] = SHORT_PLACEHOLDER;
+            lru = next[lru];
+        } else {
+            if(size == 0) lru = (short) slot;
+            size++;
+        }
+        
+        int inode;
+        OUTER: for(inode = hc & 0x7fff;;inode++) {
+            dest = inode % totalSlots;
+            odest = dest;
+            tries = 1;
+            plus = true;
+            placeholder = -1;
+            int r;
+            while((r = reverse[dest]) != SHORT_NULL) {
+                int i = inodes[r];
+                if(i == SHORT_PLACEHOLDER) {
+                    if(placeholder == -1) placeholder = dest;
+                } else if(i == inode) {
+                    continue OUTER;
+                }
+                dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
+                if(!plus) tries++;
+                plus = !plus;
+            }
+            // found a free inode
+            if(placeholder != -1) dest = placeholder;
+            break OUTER;
+        }
+        keys[slot] = key;
+        reverse[dest] = (short) slot;
+        inodes[slot] = (short) inode;
+        if(mru != -1) {
+                   prev[slot] = mru;
+                   next[mru] = (short) slot;
+        }
+        mru = (short) slot;
+        return (short) inode;
+    }
+    
+    public Object reverse(short inode) {
+        int dest = inode % totalSlots;
+        int odest = dest;
+        int tries = 1;
+        boolean plus = true;
+        int r;
+        while((r = reverse[dest]) != SHORT_NULL) {
+            if(inodes[r] == inode) return keys[r];
+            dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % totalSlots);
+            if(!plus) tries++;
+            plus = !plus;
+        }        
+        return null;
+    }
+    
+    private void dump() {
+        System.err.println("Size " + size);
+        System.err.println("UsedSlots " + usedSlots);
+        System.err.println("MRU " + mru);
+        System.err.println("LRU " + lru);
+        if(size == 0) return;
+        for(int i=mru;;i=prev[i]) {
+            System.err.println("" + i + ": " + keys[i] + " -> " + inodes[i] + "(prev: " + prev[i] + " next: " + next[i] + ")");
+            if(i == lru) break;
+        }
+    }
+    
+    private void stats() {
+        int freeKeys = 0;
+        int freeReverse = 0;
+        int placeholderKeys = 0;
+        int placeholderReverse = 0;
+        for(int i=0;i<totalSlots;i++) {
+            if(keys[i] == null) freeKeys++;
+            if(keys[i] == PLACEHOLDER) placeholderKeys++;
+            if(reverse[i] == SHORT_NULL) freeReverse++;
+        }
+        System.err.println("Keys: " + freeKeys + "/" + placeholderKeys);
+        System.err.println("Reverse: " + freeReverse);
+    }
+    
+    public static void main(String[] args) throws Exception {
+        InodeCache c = new InodeCache();
+        java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in)); 
+        String s;
+        boolean good = false;
+        try {
+                   while((s = br.readLine()) != null) {
+                if(s.charAt(0) == '#') {
+                    short n = Short.parseShort(s.substring(1));
+                           System.err.println("" + n + " -> " + c.reverse(n));
+                } else {
+                           //System.err.println("Adding " + s);
+                               short n = c.get(s);
+                               System.err.println("Added " + s + " -> " + n);
+                               //c.dump();
+                }
+            }
+            good = true;
+        } finally {
+            if(!good) c.stats();
+        }
+    }
+}