This is the mail archive of the
java@gcc.gnu.org
mailing list for the Java project.
gcj-dbtool redux
- From: Andrew Haley <aph at redhat dot com>
- To: java at gcc dot gnu dot org
- Date: Tue, 8 Feb 2005 18:44:35 +0000
- Subject: gcj-dbtool redux
A few improvements:
* A database can be modified inplace in a running system, even when
other gcj processes are using it,
* Databases are created automatically if they don't already exist.
* Databases grow automatically.
* A new command, "-m", which allows databases to be merged.
* Databases are now much more compact.
* A sensible magic number.
Andrew.
2005-02-08 Andrew Haley <aph@redhat.com>
* gnu/gcj/runtime/PersistentByteMap.java (name, values, fc): new
fields.
(PersistentByteMap): Set name
Magic number changed to 0x67636a64 ("gcjd").
(init): Force the map to be prime.
(emptyPersistentByteMap): File name was a string, now a File.
(addBytes): Share srings between entries.
(stringTableSize): New method.
(capacity): Scale by load factor.
(force): New method.
(getFile): New method.
(close): New method.
(putAll): New method.
(ByteWrapper): New class.
* gnu/gcj/tools/gcj_dbtool/Main.java (verbose): New field.
(main): Guess the average string size as 32, not 64.
Copy a database before modifying it, so that we can update a
database in a running system.
If a database isn't big enough, resize it.
"-m": new option: merges databases.
"-a": Create a new detabase if it doesn't exist.
(usage): Correct, add new option.
(addJar): Copy a database before modifying it.
(resizeMap): New method.
Index: gnu/gcj/tools/gcj_dbtool/Main.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/gnu/gcj/tools/gcj_dbtool/Main.java,v
retrieving revision 1.3
diff -c -2 -p -w -r1.3 Main.java
*** gnu/gcj/tools/gcj_dbtool/Main.java 29 Nov 2004 22:26:00 -0000 1.3
--- gnu/gcj/tools/gcj_dbtool/Main.java 8 Feb 2005 17:57:39 -0000
***************
*** 1,3 ****
! /* Copyright (C) 2004 Free Software Foundation
This file is part of libgcj.
--- 1,3 ----
! /* Copyright (C) 2004, 2005 Free Software Foundation
This file is part of libgcj.
*************** package gnu.gcj.tools.gcj_dbtool;
*** 12,22 ****
import gnu.gcj.runtime.PersistentByteMap;
import java.io.*;
import java.util.*;
import java.util.jar.*;
import java.security.MessageDigest;
- import java.math.BigInteger;
public class Main
{
public static void main (String[] s)
{
--- 12,24 ----
import gnu.gcj.runtime.PersistentByteMap;
import java.io.*;
+ import java.nio.channels.*;
import java.util.*;
import java.util.jar.*;
import java.security.MessageDigest;
public class Main
{
+ static private boolean verbose = false;
+
public static void main (String[] s)
{
*************** public class Main
*** 30,34 ****
+ System.getProperty("java.vm.version"));
System.out.println();
! System.out.println("Copyright 2004 Free Software Foundation, Inc.");
System.out.println("This is free software; see the source for copying conditions. There is NO");
System.out.println("warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.");
--- 32,36 ----
+ System.getProperty("java.vm.version"));
System.out.println();
! System.out.println("Copyright 2004, 2005 Free Software Foundation, Inc.");
System.out.println("This is free software; see the source for copying conditions. There is NO");
System.out.println("warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.");
*************** public class Main
*** 43,46 ****
--- 45,49 ----
if (s[0].equals("-n"))
{
+ // Create a new database.
insist (s.length >= 2 && s.length <= 3);
*************** public class Main
*** 49,66 ****
if (s.length == 3)
{
! // The user has explicitly provided a size for the table.
! // We're going to make that size prime. This isn't
! // strictly necessary but it can't hurt.
!
! BigInteger size = new BigInteger(s[2], 10);
! BigInteger two = BigInteger.ONE.add(BigInteger.ONE);
!
! if (size.getLowestSetBit() != 0) // A hard way to say isEven()
! size = size.add(BigInteger.ONE);
!
! while (! size.isProbablePrime(10))
! size = size.add(two);
!
! capacity = size.intValue();
if (capacity <= 2)
--- 52,56 ----
if (s.length == 3)
{
! capacity = Integer.parseInt(s[2]);
if (capacity <= 2)
*************** public class Main
*** 74,78 ****
{
PersistentByteMap b
! = PersistentByteMap.emptyPersistentByteMap (s[1], capacity, capacity*64);
}
catch (Exception e)
--- 64,69 ----
{
PersistentByteMap b
! = PersistentByteMap.emptyPersistentByteMap(new File(s[1]),
! capacity, capacity*32);
}
catch (Exception e)
*************** public class Main
*** 87,102 ****
if (s[0].equals("-a"))
{
try
{
insist (s.length == 4);
File jar = new File(s[2]);
! PersistentByteMap b
! = new PersistentByteMap(new File(s[1]),
! PersistentByteMap.AccessMode.READ_WRITE);
File soFile = new File(s[3]);
if (! soFile.isFile())
throw new IllegalArgumentException(s[3] + " is not a file");
!
! addJar(jar, b, soFile);
}
catch (Exception e)
--- 78,101 ----
if (s[0].equals("-a"))
{
+ // Add a jar file to a database, creating it if necessary.
+ // Copies the database, adds the jar file to the copy, and
+ // then renames the new database over the old.
try
{
insist (s.length == 4);
+ File database = new File(s[1]);
+ database = database.getAbsoluteFile();
File jar = new File(s[2]);
! PersistentByteMap map;
! if (database.isFile())
! map = new PersistentByteMap(database,
! PersistentByteMap.AccessMode.READ_ONLY);
! else
! map = PersistentByteMap.emptyPersistentByteMap(database,
! 100, 100*32);
File soFile = new File(s[3]);
if (! soFile.isFile())
throw new IllegalArgumentException(s[3] + " is not a file");
! map = addJar(jar, map, soFile);
}
catch (Exception e)
*************** public class Main
*** 111,114 ****
--- 110,114 ----
if (s[0].equals("-t"))
{
+ // Test
try
{
*************** public class Main
*** 143,148 ****
--- 143,200 ----
}
+ if (s[0].equals("-m"))
+ {
+ // Merge databases.
+ insist (s.length >= 3);
+ try
+ {
+ File database = new File(s[1]);
+ database = database.getAbsoluteFile();
+ File temp = File.createTempFile(database.getName(), "",
+ database.getParentFile());
+
+ int newSize = 0;
+ int newStringTableSize = 0;
+ PersistentByteMap[] sourceMaps = new PersistentByteMap[s.length - 2];
+ // Scan all the input files, calculating worst case string
+ // table and hash table use.
+ for (int i = 2; i < s.length; i++)
+ {
+ PersistentByteMap b
+ = new PersistentByteMap(new File(s[i]),
+ PersistentByteMap.AccessMode.READ_ONLY);
+ newSize += b.size();
+ newStringTableSize += b.stringTableSize();
+ sourceMaps[i - 2] = b;
+ }
+
+ newSize *= 1.5; // Scaling the new size by 1.5 results in
+ // fewer collisions.
+ PersistentByteMap map
+ = PersistentByteMap.emptyPersistentByteMap
+ (temp, newSize, newStringTableSize);
+
+ for (int i = 0; i < sourceMaps.length; i++)
+ {
+ if (verbose)
+ System.err.println("adding " + sourceMaps[i].size()
+ + " elements from "
+ + sourceMaps[i].getFile());
+ map.putAll(sourceMaps[i]);
+ }
+ map.close();
+ temp.renameTo(database);
+ }
+ catch (Exception e)
+ {
+ e.printStackTrace();
+ System.exit(3);
+ }
+ return;
+ }
+
if (s[0].equals("-l"))
{
+ // List a database.
insist (s.length == 2);
try
*************** public class Main
*** 181,184 ****
--- 233,237 ----
if (s[0].equals("-d"))
{
+ // For testing only: fill the byte map with random data.
insist (s.length == 2);
try
*************** public class Main
*** 220,224 ****
private static void usage(PrintStream out)
{
! out.println
("gcj-dbtool: Manipulate gcj map database files\n"
+ "\n"
--- 273,277 ----
private static void usage(PrintStream out)
{
! System.err.out.println
("gcj-dbtool: Manipulate gcj map database files\n"
+ "\n"
*************** public class Main
*** 226,236 ****
+ " gcj-dbtool -n file.gcjdb [size] - Create a new gcj map database\n"
+ " gcj-dbtool -a file.gcjdb file.jar file.so\n"
! + " - Add the contents of file.jar to the database\n"
+ " gcj-dbtool -t file.gcjdb - Test a gcj map database\n"
! + " gcj-dbtool -l file.gcjdb - List a gcj map database\n");
}
! private static void addJar(File f, PersistentByteMap b, File soFile)
throws Exception
{
--- 279,297 ----
+ " gcj-dbtool -n file.gcjdb [size] - Create a new gcj map database\n"
+ " gcj-dbtool -a file.gcjdb file.jar file.so\n"
! + " - Add the contents of file.jar to a new gcj map database\n"
+ " gcj-dbtool -t file.gcjdb - Test a gcj map database\n"
! + " gcj-dbtool -l file.gcjdb - List a gcj map database\n"
! + " gcj-dbtool -m dest.gcjdb [source.gcjdb]...\n"
! + " - Merge gcj map databases into dest\n"
! + " Replaces dest\n"
! + " To add to dest, include dest in the list of sources");
}
+ // Add a jar to a map. This copies the map first and returns a
+ // different map that contains the data. The original map is
+ // closed.
! private static PersistentByteMap
! addJar(File f, PersistentByteMap b, File soFile)
throws Exception
{
*************** public class Main
*** 238,243 ****
--- 299,325 ----
JarFile jar = new JarFile (f);
+
+ int count = 0;
+ {
+ Enumeration entries = jar.entries();
+ while (entries.hasMoreElements())
+ {
+ JarEntry classfile = (JarEntry)entries.nextElement();
+ if (classfile.getName().endsWith(".class"))
+ count++;
+ }
+ }
+
+ if (verbose)
+ System.err.println("adding " + count + " elements from "
+ + f + " to " + b.getFile());
+
+ // Maybe resize the destination map. We're allowing plenty of
+ // extra space by using a loadFactor of 2.
+ b = resizeMap(b, (b.size() + count) * 2, true);
+
Enumeration entries = jar.entries();
+ byte[] soFileName = soFile.getCanonicalPath().getBytes("UTF-8");
while (entries.hasMoreElements())
{
*************** public class Main
*** 260,269 ****
pos += len;
}
! b.put(md.digest(data),
! soFile.getCanonicalPath().getBytes());
}
}
}
static String bytesToString(byte[] b)
{
--- 342,380 ----
pos += len;
}
! b.put(md.digest(data), soFileName);
! }
! }
! return b;
! }
!
! // Resize a map by creating a new one with the same data and
! // renaming it. If close is true, close the original map.
!
! static PersistentByteMap resizeMap(PersistentByteMap m, int newCapacity, boolean close)
! throws IOException, IllegalAccessException
! {
! newCapacity = Math.max(m.capacity(), newCapacity);
! File name = m.getFile();
! File copy = File.createTempFile(name.getName(), "", name.getParentFile());
! try
! {
! PersistentByteMap dest
! = PersistentByteMap.emptyPersistentByteMap
! (copy, newCapacity, newCapacity*32);
! dest.putAll(m);
! dest.force();
! if (close)
! m.close();
! copy.renameTo(name);
! return dest;
}
+ catch (Exception e)
+ {
+ copy.delete();
}
+ return null;
}
+
static String bytesToString(byte[] b)
{
Index: gnu/gcj/runtime/PersistentByteMap.java
===================================================================
RCS file: /cvs/gcc/gcc/libjava/gnu/gcj/runtime/PersistentByteMap.java,v
retrieving revision 1.3
diff -c -2 -p -w -r1.3 PersistentByteMap.java
*** gnu/gcj/runtime/PersistentByteMap.java 2 Feb 2005 16:19:45 -0000 1.3
--- gnu/gcj/runtime/PersistentByteMap.java 8 Feb 2005 17:57:39 -0000
*************** BUGS/FEATURES:
*** 40,47 ****
remove() isn't written yet.
- we can't change the capacity of a PersistentByteMap.
-
- 0x12345678 is a bad choice for the magic number.
-
capacity is fixed once the map has been created.
--- 40,43 ----
*************** BUGS/FEATURES:
*** 52,60 ****
successful search and 2.5 probes for an unsuccessful one.
! We don't use unique strings. This wastes space.
!
! capacity should probably be prime, but we don't check that.
!
! we don't do any locking at all: adding to a PersistentByteMap
at runtime is possible, but it requires filesystem locks
around get(), put(), and remove().
--- 48,52 ----
successful search and 2.5 probes for an unsuccessful one.
! We don't do any locking at all: adding to a PersistentByteMap
at runtime is possible, but it requires filesystem locks
around get(), put(), and remove().
*************** import java.nio.channels.*;
*** 68,71 ****
--- 60,64 ----
import java.util.*;
import java.security.MessageDigest;
+ import java.math.BigInteger;
public class PersistentByteMap
*************** public class PersistentByteMap
*** 95,98 ****
--- 88,93 ----
private long length; // the length of the underlying file
+ private final File name; // The name of the underlying file
+
static private final int UNUSED_ENTRY = -1;
*************** public class PersistentByteMap
*** 101,104 ****
--- 96,103 ----
static public final int ENTRIES = 2;
+ private HashMap values; // A map of strings in the string table.
+
+ FileChannel fc; // The underlying file channel.
+
static final public class AccessMode
{
*************** public class PersistentByteMap
*** 109,116 ****
--- 108,117 ----
READ_ONLY = new AccessMode(FileChannel.MapMode.READ_ONLY);
READ_WRITE = new AccessMode(FileChannel.MapMode.READ_WRITE);
+ PRIVATE = new AccessMode(FileChannel.MapMode.PRIVATE);
}
public static final AccessMode READ_ONLY;
public static final AccessMode READ_WRITE;
+ public static final AccessMode PRIVATE;
private AccessMode(FileChannel.MapMode mode)
*************** public class PersistentByteMap
*** 120,125 ****
}
! private PersistentByteMap()
{
}
--- 121,127 ----
}
! private PersistentByteMap(File name)
{
+ this.name = name;
}
*************** public class PersistentByteMap
*** 133,137 ****
throws IOException
{
! FileChannel fc;
if (mode == AccessMode.READ_ONLY)
--- 135,139 ----
throws IOException
{
! name = f;
if (mode == AccessMode.READ_ONLY)
*************** public class PersistentByteMap
*** 150,154 ****
int magic = getWord (MAGIC);
! if (magic != 0x12345678)
throw new IllegalArgumentException(f.getName());
--- 152,156 ----
int magic = getWord (MAGIC);
! if (magic != 0x67636a64) /* "gcjd" */
throw new IllegalArgumentException(f.getName());
*************** public class PersistentByteMap
*** 169,173 ****
RandomAccessFile raf = new RandomAccessFile(f, "rw");
! this.capacity = capacity;
table_base = 64;
string_base = table_base + capacity * TABLE_ENTRY_SIZE;
--- 171,194 ----
RandomAccessFile raf = new RandomAccessFile(f, "rw");
! {
! // The user has explicitly provided a size for the table.
! // We're going to make that size prime. This isn't
! // strictly necessary but it can't hurt.
! //
! // We expand the size by 3/2 because the hash table is
! // intolerably slow when more than 2/3 full.
!
! BigInteger size = new BigInteger(Integer.toString(capacity * 3/2));
! BigInteger two = BigInteger.ONE.add(BigInteger.ONE);
!
! if (size.getLowestSetBit() != 0) // A hard way to say isEven()
! size = size.add(BigInteger.ONE);
!
! while (! size.isProbablePrime(10))
! size = size.add(two);
!
! this.capacity = capacity = size.intValue();
! }
!
table_base = 64;
string_base = table_base + capacity * TABLE_ENTRY_SIZE;
*************** public class PersistentByteMap
*** 184,188 ****
raf.write(_4k);
! FileChannel fc = raf.getChannel();
buf = fc.map(FileChannel.MapMode.READ_WRITE, 0, raf.length());
--- 205,209 ----
raf.write(_4k);
! fc = raf.getChannel();
buf = fc.map(FileChannel.MapMode.READ_WRITE, 0, raf.length());
*************** public class PersistentByteMap
*** 190,194 ****
putKeyPos(UNUSED_ENTRY, i);
! putWord(0x12345678, MAGIC);
putWord(0x01, VERSION);
putWord(capacity, CAPACITY);
--- 211,215 ----
putKeyPos(UNUSED_ENTRY, i);
! putWord(0x67636a64, MAGIC);
putWord(0x01, VERSION);
putWord(capacity, CAPACITY);
*************** public class PersistentByteMap
*** 198,210 ****
putWord(elements, ELEMENTS);
buf.force();
}
! static public PersistentByteMap emptyPersistentByteMap(String filename,
! int capacity, int strtabSize)
throws IOException
{
! File f = new File(filename);
! PersistentByteMap m = new PersistentByteMap();
! m.init(m, f, capacity, strtabSize);
return m;
}
--- 219,233 ----
putWord(elements, ELEMENTS);
buf.force();
+
+ length = fc.size();
+ string_size = 0;
}
! static public PersistentByteMap
! emptyPersistentByteMap(File name, int capacity, int strtabSize)
throws IOException
{
! PersistentByteMap m = new PersistentByteMap(name);
! m.init(m, name, capacity, strtabSize);
return m;
}
*************** public class PersistentByteMap
*** 314,320 ****
int hashIndex = hash(digest);
! // With the the table 2/3 full there will be on average 2 probes
! // for a successful search and 5 probes for an unsuccessful one.
! if (elements >= capacity * 2/3)
throw new IllegalAccessException("Table Full: " + elements);
--- 337,341 ----
int hashIndex = hash(digest);
! if (elements >= capacity())
throw new IllegalAccessException("Table Full: " + elements);
*************** public class PersistentByteMap
*** 348,351 ****
--- 369,399 ----
throws IllegalAccessException
{
+ if (data.length > 16)
+ {
+ // Keep track of long strings in the hope that we will be able
+ // to re-use them.
+ if (values == null)
+ {
+ values = new HashMap();
+
+ for (int i = 0; i < capacity; i++)
+ if (getKeyPos(i) != UNUSED_ENTRY)
+ {
+ int pos = getValuePos(i);
+ ByteWrapper bytes = new ByteWrapper(getBytes(pos));
+ values.put(bytes, new Integer(pos));
+ }
+ }
+
+ {
+ Object result = values.get(new ByteWrapper(data));
+ if (result != null)
+ {
+ // We already have this value in the string table
+ return ((Integer)result).intValue();
+ }
+ }
+ }
+
if (data.length + INT_SIZE >= this.length)
throw new IllegalAccessException("String table Full");
*************** public class PersistentByteMap
*** 365,368 ****
--- 413,419 ----
putWord (file_size, FILE_SIZE);
+ if (data.length > 16)
+ values.put(new ByteWrapper(data), new Integer(top - string_base));
+
return top - string_base;
}
*************** public class PersistentByteMap
*** 378,386 ****
}
public int capacity()
{
! return capacity;
}
private final class HashIterator implements Iterator
{
--- 429,494 ----
}
+ public int stringTableSize()
+ {
+ return string_size;
+ }
+
public int capacity()
{
! // With the the table 2/3 full there will be on average 2 probes
! // for a successful search and 5 probes for an unsuccessful one.
! return capacity * 2/3;
! }
!
! public void force()
! {
! buf.force();
! }
!
! public File getFile()
! {
! return name;
! }
!
! // Close the map. Once this has been done, the map can no longer be
! // used.
! public void close()
! {
! force();
! fc.close();
}
+ public void
+ putAll(PersistentByteMap t)
+ throws IllegalAccessException
+ {
+ // We can use a fast copy if the size of a map has not changed.
+ if (this.elements == 0 && t.capacity == this.capacity
+ && t.length == this.length)
+ {
+ this.buf.position(0);
+ t.buf.position(0);
+ this.buf.put(t.buf);
+ this.table_base = t.table_base;
+ this.string_base = t.string_base;
+ this.string_size = t.string_size;
+ this.file_size = t.file_size;
+ this.elements = t.elements;
+ if (t.values != null)
+ this.values = (HashMap)t.values.clone();
+ return;
+ }
+
+ // Otherwise do it the hard way.
+ Iterator iterator = t.iterator(PersistentByteMap.ENTRIES);
+ while (iterator.hasNext())
+ {
+ PersistentByteMap.MapEntry entry
+ = (PersistentByteMap.MapEntry)iterator.next();
+ this.put((byte[])entry.getKey(), (byte[])entry.getValue());
+ }
+ }
+
+
private final class HashIterator implements Iterator
{
*************** public class PersistentByteMap
*** 482,484 ****
--- 590,619 ----
}
}
+
+ // A wrapper class for a byte array that allows collections to be
+ // made.
+ private final class ByteWrapper
+ {
+ final byte[] bytes;
+ final int hash;
+
+ public ByteWrapper (byte[] bytes)
+ {
+ int sum = 0;
+ this.bytes = bytes;
+ for (int i = 0; i < bytes.length; i++)
+ sum += bytes[i];
+ hash = sum;
+ }
+
+ public int hashCode()
+ {
+ return hash;
+ }
+
+ public boolean equals(Object obj)
+ {
+ return Arrays.equals(bytes, ((ByteWrapper)obj).bytes);
+ }
+ }
}