1f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin/* 2f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Copyright (C) 2010 The Android Open Source Project 3f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 4f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Licensed under the Apache License, Version 2.0 (the "License"); 5f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * you may not use this file except in compliance with the License. 6f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * You may obtain a copy of the License at 7f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 8f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * http://www.apache.org/licenses/LICENSE-2.0 9f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * 10f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * Unless required by applicable law or agreed to in writing, software 11f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * distributed under the License is distributed on an "AS IS" BASIS, 12f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * See the License for the specific language governing permissions and 14f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin * limitations under the License. 15f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin */ 16f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 17f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// This is an on-disk cache which maps a 64-bits key to a byte array. 18f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 19f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// It consists of three files: one index file and two data files. One of the 20f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// data files is "active", and the other is "inactive". New entries are 21f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// appended into the active region until it reaches the size limit. At that 22f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// point the active file and the inactive file are swapped, and the new active 23f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// file is truncated to empty (and the index for that file is also cleared). 24f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// The index is a hash table with linear probing. When the load factor reaches 25f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 0.5, it does the same thing like when the size limit is reached. 26f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 27f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// The index file format: (all numbers are stored in little-endian) 28f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [0] Magic number: 0xB3273030 29f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [4] MaxEntries: Max number of hash entries per region. 30f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [8] MaxBytes: Max number of data bytes per region (including header). 31f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [12] ActiveRegion: The active growing region: 0 or 1. 32f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [16] ActiveEntries: The number of hash entries used in the active region. 33f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [20] ActiveBytes: The number of data bytes used in the active region. 34f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [24] Version number. 35f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [28] Checksum of [0..28). 36f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [32] Hash entries for region 0. The size is X = (12 * MaxEntries bytes). 37f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [32 + X] Hash entries for region 1. The size is also X. 38f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 39f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// Each hash entry is 12 bytes: 8 bytes key and 4 bytes offset into the data 40f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// file. The offset is 0 when the slot is free. Note that 0 is a valid value 41f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// for key. The keys are used directly as index into a hash table, so they 42f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// should be suitably distributed. 43f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 44f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// Each data file stores data for one region. The data file is concatenated 45f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// blobs followed by the magic number 0xBD248510. 46f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 47f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// The blob format: 48f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [0] Key of this blob 49f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [8] Checksum of this blob 50f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [12] Offset of this blob 51f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [16] Length of this blob (not including header) 52f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// [20] Blob 53f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 54f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// Below are the interface for BlobCache. The instance of this class does not 55f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// support concurrent use by multiple threads. 56f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 57f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public BlobCache(String path, int maxEntries, int maxBytes, boolean reset) throws IOException; 58f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public void insert(long key, byte[] data) throws IOException; 59f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public byte[] lookup(long key) throws IOException; 60f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public void lookup(LookupRequest req) throws IOException; 61f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public void close(); 62f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public void syncIndex(); 63f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public void syncAll(); 64f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// public static void deleteFiles(String path); 65f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin// 66f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linpackage com.android.gallery3d.common; 67f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 68f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport android.util.Log; 69f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 70f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.io.Closeable; 71f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.io.File; 72f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.io.IOException; 73f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.io.RandomAccessFile; 74f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.nio.ByteOrder; 75f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.nio.MappedByteBuffer; 76f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.nio.channels.FileChannel; 77f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Linimport java.util.zip.Adler32; 78f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 79c0715fd58c287347458756e34f07cee1fd72b982Owen Linpublic class BlobCache implements Closeable { 80f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final String TAG = "BlobCache"; 81f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 82f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int MAGIC_INDEX_FILE = 0xB3273030; 83f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int MAGIC_DATA_FILE = 0xBD248510; 84f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 85f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // index header offset 86f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_MAGIC = 0; 87f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_MAX_ENTRIES = 4; 88f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_MAX_BYTES = 8; 89f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_ACTIVE_REGION = 12; 90f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_ACTIVE_ENTRIES = 16; 91f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_ACTIVE_BYTES = 20; 92f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_VERSION = 24; 93f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int IH_CHECKSUM = 28; 94f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int INDEX_HEADER_SIZE = 32; 95f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 96f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int DATA_HEADER_SIZE = 4; 97f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 98f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // blob header offset 99f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int BH_KEY = 0; 100f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int BH_CHECKSUM = 8; 101f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int BH_OFFSET = 12; 102f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int BH_LENGTH = 16; 103f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static final int BLOB_HEADER_SIZE = 20; 104f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 105f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private RandomAccessFile mIndexFile; 106f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private RandomAccessFile mDataFile0; 107f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private RandomAccessFile mDataFile1; 108f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private FileChannel mIndexChannel; 109f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private MappedByteBuffer mIndexBuffer; 110f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 111f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mMaxEntries; 112f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mMaxBytes; 113f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mActiveRegion; 114f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mActiveEntries; 115f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mActiveBytes; 116f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mVersion; 117f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 118f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private RandomAccessFile mActiveDataFile; 119f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private RandomAccessFile mInactiveDataFile; 120f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mActiveHashStart; 121f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mInactiveHashStart; 122f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private byte[] mIndexHeader = new byte[INDEX_HEADER_SIZE]; 123f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private byte[] mBlobHeader = new byte[BLOB_HEADER_SIZE]; 124f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private Adler32 mAdler32 = new Adler32(); 125f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 126f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Creates the cache. Three files will be created: 127f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // path + ".idx", path + ".0", and path + ".1" 128f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The ".0" file and the ".1" file each stores data for a region. Each of 129f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // them can grow to the size specified by maxBytes. The maxEntries parameter 130f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // specifies the maximum number of entries each region can have. If the 131f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // "reset" parameter is true, the cache will be cleared before use. 132f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public BlobCache(String path, int maxEntries, int maxBytes, boolean reset) 133f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin throws IOException { 134f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin this(path, maxEntries, maxBytes, reset, 0); 135f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 136f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 137f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public BlobCache(String path, int maxEntries, int maxBytes, boolean reset, 138f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int version) throws IOException { 139f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile = new RandomAccessFile(path + ".idx", "rw"); 140f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0 = new RandomAccessFile(path + ".0", "rw"); 141f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1 = new RandomAccessFile(path + ".1", "rw"); 142f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mVersion = version; 143f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 144f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (!reset && loadIndex()) { 145f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return; 146f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 147f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 148f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin resetCache(maxEntries, maxBytes); 149f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 150f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (!loadIndex()) { 151f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeAll(); 152f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin throw new IOException("unable to load index"); 153f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 154f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 155f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 156f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Delete the files associated with the given path previously created 157f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // by the BlobCache constructor. 158f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public static void deleteFiles(String path) { 159f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin deleteFileSilently(path + ".idx"); 160f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin deleteFileSilently(path + ".0"); 161f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin deleteFileSilently(path + ".1"); 162f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 163f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 164f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private static void deleteFileSilently(String path) { 165f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 166f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin new File(path).delete(); 167f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 168f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // ignore; 169f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 170f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 171f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 172f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Close the cache. All resources are released. No other method should be 173f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // called after this is called. 174c0715fd58c287347458756e34f07cee1fd72b982Owen Lin @Override 175f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void close() { 176f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin syncAll(); 177f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeAll(); 178f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 179f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 180f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void closeAll() { 181f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeSilently(mIndexChannel); 182f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeSilently(mIndexFile); 183f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeSilently(mDataFile0); 184f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin closeSilently(mDataFile1); 185f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 186f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 187f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Returns true if loading index is successful. After this method is called, 188f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // mIndexHeader and index header in file should be kept sync. 189f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private boolean loadIndex() { 190f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 191f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile.seek(0); 192f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0.seek(0); 193f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1.seek(0); 194f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 195f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] buf = mIndexHeader; 196f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mIndexFile.read(buf) != INDEX_HEADER_SIZE) { 197f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read header"); 198f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 199f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 200f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 201f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (readInt(buf, IH_MAGIC) != MAGIC_INDEX_FILE) { 202f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read header magic"); 203f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 204f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 205f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 206f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (readInt(buf, IH_VERSION) != mVersion) { 207f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "version mismatch"); 208f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 209f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 210f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 211f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mMaxEntries = readInt(buf, IH_MAX_ENTRIES); 212f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mMaxBytes = readInt(buf, IH_MAX_BYTES); 213f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveRegion = readInt(buf, IH_ACTIVE_REGION); 214f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveEntries = readInt(buf, IH_ACTIVE_ENTRIES); 215f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveBytes = readInt(buf, IH_ACTIVE_BYTES); 216f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 217f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int sum = readInt(buf, IH_CHECKSUM); 218f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (checkSum(buf, 0, IH_CHECKSUM) != sum) { 219f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "header checksum does not match"); 220f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 221f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 222f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 223f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Sanity check 224f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mMaxEntries <= 0) { 225f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid max entries"); 226f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 227f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 228f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mMaxBytes <= 0) { 229f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid max bytes"); 230f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 231f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 232f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveRegion != 0 && mActiveRegion != 1) { 233f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid active region"); 234f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 235f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 236f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveEntries < 0 || mActiveEntries > mMaxEntries) { 237f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid active entries"); 238f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 239f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 240f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveBytes < DATA_HEADER_SIZE || mActiveBytes > mMaxBytes) { 241f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid active bytes"); 242f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 243f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 244f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mIndexFile.length() != 245f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin INDEX_HEADER_SIZE + mMaxEntries * 12 * 2) { 246f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid index file length"); 247f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 248f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 249f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 250f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Make sure data file has magic 251f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] magic = new byte[4]; 252f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mDataFile0.read(magic) != 4) { 253f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read data file magic"); 254f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 255f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 256f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (readInt(magic, 0) != MAGIC_DATA_FILE) { 257f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid data file magic"); 258f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 259f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 260f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mDataFile1.read(magic) != 4) { 261f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read data file magic"); 262f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 263f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 264f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (readInt(magic, 0) != MAGIC_DATA_FILE) { 265f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid data file magic"); 266f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 267f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 268f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 269f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Map index file to memory 270f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexChannel = mIndexFile.getChannel(); 271f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer = mIndexChannel.map(FileChannel.MapMode.READ_WRITE, 272f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 0, mIndexFile.length()); 273f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.order(ByteOrder.LITTLE_ENDIAN); 274f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 275f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin setActiveVariables(); 276f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 277f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (IOException ex) { 278f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.e(TAG, "loadIndex failed.", ex); 279f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 280f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 281f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 282f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 283f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void setActiveVariables() throws IOException { 284f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveDataFile = (mActiveRegion == 0) ? mDataFile0 : mDataFile1; 285f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mInactiveDataFile = (mActiveRegion == 1) ? mDataFile0 : mDataFile1; 286f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveDataFile.setLength(mActiveBytes); 287f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveDataFile.seek(mActiveBytes); 288f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 289f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveHashStart = INDEX_HEADER_SIZE; 290f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mInactiveHashStart = INDEX_HEADER_SIZE; 291f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 292f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveRegion == 0) { 293f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mInactiveHashStart += mMaxEntries * 12; 294f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 295f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveHashStart += mMaxEntries * 12; 296f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 297f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 298f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 299f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void resetCache(int maxEntries, int maxBytes) throws IOException { 300f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile.setLength(0); // truncate to zero the index 301f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile.setLength(INDEX_HEADER_SIZE + maxEntries * 12 * 2); 302f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile.seek(0); 303f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] buf = mIndexHeader; 304f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_MAGIC, MAGIC_INDEX_FILE); 305f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_MAX_ENTRIES, maxEntries); 306f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_MAX_BYTES, maxBytes); 307f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_ACTIVE_REGION, 0); 308f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_ACTIVE_ENTRIES, 0); 309f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_ACTIVE_BYTES, DATA_HEADER_SIZE); 310f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_VERSION, mVersion); 311f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, IH_CHECKSUM, checkSum(buf, 0, IH_CHECKSUM)); 312f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexFile.write(buf); 313f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // This is only needed if setLength does not zero the extended part. 314f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // writeZero(mIndexFile, maxEntries * 12 * 2); 315f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 316f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0.setLength(0); 317f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1.setLength(0); 318f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0.seek(0); 319f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1.seek(0); 320f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(buf, 0, MAGIC_DATA_FILE); 321f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0.write(buf, 0, 4); 322f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1.write(buf, 0, 4); 323f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 324f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 325f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Flip the active region and the inactive region. 326f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void flipRegion() throws IOException { 327f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveRegion = 1 - mActiveRegion; 328f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveEntries = 0; 329f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveBytes = DATA_HEADER_SIZE; 330f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 331f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_REGION, mActiveRegion); 332f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries); 333f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_BYTES, mActiveBytes); 334f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin updateIndexHeader(); 335f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 336f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin setActiveVariables(); 337f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin clearHash(mActiveHashStart); 338f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin syncIndex(); 339f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 340f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 341f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Sync mIndexHeader to the index file. 342f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void updateIndexHeader() { 343f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_CHECKSUM, 344f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin checkSum(mIndexHeader, 0, IH_CHECKSUM)); 345f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.position(0); 346f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.put(mIndexHeader); 347f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 348f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 349f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Clear the hash table starting from the specified offset. 350f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void clearHash(int hashStart) { 351f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] zero = new byte[1024]; 352f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.position(hashStart); 353f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int count = mMaxEntries * 12; count > 0;) { 354f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int todo = Math.min(count, 1024); 355f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.put(zero, 0, todo); 356f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin count -= todo; 357f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 358f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 359f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 360f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Inserts a (key, data) pair into the cache. 361f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void insert(long key, byte[] data) throws IOException { 362f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (DATA_HEADER_SIZE + BLOB_HEADER_SIZE + data.length > mMaxBytes) { 363f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin throw new RuntimeException("blob is too large!"); 364f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 365f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 366f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveBytes + BLOB_HEADER_SIZE + data.length > mMaxBytes 367f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin || mActiveEntries * 2 >= mMaxEntries) { 368f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin flipRegion(); 369f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 370f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 371f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (!lookupInternal(key, mActiveHashStart)) { 372f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // If we don't have an existing entry with the same key, increase 373f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // the entry count. 374f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveEntries++; 375f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries); 376f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 377f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 378f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin insertInternal(key, data, data.length); 379f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin updateIndexHeader(); 380f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 381f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 382f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Appends the data to the active file. It also updates the hash entry. 383f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The proper hash entry (suitable for insertion or replacement) must be 384f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // pointed by mSlotOffset. 385f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private void insertInternal(long key, byte[] data, int length) 386f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin throws IOException { 387f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] header = mBlobHeader; 388f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int sum = checkSum(data); 389f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeLong(header, BH_KEY, key); 390f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(header, BH_CHECKSUM, sum); 391f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(header, BH_OFFSET, mActiveBytes); 392f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(header, BH_LENGTH, length); 393f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveDataFile.write(header); 394f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveDataFile.write(data, 0, length); 395f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 396f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.putLong(mSlotOffset, key); 397f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.putInt(mSlotOffset + 8, mActiveBytes); 398f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveBytes += BLOB_HEADER_SIZE + length; 399f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_BYTES, mActiveBytes); 400f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 401f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 402f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public static class LookupRequest { 403f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public long key; // input: the key to find 404f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public byte[] buffer; // input/output: the buffer to store the blob 405f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public int length; // output: the length of the blob 406f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 407f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 408f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // This method is for one-off lookup. For repeated lookup, use the version 409f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // accepting LookupRequest to avoid repeated memory allocation. 410f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private LookupRequest mLookupRequest = new LookupRequest(); 411f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public byte[] lookup(long key) throws IOException { 412f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mLookupRequest.key = key; 413f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mLookupRequest.buffer = null; 414f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (lookup(mLookupRequest)) { 415f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return mLookupRequest.buffer; 416f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 417f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return null; 418f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 419f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 420f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 421f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Returns true if the associated blob for the given key is available. 422f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The blob is stored in the buffer pointed by req.buffer, and the length 423f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // is in stored in the req.length variable. 424f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // 425f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The user can input a non-null value in req.buffer, and this method will 426f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // try to use that buffer. If that buffer is not large enough, this method 427f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // will allocate a new buffer and assign it to req.buffer. 428f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // 429f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // This method tries not to throw IOException even if the data file is 430f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // corrupted, but it can still throw IOException if things get strange. 431f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public boolean lookup(LookupRequest req) throws IOException { 432f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Look up in the active region first. 433f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (lookupInternal(req.key, mActiveHashStart)) { 434f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (getBlob(mActiveDataFile, mFileOffset, req)) { 435f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 436f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 437f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 438f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 439f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // We want to copy the data from the inactive file to the active file 440f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // if it's available. So we keep the offset of the hash entry so we can 441f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // avoid looking it up again. 442f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int insertOffset = mSlotOffset; 443f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 444f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Look up in the inactive region. 445f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (lookupInternal(req.key, mInactiveHashStart)) { 446f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (getBlob(mInactiveDataFile, mFileOffset, req)) { 447f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // If we don't have enough space to insert this blob into 448f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // the active file, just return it. 449f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (mActiveBytes + BLOB_HEADER_SIZE + req.length > mMaxBytes 450f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin || mActiveEntries * 2 >= mMaxEntries) { 451f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 452f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 453f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Otherwise copy it over. 454f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mSlotOffset = insertOffset; 455f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 456f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin insertInternal(req.key, req.buffer, req.length); 457f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mActiveEntries++; 458f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin writeInt(mIndexHeader, IH_ACTIVE_ENTRIES, mActiveEntries); 459f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin updateIndexHeader(); 460f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 461f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.e(TAG, "cannot copy over"); 462f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 463f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 464f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 465f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 466f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 467f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 468f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 469f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 470f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 471f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Copies the blob for the specified offset in the specified file to 472f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // req.buffer. If req.buffer is null or too small, allocate a buffer and 473f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // assign it to req.buffer. 474f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Returns false if the blob is not available (either the index file is 475f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // not sync with the data file, or one of them is corrupted). The length 476f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // of the blob is stored in the req.length variable. 477f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private boolean getBlob(RandomAccessFile file, int offset, 478f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin LookupRequest req) throws IOException { 479f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] header = mBlobHeader; 480f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin long oldPosition = file.getFilePointer(); 481f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 482f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin file.seek(offset); 483f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (file.read(header) != BLOB_HEADER_SIZE) { 484f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read blob header"); 485f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 486f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 487f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin long blobKey = readLong(header, BH_KEY); 488f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (blobKey != req.key) { 489f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "blob key does not match: " + blobKey); 490f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 491f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 492f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int sum = readInt(header, BH_CHECKSUM); 493f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int blobOffset = readInt(header, BH_OFFSET); 494f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (blobOffset != offset) { 495f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "blob offset does not match: " + blobOffset); 496f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 497f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 498f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int length = readInt(header, BH_LENGTH); 499f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (length < 0 || length > mMaxBytes - offset - BLOB_HEADER_SIZE) { 500f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "invalid blob length: " + length); 501f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 502f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 503f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (req.buffer == null || req.buffer.length < length) { 504f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin req.buffer = new byte[length]; 505f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 506f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 507f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin byte[] blob = req.buffer; 508f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin req.length = length; 509f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 510f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (file.read(blob, 0, length) != length) { 511f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "cannot read blob data"); 512f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 513f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 514f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (checkSum(blob, 0, length) != sum) { 515f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "blob checksum does not match: " + sum); 516f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 517f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 518f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 519f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 520f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.e(TAG, "getBlob failed.", t); 521f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 522f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } finally { 523f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin file.seek(oldPosition); 524f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 525f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 526f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 527f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Tries to look up a key in the specified hash region. 528f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Returns true if the lookup is successful. 529f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // The slot offset in the index file is saved in mSlotOffset. If the lookup 530f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // is successful, it's the slot found. Otherwise it's the slot suitable for 531f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // insertion. 532f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // If the lookup is successful, the file offset is also saved in 533f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // mFileOffset. 534f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mSlotOffset; 535f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private int mFileOffset; 536f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin private boolean lookupInternal(long key, int hashStart) { 537f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int slot = (int) (key % mMaxEntries); 538f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (slot < 0) slot += mMaxEntries; 539f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int slotBegin = slot; 540f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin while (true) { 541f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int offset = hashStart + slot * 12; 542f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin long candidateKey = mIndexBuffer.getLong(offset); 543f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int candidateOffset = mIndexBuffer.getInt(offset + 8); 544f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (candidateOffset == 0) { 545f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mSlotOffset = offset; 546f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return false; 547f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else if (candidateKey == key) { 548f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mSlotOffset = offset; 549f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mFileOffset = candidateOffset; 550f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return true; 551f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 552f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (++slot >= mMaxEntries) { 553f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin slot = 0; 554f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 555f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (slot == slotBegin) { 556f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "corrupted index: clear the slot."); 557f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.putInt(hashStart + slot * 12 + 8, 0); 558f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 559f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 560f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 561f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 562f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 563f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void syncIndex() { 564f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 565f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mIndexBuffer.force(); 566f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 567f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "sync index failed", t); 568f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 569f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 570f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 571f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin public void syncAll() { 572f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin syncIndex(); 573f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 574f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile0.getFD().sync(); 575f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 576f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "sync data file 0 failed", t); 577f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 578f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 579f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mDataFile1.getFD().sync(); 580f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 581f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.w(TAG, "sync data file 1 failed", t); 582f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 583f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 584f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 585f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // This is for testing only. 586f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // 587f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // Returns the active count (mActiveEntries). This also verifies that 588f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // the active count matches matches what's inside the hash region. 589f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int getActiveCount() { 590f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int count = 0; 591f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < mMaxEntries; i++) { 592f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int offset = mActiveHashStart + i * 12; 593f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin long candidateKey = mIndexBuffer.getLong(offset); 594f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int candidateOffset = mIndexBuffer.getInt(offset + 8); 595f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (candidateOffset != 0) ++count; 596f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 597f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (count == mActiveEntries) { 598f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return count; 599f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } else { 600f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin Log.e(TAG, "wrong active count: " + mActiveEntries + " vs " + count); 601f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return -1; // signal failure. 602f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 603f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 604f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 605f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int checkSum(byte[] data) { 606f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mAdler32.reset(); 607f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mAdler32.update(data); 608f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return (int) mAdler32.getValue(); 609f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 610f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 611f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin int checkSum(byte[] data, int offset, int nbytes) { 612f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mAdler32.reset(); 613f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin mAdler32.update(data, offset, nbytes); 614f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return (int) mAdler32.getValue(); 615f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 616f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 617f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin static void closeSilently(Closeable c) { 618f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin if (c == null) return; 619f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin try { 620f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin c.close(); 621f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } catch (Throwable t) { 622f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin // do nothing 623f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 624f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 625f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 626f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin static int readInt(byte[] buf, int offset) { 627f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return (buf[offset] & 0xff) 628f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin | ((buf[offset + 1] & 0xff) << 8) 629f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin | ((buf[offset + 2] & 0xff) << 16) 630f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin | ((buf[offset + 3] & 0xff) << 24); 631f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 632f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 633f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin static long readLong(byte[] buf, int offset) { 634f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin long result = buf[offset + 7] & 0xff; 635f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 6; i >= 0; i--) { 636f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin result = (result << 8) | (buf[offset + i] & 0xff); 637f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 638f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin return result; 639f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 640f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 641f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin static void writeInt(byte[] buf, int offset, int value) { 642f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < 4; i++) { 643f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin buf[offset + i] = (byte) (value & 0xff); 644f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin value >>= 8; 645f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 646f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 647f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin 648f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin static void writeLong(byte[] buf, int offset, long value) { 649f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin for (int i = 0; i < 8; i++) { 650f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin buf[offset + i] = (byte) (value & 0xff); 651f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin value >>= 8; 652f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 653f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin } 654f9a0a4306d589b4a4e20554fed512a603426bfa1Owen Lin} 655