commit 1ad8f400c93d1178d83a91a3a33e107a652e985e
Author: Karsten Loesing <karsten.loesing(a)gmx.net>
Date: Wed Sep 12 18:49:43 2012 -0400
Implement a multi-GeoIP database in Java (#6471).
---
task-6471/.gitignore | 2 +
task-6471/README | 3 +
task-6471/java/.gitignore | 5 +
task-6471/java/build.xml | 42 ++
.../java/src/org/torproject/task6471/Database.java | 70 +++
.../src/org/torproject/task6471/DatabaseImpl.java | 652 ++++++++++++++++++++
.../task6471/DatabasePerformanceExample.java | 146 +++++
.../src/org/torproject/task6471/DatabaseTest.java | 141 +++++
8 files changed, 1061 insertions(+), 0 deletions(-)
diff --git a/task-6471/.gitignore b/task-6471/.gitignore
new file mode 100644
index 0000000..6dbccb1
--- /dev/null
+++ b/task-6471/.gitignore
@@ -0,0 +1,2 @@
+data/
+
diff --git a/task-6471/README b/task-6471/README
new file mode 100644
index 0000000..bb1a572
--- /dev/null
+++ b/task-6471/README
@@ -0,0 +1,3 @@
+Task 6471 -- Designing a file format and Python/Java library for multiple
+ GeoIP or AS databases
+
diff --git a/task-6471/java/.gitignore b/task-6471/java/.gitignore
new file mode 100644
index 0000000..86b7b14
--- /dev/null
+++ b/task-6471/java/.gitignore
@@ -0,0 +1,5 @@
+.classpath
+.project
+lib/
+classes/
+
diff --git a/task-6471/java/build.xml b/task-6471/java/build.xml
new file mode 100644
index 0000000..9eb1223
--- /dev/null
+++ b/task-6471/java/build.xml
@@ -0,0 +1,42 @@
+<project default="test" name="task-6471" basedir=".">
+ <property name="sources" value="src"/>
+ <property name="classes" value="classes"/>
+ <property name="libs" value="lib"/>
+ <path id="classpath">
+ <pathelement path="${classes}"/>
+ <fileset dir="${libs}">
+ <include name="*.jar"/>
+ </fileset>
+ </path>
+ <target name="init">
+ <mkdir dir="${classes}"/>
+ </target>
+ <target name="compile"
+ depends="init">
+ <javac destdir="${classes}"
+ srcdir="${sources}"
+ source="1.5"
+ target="1.5"
+ debug="true"
+ deprecation="true"
+ optimize="false"
+ failonerror="true"
+ includeantruntime="false">
+ <classpath refid="classpath"/>
+ </javac>
+ </target>
+ <target name="test" depends="compile">
+ <junit fork="true"
+ haltonfailure="true"
+ maxmemory="1g"
+ printsummary="off">
+ <classpath refid="classpath"/>
+ <formatter type="plain" usefile="false"/>
+ <batchtest>
+ <fileset dir="${classes}"
+ includes="**/*Test.class"/>
+ </batchtest>
+ </junit>
+ </target>
+</project>
+
diff --git a/task-6471/java/src/org/torproject/task6471/Database.java b/task-6471/java/src/org/torproject/task6471/Database.java
new file mode 100644
index 0000000..447b3c2
--- /dev/null
+++ b/task-6471/java/src/org/torproject/task6471/Database.java
@@ -0,0 +1,70 @@
+/* Copyright 2012 The Tor Project */
+package org.torproject.task6471;
+
+/**
+ * Database storing multiple GeoIP databases and supporting efficient
+ * ip-to-country lookups in the most recent of those databases for any
+ * given date.
+ *
+ * A typical query for this GeoIP database is: "to which country was IPv4
+ * address 1.2.3.4 assigned on date 20120912?" This query is answered by
+ * looking at the entries from the most recent database published on or
+ * before 20120912. If the earliest known database was published after
+ * 20120912, the earliest known database is used to resolve the request.
+ */
+public interface Database {
+
+ /**
+ * Import the contents of one or more IP address assignments files
+ * published by the Regional Internet Registries. The file or files
+ * are expected to conform to the RIR Statistics Exchange Format.
+ * Only IPv4 address ranges are imported, whereas ASN and IPv6 lines are
+ * ignored. Only the country code, start address, and address range
+ * length fields are imported. (TODO Extend to IPv6 and find similar
+ * data source for ASN.)
+ *
+ * A typical entry from a RIR file is:
+ * "ripencc|FR|ipv4|2.0.0.0|1048576|20100712|allocated".
+ *
+ * It is important to note that all five registry files (AfriNIC, APNIC,
+ * ARIN, LACNIC, and RIPE NCC) published on a given day should be
+ * imported, or the missing address ranges will be considered as
+ * unassigned from that day until the next database publication day.
+ * (TODO We could be smarter here by checking that less than five
+ * registry files have been imported for the same day, or something.)
+ *
+ * @param path Path to a stats file or directory.
+ * @return True if importing the file or directory was successful,
+ * false otherwise.
+ */
+ public boolean importRegionalRegistryStatsFileOrDirectory(String path);
+
+ /**
+ * Save the combined databases in a format that can later be loaded much
+ * more efficiently than importing the original RIR files again.
+ *
+ * @param path Path to the combined database file.
+ * @return True if saving the combined database file was successful,
+ * false otherwise.
+ */
+ public boolean saveCombinedDatabases(String path);
+
+ /**
+ * Load a combined databases file.
+ *
+ * @param path Path to the combined database file.
+ * @return True if loading the combined database file was successful,
+ * false otherwise.
+ */
+ public boolean loadCombinedDatabases(String path);
+
+ /**
+ * Query the database for an IPv4 address and assignment date.
+ *
+ * @param address IPv4 address in dotted-quad notation.
+ * @param date Assignment date in format yyyymmdd.
+ * @return Assigned country code, or null if no assignment could be
+ * found.
+ */
+ public String lookupAddress(String address, String date);
+}
diff --git a/task-6471/java/src/org/torproject/task6471/DatabaseImpl.java b/task-6471/java/src/org/torproject/task6471/DatabaseImpl.java
new file mode 100644
index 0000000..43e5a95
--- /dev/null
+++ b/task-6471/java/src/org/torproject/task6471/DatabaseImpl.java
@@ -0,0 +1,652 @@
+/* Copyright 2012 The Tor Project */
+package org.torproject.task6471;
+
+import java.io.BufferedReader;
+import java.io.BufferedWriter;
+import java.io.File;
+import java.io.FileReader;
+import java.io.FileWriter;
+import java.io.IOException;
+import java.text.ParseException;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.SortedMap;
+import java.util.SortedSet;
+import java.util.Stack;
+import java.util.TimeZone;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+/**
+ * Implementation of database holding multiple GeoIP databases with
+ * special focus on lookup performance, import performance, and memory
+ * consumption (in that order).
+ *
+ * This implementation uses a single tree to store IP address and date
+ * ranges. Each tree element is stored under a long integer consisting of
+ * the start IPv4 address in the higher bits and the first database
+ * publication date containing that range in the lower bits. The tree
+ * element itself contains the end IPv4 address, last database publication
+ * date, last database index number (see explanation further below), and
+ * country code.
+ *
+ * Lookups for a given address and random date only require iterating
+ * backwards over ranges with start address smaller than or equaling the
+ * requested address and can terminate as soon as a range with a smaller
+ * end address is encountered.
+ *
+ * As a requirement for lookups to work correctly, address ranges may
+ * never overlap for different assignment periods. Similarly, date
+ * assignment ranges for a given address range may not overlap. These
+ * requirements make the import process somewhat more complex and
+ * time-consuming, which is a tradeoff for faster lookup performance.
+ *
+ * The purpose of storing the last database index number is to fix ranges
+ * that are contained in two or more databases, but that are missing in a
+ * database that was published between the others but imported after them.
+ * The database index number defines that the range is only valid for
+ * databases imported until a given database, not necessarily for
+ * databases importer later on. A separate repair run is necessary to
+ * check whether later imported databases require splitting a range into
+ * two or more sub ranges to correctly reflect that the range was not
+ * contained in those databases.
+ */
+public class DatabaseImpl implements Database {
+
+ /**
+ * Tree element containing an end IPv4 address, last database date,
+ * last database index, and country code. Start IPv4 address and first
+ * database date are encoded in the key under which the element is
+ * stored.
+ */
+ private static class TreeElement {
+ private long endAddress;
+ private int lastDbDate;
+ private int lastKnownDbIndex;
+ private String countryCode;
+ TreeElement(long endAddress, int lastDbDate, int lastKnownDbIndex,
+ String countryCode) {
+ this.endAddress = endAddress;
+ this.lastDbDate = lastDbDate;
+ this.lastKnownDbIndex = lastKnownDbIndex;
+ this.countryCode = countryCode;
+ }
+ }
+
+ /**
+ * IPv4 address and date ranges, ordered backwards by start address and
+ * first database date.
+ */
+ private SortedMap<Long, TreeElement> ranges =
+ new TreeMap<Long, TreeElement>(Collections.reverseOrder());
+
+ /**
+ * Return number of contained ranges.
+ */
+ int getNumberOfElements() {
+ return this.ranges.size();
+ }
+
+ /**
+ * Database dates ordered from oldest to youngest.
+ */
+ private SortedSet<Integer> databaseDates = new TreeSet<Integer>();
+
+ /**
+ * Ordered list of database dates to find out their indexes.
+ */
+ private List<Integer> databaseIndexes = new ArrayList<Integer>();
+
+ /**
+ * Parse one or more stats files.
+ */
+ public boolean importRegionalRegistryStatsFileOrDirectory(String path) {
+ boolean allImportsSuccessful = true;
+ Stack<File> files = new Stack<File>();
+ files.add(new File(path));
+ while (!files.isEmpty()) {
+ File file = files.pop();
+ if (file.isDirectory()) {
+ files.addAll(Arrays.asList(file.listFiles()));
+ } else if (file.getName().endsWith(".md5") ||
+ file.getName().endsWith(".md5.gz") ||
+ file.getName().endsWith(".asc") ||
+ file.getName().endsWith(".asc.gz")) {
+ System.err.println("Signature and digest files are not supported "
+ + "yet: '" + file.getAbsolutePath() + "'. Skipping.");
+ /* TODO Implement checking signatures/digests. */
+ } else if (file.getName().endsWith(".gz") ||
+ file.getName().endsWith(".bz2")) {
+ System.err.println("Parsing compressed files is not supported "
+ + "yet: '" + file.getAbsolutePath() + "'. Skipping.");
+ /* TODO Implement parsing compressed files. */
+ } else if (!this.importRegionalRegistryStatsFile(file)) {
+ allImportsSuccessful = false;
+ }
+ }
+ return allImportsSuccessful;
+ }
+
+ /**
+ * Simple and not very robust implementation of an RIR stats file
+ * parser.
+ */
+ private boolean importRegionalRegistryStatsFile(File file) {
+ try {
+ BufferedReader br = new BufferedReader(new FileReader(file));
+ String line;
+ String databaseDateString =
+ file.getName().substring(file.getName().length() - 8);
+ while ((line = br.readLine()) != null) {
+ if (line.startsWith("#") || line.length() == 0) {
+ /* Skip comment line. */
+ continue;
+ }
+ String[] parts = line.split("\\|");
+ if (parts[0].equals("2")) {
+ continue;
+ }
+ if (parts[1].equals("*")) {
+ /* Skip summary line. */
+ continue;
+ }
+ String type = parts[2];
+ if (type.equals("asn")) {
+ continue;
+ } else if (type.equals("ipv6")) {
+ continue;
+ }
+ String countryCode = parts[1].toLowerCase();
+ String startAddressString = parts[3];
+ long addresses = Long.parseLong(parts[4]);
+ this.addRange(databaseDateString, countryCode, startAddressString,
+ addresses);
+ }
+ br.close();
+ this.repairIndex();
+ } catch (IOException e) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Internal counters for import statistics.
+ */
+ private int rangeImports = 0, rangeImportsKeyLookups = 0;
+
+ /**
+ * Add a single address and date range to the database, which may
+ * require splitting up existing ranges.
+ *
+ * This method has default visibility and is not specified in the
+ * interface, because the caller needs to make sure that repairIndex()
+ * is called prior to any lookupAddress() calls. No further checks are
+ * performed that the tree is repaired before look up an address.
+ */
+ void addRange(String databaseDateString, String countryCode,
+ String startAddressString, long addresses) {
+
+ this.rangeImports++;
+ int databaseDate = convertDateStringToNumber(databaseDateString);
+ long startAddress = convertAddressStringToNumber(startAddressString);
+ long endAddress = startAddress + addresses - 1L;
+
+ /* Add new database date if it's not yet contained. */
+ if (!this.databaseDates.contains(databaseDate)) {
+ this.databaseDates.add(databaseDate);
+ this.databaseIndexes.add(databaseDate);
+ if (this.databaseIndexes.size() > 1) {
+ this.needToFixDatabase = true;
+ }
+ }
+
+ /* We might have to split existing ranges or the new range before
+ * adding it to the database, and we might have to remove existing
+ * ranges. We shouldn't mess with the tree directly while iterating
+ * over it, so let's for now only calculate what changes we want to
+ * make. */
+ SortedMap<Long, TreeElement> updateElements =
+ this.getUpdatesForAddingRange(databaseDate, countryCode,
+ startAddress, endAddress);
+
+ /* Apply updates. Elements with non-null values are added, elements
+ * with null values are removed. */
+ for (Map.Entry<Long, TreeElement> e : updateElements.entrySet()) {
+ if (e.getValue() == null) {
+ this.ranges.remove(e.getKey());
+ } else {
+ this.ranges.put(e.getKey(), e.getValue());
+ }
+ }
+ }
+
+ /**
+ * Calculate necessary changes to the tree to add a range.
+ */
+ private SortedMap<Long, TreeElement> getUpdatesForAddingRange(
+ int databaseDate, String countryCode, long startAddress,
+ long endAddress) {
+
+ /* Keep updates in a single tree where non-null values will later be
+ * added, possibly replacing existing elements, and null values will
+ * be removed from the tree. */
+ SortedMap<Long, TreeElement> updateElements =
+ new TreeMap<Long, TreeElement>();
+
+ /* Find out previous and next database, so that we can possibly merge
+ * ranges. */
+ int previousDatabaseDate =
+ this.databaseDates.headSet(databaseDate).isEmpty() ? -1 :
+ this.databaseDates.headSet(databaseDate).last();
+ int nextDatabaseDate =
+ this.databaseDates.tailSet(databaseDate + 1).isEmpty() ? -1 :
+ this.databaseDates.tailSet(databaseDate + 1).first();
+
+ /* Look up database index number of the range to be added. */
+ int dbIndex = this.databaseIndexes.indexOf(databaseDate);
+
+ /* Remember the address boundaries of the next (partial) range to be
+ * added. */
+ long nextStartAddress = startAddress, nextEndAddress = endAddress;
+ int nextFirstDbDate = databaseDate, nextLastDbDate = databaseDate;
+
+ /* Iterate backwards over the existing ranges, starting at the end
+ * address of the range to be added and at the last conceivable
+ * database publication date. */
+ for (Map.Entry<Long, TreeElement> e :
+ this.ranges.tailMap(((endAddress + 1L) << 16) - 1L).entrySet()) {
+ this.rangeImportsKeyLookups++;
+
+ /* Extract everything we need to know from the next existing range
+ * we're looking at. */
+ long eStartAddress = e.getKey() >> 16;
+ long eEndAddress = e.getValue().endAddress;
+ int eFirstDbDate = (int) (e.getKey() & ((1L << 16) - 1L));
+ int eLastDbDate = e.getValue().lastDbDate;
+ int eLastKnownDbIndex = e.getValue().lastKnownDbIndex;
+ String eCountryCode = e.getValue().countryCode;
+
+ /* If the next (partial) range starts after the current element
+ * ends, add the new range. */
+ if (nextStartAddress > eEndAddress &&
+ nextEndAddress >= startAddress) {
+ updateElements.put((nextStartAddress << 16) + nextFirstDbDate,
+ new TreeElement(nextEndAddress, nextLastDbDate, dbIndex,
+ countryCode));
+ nextEndAddress = nextStartAddress - 1L;
+ nextStartAddress = startAddress;
+ nextFirstDbDate = databaseDate;
+ nextLastDbDate = databaseDate;
+ }
+
+ /* If the next (partial) range still ends after the current element
+ * ends, add the new range. */
+ if (nextEndAddress > eEndAddress &&
+ nextEndAddress >= startAddress) {
+ updateElements.put(((eEndAddress + 1L) << 16) + databaseDate,
+ new TreeElement(nextEndAddress, databaseDate, dbIndex,
+ countryCode));
+ nextEndAddress = eEndAddress;
+ nextStartAddress = startAddress;
+ nextFirstDbDate = databaseDate;
+ nextLastDbDate = databaseDate;
+ }
+
+ /* If the existing range ends before the new range starts, we don't
+ * have to look at any more existing ranges. */
+ if (eEndAddress < startAddress) {
+ break;
+ }
+
+ /* Cut off any address range parts of the existing element that are
+ * not contained in the currently added range. First check whether
+ * the existing range ends after the newly added range. In that
+ * case cut off the overlapping part and store it as a new
+ * element.*/
+ if (eStartAddress <= endAddress && eEndAddress > endAddress) {
+ updateElements.put(((endAddress + 1L) << 16) + eFirstDbDate,
+ new TreeElement(eEndAddress, eLastDbDate, eLastKnownDbIndex,
+ eCountryCode));
+ updateElements.put((eStartAddress << 16) + eFirstDbDate,
+ new TreeElement(endAddress, eLastDbDate, eLastKnownDbIndex,
+ eCountryCode));
+ eEndAddress = endAddress;
+ }
+
+ /* Similarly, check whether the existing range starts before the
+ * newly added one. If so, cut off the overlapping part and store
+ * it as new element. */
+ if (eStartAddress < startAddress && eEndAddress >= startAddress) {
+ updateElements.put((eStartAddress << 16) + eFirstDbDate,
+ new TreeElement(startAddress - 1L, eLastDbDate,
+ eLastKnownDbIndex, eCountryCode));
+ updateElements.put((startAddress << 16) + eFirstDbDate,
+ new TreeElement(eEndAddress, eLastDbDate, eLastKnownDbIndex,
+ eCountryCode));
+ eStartAddress = startAddress;
+ }
+
+ /* Now we're sure the existing element doesn't exceed the newly
+ * added element, address-wise. */
+ nextStartAddress = eStartAddress;
+ nextEndAddress = eEndAddress;
+
+ /* If the range is already contained, maybe even with different
+ * country code, ignore it. */
+ if (eFirstDbDate <= databaseDate && eLastDbDate >= databaseDate) {
+ updateElements.clear();
+ return updateElements;
+ }
+
+ /* See if we can merge the new range with the previous or next
+ * range. If so, extend our database range and mark the existing
+ * element for deletion. */
+ if (eCountryCode.equals(countryCode)) {
+ if (eLastDbDate == previousDatabaseDate) {
+ nextFirstDbDate = eFirstDbDate;
+ updateElements.put((eStartAddress << 16) + eFirstDbDate, null);
+ } else if (eFirstDbDate == nextDatabaseDate) {
+ nextLastDbDate = eLastDbDate;
+ updateElements.put((eStartAddress << 16) + eFirstDbDate, null);
+ }
+ }
+ }
+
+ /* If there's still some part (or the whole?) address range left to
+ * add, add it now. */
+ while (nextEndAddress >= startAddress) {
+ updateElements.put((nextStartAddress << 16) + nextFirstDbDate,
+ new TreeElement(nextEndAddress, nextLastDbDate, dbIndex,
+ countryCode));
+ nextEndAddress = nextStartAddress - 1L;
+ nextStartAddress = startAddress;
+ nextFirstDbDate = databaseDate;
+ nextLastDbDate = databaseDate;
+ }
+
+ /* Return the tree updates that will add the given range. */
+ return updateElements;
+ }
+
+ /* Do we have to repair the tree? */
+ private boolean needToFixDatabase = false;
+
+ /**
+ * Repair tree by making sure that any range from a given database date
+ * to another is still valid when considering any other database that
+ * was imported later.
+ */
+ void repairIndex() {
+ if (!needToFixDatabase) {
+ return;
+ }
+ int maxDatabaseIndex = databaseIndexes.size() - 1;
+ if (maxDatabaseIndex < 1) {
+ return;
+ }
+ SortedMap<Long, TreeElement> updateElements =
+ new TreeMap<Long, TreeElement>();
+ for (Map.Entry<Long, TreeElement> e : this.ranges.entrySet()) {
+ if (e.getValue().lastKnownDbIndex < maxDatabaseIndex) {
+ int eFirstDbDate = (int) (e.getKey() & ((1L << 16) - 1L));
+ int eLastDbDate = e.getValue().lastDbDate;
+ List<Integer> splitAtDates = new ArrayList<Integer>();
+ for (int dbIndex = e.getValue().lastKnownDbIndex + 1;
+ dbIndex <= maxDatabaseIndex; dbIndex++) {
+ int dbDate = databaseIndexes.get(dbIndex);
+ if (eFirstDbDate < dbDate && eLastDbDate > dbDate) {
+ splitAtDates.add(dbDate);
+ }
+ }
+ if (splitAtDates.isEmpty()) {
+ e.getValue().lastKnownDbIndex = maxDatabaseIndex;
+ } else {
+ long eStartAddress = e.getKey() >> 16;
+ long eEndAddress = e.getValue().endAddress;
+ String eCountryCode = e.getValue().countryCode;
+ int start = eFirstDbDate, end = eFirstDbDate;
+ for (int cur : this.databaseDates.tailSet(eFirstDbDate)) {
+ if (cur > eLastDbDate) {
+ break;
+ }
+ if (splitAtDates.contains(cur)) {
+ if (start >= 0 && end >= 0) {
+ updateElements.put((eStartAddress << 16) + start,
+ new TreeElement(eEndAddress, end,
+ maxDatabaseIndex, eCountryCode));
+ start = end = -1;
+ }
+ } else if (start < 0) {
+ start = end = cur;
+ } else {
+ end = cur;
+ }
+ }
+ if (start >= 0 && end >= 0) {
+ updateElements.put((eStartAddress << 16) + start,
+ new TreeElement(eEndAddress, end,
+ maxDatabaseIndex, eCountryCode));
+ }
+ }
+ }
+ }
+ for (Map.Entry<Long, TreeElement> e : updateElements.entrySet()) {
+ this.ranges.put(e.getKey(), e.getValue());
+ }
+ this.needToFixDatabase = false;
+ }
+
+ /**
+ * Internal counters for lookup statistics.
+ */
+ private int addressLookups = 0, addressLookupsKeyLookups = 0;
+
+ /**
+ * Look up address and date by iterating backwards over possibly
+ * matching ranges.
+ */
+ public String lookupAddress(String addressString, String dateString) {
+ this.addressLookups++;
+
+ long address = convertAddressStringToNumber(addressString);
+ int date = convertDateStringToNumber(dateString);
+
+ if (this.databaseDates.isEmpty()) {
+ return null;
+ }
+
+ /* Look up which database we want. */
+ int databaseDate = this.databaseDates.headSet(date + 1).isEmpty() ?
+ this.databaseDates.first() :
+ this.databaseDates.headSet(date + 1).last();
+
+ /* Iterate backwards over the existing ranges, starting at the last
+ * possible date of the address to be found. */
+ for (Map.Entry<Long, TreeElement> e :
+ this.ranges.tailMap(((address + 1L) << 16) - 1L).entrySet()) {
+ this.addressLookupsKeyLookups++;
+
+ /* If either the end address or end date of the range we're looking
+ * at is smaller than the values we're looking for, we can be sure
+ * not to find it anymore. */
+ if (e.getValue().endAddress < address ||
+ e.getValue().lastDbDate < databaseDate) {
+ return null;
+ }
+
+ /* If the range starts at a later date, skip it and look at the next
+ * one. */
+ long startDate = e.getKey() & ((1L << 16) - 1L);
+ if (startDate > databaseDate) {
+ continue;
+ }
+
+ /* Both address and date ranges match, so return the assigned
+ * country code. */
+ return e.getValue().countryCode;
+ }
+
+ /* No ranges (left) to look at. We don't have what we were looking
+ * for. */
+ return null;
+ }
+
+ /* Helper: convert a dotted-quad formatted address string to its
+ * corresponding long integer number. */
+ static long convertAddressStringToNumber(String addressString) {
+ long address = 0;
+ String[] addressParts = addressString.split("\\.");
+ for (int i = 0; i < 4; i++) {
+ address += Long.parseLong(addressParts[i]) << ((3 - i) * 8);
+ }
+ return address;
+ }
+
+ /* Helper: convert a long integer address number to its corresponding
+ * dotted-quad formatted string. */
+ static String convertAddressNumberToString(long address) {
+ return "" + (address / 256 / 256 / 256) + "."
+ + ((address / 256 / 256) % 256) + "."
+ + ((address / 256) % 256) + "." + (address % 256);
+ }
+
+ /* Helper: date format parser/formatter. */
+ private static SimpleDateFormat dateFormat;
+ static {
+ dateFormat = new SimpleDateFormat("yyyyMMdd");
+ dateFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
+ }
+
+ /* Helper: convert date string in format yyyymmdd to integer containing
+ * days passed since 1970-01-01. */
+ static int convertDateStringToNumber(String dateString)
+ throws IllegalArgumentException {
+ try {
+ SimpleDateFormat dateFormat = new SimpleDateFormat("yyyyMMdd");
+ dateFormat.setTimeZone(TimeZone.getTimeZone("UTC"));
+ return (int) (dateFormat.parse(dateString).getTime() / 86400000);
+ } catch (ParseException e) {
+ throw new IllegalArgumentException(e);
+ }
+ }
+
+ /* Helper: convert integer containing days passed since 1970-01-01 to
+ * date string in format yyyymmdd. */
+ static String convertDateNumberToString(int date) {
+ return dateFormat.format(((long) date) * 86400000);
+ }
+
+ /* Return a nicely formatted string summarizing database contents and
+ * usage statistics. */
+ public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append(String.format("Database contains %d databases and %d "
+ + "combined address ranges.\n"
+ + "Performed %d address range imports requiring %d lookups.\n"
+ + "Performed %d address lookups requiring %d lookups.\n"
+ + "First 10 entries, in reverse order, are:",
+ this.databaseDates.size(), this.ranges.size(), rangeImports,
+ rangeImportsKeyLookups, addressLookups,
+ addressLookupsKeyLookups));
+ int entries = 10;
+ for (Map.Entry<Long, TreeElement> e : this.ranges.entrySet()) {
+ sb.append(String.format("%n %s %s %s %s %s %d",
+ convertAddressNumberToString(e.getKey() >> 16),
+ convertAddressNumberToString(e.getValue().endAddress),
+ e.getValue().countryCode,
+ convertDateNumberToString(
+ (int) (e.getKey() & ((1L << 16) - 1L))),
+ convertDateNumberToString(e.getValue().lastDbDate),
+ e.getValue().lastKnownDbIndex));
+ if (--entries <= 0) {
+ break;
+ }
+ }
+ return sb.toString();
+ }
+
+ /**
+ * Save the combined databases to disk.
+ */
+ public boolean saveCombinedDatabases(String path) {
+ try {
+
+ /* Create parent directories if necessary. */
+ File file = new File(path);
+ if (file.getParentFile() != null) {
+ file.getParentFile().mkdirs();
+ }
+
+ /* Start with writing all contained database dates to the file
+ * header. */
+ BufferedWriter bw = new BufferedWriter(new FileWriter(file));
+ for (int dbDate : this.databaseDates) {
+ bw.write("!" + convertDateNumberToString(dbDate) + "\n");
+ }
+
+ /* Next write all database ranges in the same order as they are
+ * currently contained in memory. The only information we can drop
+ * is the last known database index of each range, because we assume
+ * the tree is already in repaired state. */
+ for (Map.Entry<Long, TreeElement> e : this.ranges.entrySet()) {
+ bw.write(String.format("%s,%s,%s,%s,%s%n",
+ convertAddressNumberToString(e.getKey() >> 16),
+ convertAddressNumberToString(e.getValue().endAddress),
+ e.getValue().countryCode,
+ convertDateNumberToString(
+ (int) (e.getKey() & ((1L << 16) - 1L))),
+ convertDateNumberToString(e.getValue().lastDbDate)));
+ }
+ bw.close();
+ } catch (IOException e) {
+ return false;
+ }
+ return true;
+ }
+
+ /**
+ * Load previously saved combined databases from disk. This code is not
+ * at all robust against external changes of the combined database file.
+ */
+ public boolean loadCombinedDatabases(String path) {
+ try {
+ File file = new File(path);
+ BufferedReader br = new BufferedReader(new FileReader(file));
+ String line;
+ int maxDbIndex = -1;
+ while ((line = br.readLine()) != null) {
+ if (line.startsWith("!")) {
+
+ /* First read file header containing database dates. */
+ int dbDate = convertDateStringToNumber(line.substring(1));
+ this.databaseDates.add(dbDate);
+ this.databaseIndexes.add(dbDate);
+ maxDbIndex = this.databaseIndexes.size() - 1;
+ } else {
+
+ /* Next read all ranges. Set last known database index for each
+ * range to the last database we read from the header, because
+ * the tree will immediately be in repaired state. */
+ String[] parts = line.split(",");
+ long startAddress = convertAddressStringToNumber(parts[0]);
+ long endAddress = convertAddressStringToNumber(parts[1]);
+ String countryCode = parts[2];
+ int firstDbDate = convertDateStringToNumber(parts[3]);
+ int lastDbDate = convertDateStringToNumber(parts[4]);
+ this.ranges.put((startAddress << 16) + firstDbDate,
+ new TreeElement(endAddress, lastDbDate, maxDbIndex,
+ countryCode));
+ }
+ }
+ br.close();
+ } catch (IOException e) {
+ return false;
+ }
+ return true;
+ }
+}
diff --git a/task-6471/java/src/org/torproject/task6471/DatabasePerformanceExample.java b/task-6471/java/src/org/torproject/task6471/DatabasePerformanceExample.java
new file mode 100644
index 0000000..3b273bc
--- /dev/null
+++ b/task-6471/java/src/org/torproject/task6471/DatabasePerformanceExample.java
@@ -0,0 +1,146 @@
+package org.torproject.task6471;
+
+import java.io.File;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Random;
+import java.util.SortedMap;
+import java.util.SortedSet;
+import java.util.Stack;
+import java.util.TreeMap;
+import java.util.TreeSet;
+
+public class DatabasePerformanceExample {
+ public static void main(String[] args) {
+
+ System.out.print("Generating test cases... ");
+ long startMillis = System.currentTimeMillis();
+ List<Long> tests = new ArrayList<Long>();
+ SortedMap<Long, String> results = new TreeMap<Long, String>();
+ Random rnd = new Random(1L);
+ int startDate = DatabaseImpl.convertDateStringToNumber("20071001");
+ int endDate = DatabaseImpl.convertDateStringToNumber("20120930");
+ /* Skipping Dec 1--3, 2009, because the first available database from
+ * December 2009 was published on the 4th, and generating test cases
+ * was just too confusing when taking that into account. */
+ List<Integer> skipDates = new ArrayList<Integer>();
+ skipDates.add(DatabaseImpl.convertDateStringToNumber("20091201"));
+ skipDates.add(DatabaseImpl.convertDateStringToNumber("20091202"));
+ skipDates.add(DatabaseImpl.convertDateStringToNumber("20091203"));
+ for (int i = 0; i < 100000; i++) {
+ long testAddress = rnd.nextLong() & ((1L << 32) - 1L);
+ int testDate = startDate + rnd.nextInt(endDate - startDate);
+ if (skipDates.contains(testDate)) {
+ i--;
+ } else {
+ tests.add((testAddress << 16) + testDate);
+ }
+ }
+ Stack<File> stackedFiles = new Stack<File>();
+ stackedFiles.add(new File("../data"));
+ SortedSet<File> files = new TreeSet<File>();
+ while (!stackedFiles.isEmpty()) {
+ File file = stackedFiles.pop();
+ if (file.isDirectory()) {
+ stackedFiles.addAll(Arrays.asList(file.listFiles()));
+ } else if (!file.getName().endsWith(".md5") &&
+ !file.getName().endsWith(".md5.gz") &&
+ !file.getName().endsWith(".asc") &&
+ !file.getName().endsWith(".asc.gz")) {
+ files.add(file);
+ }
+ }
+ for (File file : files) {
+ String dbMonth = file.getName().substring(
+ file.getName().length() - 8);
+ dbMonth = dbMonth.substring(0, 6);
+ Database temp = new DatabaseImpl();
+ temp.importRegionalRegistryStatsFileOrDirectory(
+ file.getAbsolutePath());
+ for (long test : tests) {
+ int testDate = (int) (test & ((1 << 16) - 1));
+ String testMonth = DatabaseImpl.convertDateNumberToString(
+ testDate).substring(0, 6);
+ if (testMonth.equals(dbMonth)) {
+ String testAddressString = DatabaseImpl.
+ convertAddressNumberToString(test >> 16);
+ String testDateString = DatabaseImpl.convertDateNumberToString(
+ testDate);
+ String countryCode = temp.lookupAddress(testAddressString,
+ testDateString);
+ if (countryCode != null) {
+ results.put(test, countryCode);
+ }
+ }
+ }
+ }
+ long endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis.");
+
+ System.out.print("Importing files... ");
+ startMillis = endMillis;
+ Database database = new DatabaseImpl();
+ database.importRegionalRegistryStatsFileOrDirectory("../data");
+ endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis.");
+
+ System.out.print("Making test requests... ");
+ startMillis = endMillis;
+ int failures = 0;
+ for (long test : tests) {
+ String testAddress = DatabaseImpl.convertAddressNumberToString(
+ test >> 16);
+ String testDate = DatabaseImpl.convertDateNumberToString(
+ (int) (test & ((1 << 16) - 1)));
+ String expected = results.get(test);
+ String result = database.lookupAddress(testAddress, testDate);
+ if ((expected == null && result != null) ||
+ (expected != null && !expected.equals(result))) {
+ //System.out.println("Expected " + expected + " for "
+ // + testAddress + " " + testDate + ", but got " + result);
+ failures++;
+ }
+ }
+ endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis, " + failures
+ + " out of " + tests.size() + " tests failed.");
+
+ System.out.println(database);
+
+ System.out.print("Saving combined databases to disk... ");
+ startMillis = endMillis;
+ database.saveCombinedDatabases("geoip-2007-10-2012-09.csv");
+ endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis.");
+ startMillis = endMillis;
+
+ System.out.print("Loading combined databases from disk... ");
+ startMillis = endMillis;
+ database = new DatabaseImpl();
+ database.loadCombinedDatabases("geoip-2007-10-2012-09.csv");
+ endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis.");
+
+ System.out.print("Making a second round of test requests... ");
+ startMillis = endMillis;
+ failures = 0;
+ for (long test : tests) {
+ String testAddress = DatabaseImpl.convertAddressNumberToString(
+ test >> 16);
+ String testDate = DatabaseImpl.convertDateNumberToString(
+ (int) (test & ((1 << 16) - 1)));
+ String expected = results.get(test);
+ String result = database.lookupAddress(testAddress, testDate);
+ if ((expected == null && result != null) ||
+ (expected != null && !expected.equals(result))) {
+ //System.out.println("Expected " + expected + " for "
+ // + testAddress + " " + testDate + ", but got " + result);
+ failures++;
+ }
+ }
+ endMillis = System.currentTimeMillis();
+ System.out.println((endMillis - startMillis) + " millis, " + failures
+ + " out of " + tests.size() + " tests failed.");
+ }
+}
diff --git a/task-6471/java/src/org/torproject/task6471/DatabaseTest.java b/task-6471/java/src/org/torproject/task6471/DatabaseTest.java
new file mode 100644
index 0000000..8f90b3d
--- /dev/null
+++ b/task-6471/java/src/org/torproject/task6471/DatabaseTest.java
@@ -0,0 +1,141 @@
+/* Copyright 2012 The Tor Project */
+package org.torproject.task6471;
+
+import static org.junit.Assert.assertEquals;
+import org.junit.Test;
+
+/**
+ * Test the multi-GeoIP database implementation.
+ */
+public class DatabaseTest {
+
+ @Test()
+ public void testSingleIpRangeSingleDatebase() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(1, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals(null, database.lookupAddress("2.255.255.255",
+ "19920901"));
+ assertEquals(null, database.lookupAddress("2.255.255.255",
+ "20020901"));
+ assertEquals(null, database.lookupAddress("2.255.255.255",
+ "20120901"));
+ assertEquals(null, database.lookupAddress("2.255.255.255",
+ "20220901"));
+ assertEquals("us", database.lookupAddress("3.0.0.0", "19920901"));
+ assertEquals("us", database.lookupAddress("3.0.0.0", "20020901"));
+ assertEquals("us", database.lookupAddress("3.0.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.0.0.0", "20220901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "19920901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20020901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20220901"));
+ assertEquals("us", database.lookupAddress("3.255.255.255",
+ "19920901"));
+ assertEquals("us", database.lookupAddress("3.255.255.255",
+ "20020901"));
+ assertEquals("us", database.lookupAddress("3.255.255.255",
+ "20120901"));
+ assertEquals("us", database.lookupAddress("3.255.255.255",
+ "20220901"));
+ assertEquals(null, database.lookupAddress("4.0.0.0", "19920901"));
+ assertEquals(null, database.lookupAddress("4.0.0.0", "20020901"));
+ assertEquals(null, database.lookupAddress("4.0.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("4.0.0.0", "20220901"));
+ }
+
+ @Test()
+ public void testTwoAdjacentIpRangesSingleDatabase() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20120901", "ca", "4.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(2, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals(null, database.lookupAddress("2.255.255.255",
+ "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("ca", database.lookupAddress("4.127.0.0", "20120901"));
+ assertEquals("ca", database.lookupAddress("4.127.0.0", "20120901"));
+ assertEquals("ca", database.lookupAddress("4.127.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("5.0.0.0", "20120901"));
+ }
+
+ @Test()
+ public void testTwoNonAdjacentIpDateRangesSingleDatabase() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20120901", "ca", "6.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(2, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals(null, database.lookupAddress("2.255.255.255", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("4.255.255.255", "20120901"));
+ assertEquals("ca", database.lookupAddress("6.127.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("7.0.0.0", "20120901"));
+ }
+
+ @Test()
+ public void testDuplicateImport() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(1, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals(null, database.lookupAddress("2.255.255.255", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("4.0.0.0", "20120901"));
+ }
+
+ @Test()
+ public void testDuplicateImportDifferentCountryCode() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20120901", "ca", "3.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(1, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ }
+
+ @Test()
+ public void testLeaveIpChangeUnchanged() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20121001", "us", "3.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(1, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120801"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20121001"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20121101"));
+ }
+
+ @Test()
+ public void testLeaveIpChangeUnchangedReverseOrder() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20121001", "us", "3.0.0.0", 16777216);
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(1, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120801"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20121001"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20121101"));
+ }
+
+ @Test()
+ public void testMissingIpRange() {
+ DatabaseImpl database = new DatabaseImpl();
+ database.addRange("20120901", "us", "3.0.0.0", 16777216);
+ database.addRange("20121101", "us", "3.0.0.0", 16777216);
+ database.addRange("20121001", "us", "6.0.0.0", 16777216);
+ database.repairIndex();
+ assertEquals(3, ((DatabaseImpl) database).getNumberOfElements());
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120801"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20120901"));
+ assertEquals(null, database.lookupAddress("3.127.0.0", "20121001"));
+ assertEquals("us", database.lookupAddress("3.127.0.0", "20121101"));
+ }
+}
