gcj-dbtool redux

Andrew Haley aph@redhat.com
Wed Feb 9 11:57:00 GMT 2005

• Previous message (by thread): Question about the Classpath license
• Next message (by thread): EXPR_WITH_FILE_LOCATION Tree Nodes
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

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);
+ }
+ }
 }

---

• Previous message (by thread): Question about the Classpath license
• Next message (by thread): EXPR_WITH_FILE_LOCATION Tree Nodes
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

---

More information about the Java mailing list