Subversion Repositories SmartDukaan

/**
 * Copyright 2010-present Facebook.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.facebook.internal;

import android.content.Context;
import android.util.Log;
import com.facebook.LoggingBehavior;
import com.facebook.Settings;
import org.json.JSONException;
import org.json.JSONObject;
import org.json.JSONTokener;

import java.io.*;
import java.security.InvalidParameterException;
import java.util.Date;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicLong;

// This class is intended to be thread-safe.
//
// There are two classes of files:  buffer files and cache files:
// - A buffer file is in the process of being written, and there is an open stream on the file.  These files are
//   named as "bufferN" where N is an incrementing integer.  On startup, we delete all existing files of this form.
//   Once the stream is closed, we rename the buffer file to a cache file or attempt to delete if this fails.  We
//   do not otherwise ever attempt to delete these files.
// - A cache file is a non-changing file that is named by the md5 hash of the cache key.  We monitor the size of
//   these files in aggregate and remove the oldest one(s) to stay under quota.  This process does not block threads
//   calling into this class, so theoretically we could go arbitrarily over quota but in practice this should not
//   happen because deleting files should be much cheaper than downloading new file content.
//
// Since there can only ever be one thread accessing a particular buffer file, we do not synchronize access to these.
// We do assume that file rename is atomic when converting a buffer file to a cache file, and that if multiple files
// are renamed to a single target that exactly one of them continues to exist.
//
// Standard POSIX file semantics guarantee being able to continue to use a file handle even after the
// corresponding file has been deleted.  Given this and that cache files never change other than deleting in trim()
// or clear(),  we only have to ensure that there is at most one trim() or clear() process deleting files at any
// given time.

/**
 * com.facebook.internal is solely for the use of other packages within the Facebook SDK for Android. Use of
 * any of the classes in this package is unsupported, and they may be modified or removed without warning at
 * any time.
 */
public final class FileLruCache {
    static final String TAG = FileLruCache.class.getSimpleName();
    private static final String HEADER_CACHEKEY_KEY = "key";
    private static final String HEADER_CACHE_CONTENT_TAG_KEY = "tag";

    private static final AtomicLong bufferIndex = new AtomicLong();

    private final String tag;
    private final Limits limits;
    private final File directory;
    private boolean isTrimPending;
    private boolean isTrimInProgress;
    private final Object lock;
    private AtomicLong lastClearCacheTime = new AtomicLong(0);

    // The value of tag should be a final String that works as a directory name.
    public FileLruCache(Context context, String tag, Limits limits) {
        this.tag = tag;
        this.limits = limits;
        this.directory = new File(context.getCacheDir(), tag);
        this.lock = new Object();

        // Ensure the cache dir exists
        if (this.directory.mkdirs() || this.directory.isDirectory()) {
            // Remove any stale partially-written files from a previous run
            BufferFile.deleteAll(this.directory);
        }
    }

    // This is not robust to files changing dynamically underneath it and should therefore only be used
    // for test code.  If we ever need this for product code we need to think through synchronization.
    // See the threading notes at the top of this class.
    //
    // Also, since trim() runs asynchronously now, this blocks until any pending trim has completed.
    long sizeInBytesForTest() {
        synchronized (lock) {
            while (isTrimPending || isTrimInProgress) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    // intentional no-op
                }
            }
        }

        File[] files = this.directory.listFiles();
        long total = 0;
        if (files != null) {
            for (File file : files) {
                total += file.length();
            }
        }
        return total;
    }

    public InputStream get(String key) throws IOException {
        return get(key, null);
    }

    public InputStream get(String key, String contentTag) throws IOException {
        File file = new File(this.directory, Utility.md5hash(key));

        FileInputStream input = null;
        try {
            input = new FileInputStream(file);
        } catch (IOException e) {
            return null;
        }

        BufferedInputStream buffered = new BufferedInputStream(input, Utility.DEFAULT_STREAM_BUFFER_SIZE);
        boolean success = false;

        try {
            JSONObject header = StreamHeader.readHeader(buffered);
            if (header == null) {
                return null;
            }

            String foundKey = header.optString(HEADER_CACHEKEY_KEY);
            if ((foundKey == null) || !foundKey.equals(key)) {
                return null;
            }

            String headerContentTag = header.optString(HEADER_CACHE_CONTENT_TAG_KEY, null);

            if ((contentTag == null && headerContentTag != null) ||
                    (contentTag != null && !contentTag.equals(headerContentTag))) {
                return null;
            }

            long accessTime = new Date().getTime();
            Logger.log(LoggingBehavior.CACHE, TAG, "Setting lastModified to " + Long.valueOf(accessTime) + " for "
                    + file.getName());
            file.setLastModified(accessTime);

            success = true;
            return buffered;
        } finally {
            if (!success) {
                buffered.close();
            }
        }
    }

    OutputStream openPutStream(final String key) throws IOException {
        return openPutStream(key, null);
    }

    public OutputStream openPutStream(final String key, String contentTag) throws IOException {
        final File buffer = BufferFile.newFile(this.directory);
        buffer.delete();
        if (!buffer.createNewFile()) {
            throw new IOException("Could not create file at " + buffer.getAbsolutePath());
        }

        FileOutputStream file = null;
        try {
            file = new FileOutputStream(buffer);
        } catch (FileNotFoundException e) {
            Logger.log(LoggingBehavior.CACHE, Log.WARN, TAG, "Error creating buffer output stream: " + e);
            throw new IOException(e.getMessage());
        }

        final long bufferFileCreateTime = System.currentTimeMillis();
        StreamCloseCallback renameToTargetCallback = new StreamCloseCallback() {
            @Override
            public void onClose() {
                // if the buffer file was created before the cache was cleared, then the buffer file
                // should be deleted rather than renamed and saved.
                if (bufferFileCreateTime < lastClearCacheTime.get()) {
                    buffer.delete();
                } else {
                    renameToTargetAndTrim(key, buffer);
                }
            }
        };

        CloseCallbackOutputStream cleanup = new CloseCallbackOutputStream(file, renameToTargetCallback);
        BufferedOutputStream buffered = new BufferedOutputStream(cleanup, Utility.DEFAULT_STREAM_BUFFER_SIZE);
        boolean success = false;

        try {
            // Prefix the stream with the actual key, since there could be collisions
            JSONObject header = new JSONObject();
            header.put(HEADER_CACHEKEY_KEY, key);
            if (!Utility.isNullOrEmpty(contentTag)) {
                header.put(HEADER_CACHE_CONTENT_TAG_KEY, contentTag);
            }

            StreamHeader.writeHeader(buffered, header);

            success = true;
            return buffered;
        } catch (JSONException e) {
            // JSON is an implementation detail of the cache, so don't let JSON exceptions out.
            Logger.log(LoggingBehavior.CACHE, Log.WARN, TAG, "Error creating JSON header for cache file: " + e);
            throw new IOException(e.getMessage());
        } finally {
            if (!success) {
                buffered.close();
            }
        }
    }

    public void clearCache() {
        // get the current directory listing of files to delete
        final File[] filesToDelete = directory.listFiles(BufferFile.excludeBufferFiles());
        lastClearCacheTime.set(System.currentTimeMillis());
        if (filesToDelete != null) {
            Settings.getExecutor().execute(new Runnable() {
                @Override
                public void run() {
                    for (File file : filesToDelete) {
                        file.delete();
                    }
                }
            });
        }
    }

    private void renameToTargetAndTrim(String key, File buffer) {
        final File target = new File(directory, Utility.md5hash(key));

        // This is triggered by close().  By the time close() returns, the file should be cached, so this needs to
        // happen synchronously on this thread.
        //
        // However, it does not need to be synchronized, since in the race we will just start an unnecesary trim
        // operation.  Avoiding the cost of holding the lock across the file operation seems worth this cost.
        if (!buffer.renameTo(target)) {
            buffer.delete();
        }

        postTrim();
    }

    // Opens an output stream for the key, and creates an input stream wrapper to copy
    // the contents of input into the new output stream.  The effect is to store a
    // copy of input, and associate that data with key.
    public InputStream interceptAndPut(String key, InputStream input) throws IOException {
        OutputStream output = openPutStream(key);
        return new CopyingInputStream(input, output);
    }

    public String toString() {
        return "{FileLruCache:" + " tag:" + this.tag + " file:" + this.directory.getName() + "}";
    }

    private void postTrim() {
        synchronized (lock) {
            if (!isTrimPending) {
                isTrimPending = true;
                Settings.getExecutor().execute(new Runnable() {
                    @Override
                    public void run() {
                        trim();
                    }
                });
            }
        }
    }

    private void trim() {
        synchronized (lock) {
            isTrimPending = false;
            isTrimInProgress = true;
        }
        try {
            Logger.log(LoggingBehavior.CACHE, TAG, "trim started");
            PriorityQueue<ModifiedFile> heap = new PriorityQueue<ModifiedFile>();
            long size = 0;
            long count = 0;
            File[] filesToTrim =this.directory.listFiles(BufferFile.excludeBufferFiles());
            if (filesToTrim != null) {
                for (File file : filesToTrim) {
                    ModifiedFile modified = new ModifiedFile(file);
                    heap.add(modified);
                    Logger.log(LoggingBehavior.CACHE, TAG, "  trim considering time=" + Long.valueOf(modified.getModified())
                            + " name=" + modified.getFile().getName());

                    size += file.length();
                    count++;
                }
            }

            while ((size > limits.getByteCount()) || (count > limits.getFileCount())) {
                File file = heap.remove().getFile();
                Logger.log(LoggingBehavior.CACHE, TAG, "  trim removing " + file.getName());
                size -= file.length();
                count--;
                file.delete();
            }
        } finally {
            synchronized (lock) {
                isTrimInProgress = false;
                lock.notifyAll();
            }
        }
    }

    private static class BufferFile {
        private static final String FILE_NAME_PREFIX = "buffer";
        private static final FilenameFilter filterExcludeBufferFiles = new FilenameFilter() {
            @Override
            public boolean accept(File dir, String filename) {
                return !filename.startsWith(FILE_NAME_PREFIX);
            }
        };
        private static final FilenameFilter filterExcludeNonBufferFiles = new FilenameFilter() {
            @Override
            public boolean accept(File dir, String filename) {
                return filename.startsWith(FILE_NAME_PREFIX);
            }
        };

        static void deleteAll(final File root) {
            File[] filesToDelete = root.listFiles(excludeNonBufferFiles());
            if (filesToDelete != null) {
                for (File file : filesToDelete) {
                    file.delete();
                }
            }
        }

        static FilenameFilter excludeBufferFiles() {
            return filterExcludeBufferFiles;
        }

        static FilenameFilter excludeNonBufferFiles() {
            return filterExcludeNonBufferFiles;
        }

        static File newFile(final File root) {
            String name = FILE_NAME_PREFIX + Long.valueOf(bufferIndex.incrementAndGet()).toString();
            return new File(root, name);
        }
    }

    // Treats the first part of a stream as a header, reads/writes it as a JSON blob, and
    // leaves the stream positioned exactly after the header.
    //
    // The format is as follows:
    //     byte: meaning
    // ---------------------------------
    //        0: version number
    //      1-3: big-endian JSON header blob size
    // 4-size+4: UTF-8 JSON header blob
    //      ...: stream data
    private static final class StreamHeader {
        private static final int HEADER_VERSION = 0;

        static void writeHeader(OutputStream stream, JSONObject header) throws IOException {
            String headerString = header.toString();
            byte[] headerBytes = headerString.getBytes();

            // Write version number and big-endian header size
            stream.write(HEADER_VERSION);
            stream.write((headerBytes.length >> 16) & 0xff);
            stream.write((headerBytes.length >> 8) & 0xff);
            stream.write((headerBytes.length >> 0) & 0xff);

            stream.write(headerBytes);
        }

        static JSONObject readHeader(InputStream stream) throws IOException {
            int version = stream.read();
            if (version != HEADER_VERSION) {
                return null;
            }

            int headerSize = 0;
            for (int i = 0; i < 3; i++) {
                int b = stream.read();
                if (b == -1) {
                    Logger.log(LoggingBehavior.CACHE, TAG,
                            "readHeader: stream.read returned -1 while reading header size");
                    return null;
                }
                headerSize <<= 8;
                headerSize += b & 0xff;
            }

            byte[] headerBytes = new byte[headerSize];
            int count = 0;
            while (count < headerBytes.length) {
                int readCount = stream.read(headerBytes, count, headerBytes.length - count);
                if (readCount < 1) {
                    Logger.log(LoggingBehavior.CACHE, TAG,
                            "readHeader: stream.read stopped at " + Integer.valueOf(count) + " when expected "
                                    + headerBytes.length);
                    return null;
                }
                count += readCount;
            }

            String headerString = new String(headerBytes);
            JSONObject header = null;
            JSONTokener tokener = new JSONTokener(headerString);
            try {
                Object parsed = tokener.nextValue();
                if (!(parsed instanceof JSONObject)) {
                    Logger.log(LoggingBehavior.CACHE, TAG, "readHeader: expected JSONObject, got " + parsed.getClass().getCanonicalName());
                    return null;
                }
                header = (JSONObject) parsed;
            } catch (JSONException e) {
                throw new IOException(e.getMessage());
            }

            return header;
        }
    }

    private static class CloseCallbackOutputStream extends OutputStream {
        final OutputStream innerStream;
        final StreamCloseCallback callback;

        CloseCallbackOutputStream(OutputStream innerStream, StreamCloseCallback callback) {
            this.innerStream = innerStream;
            this.callback = callback;
        }

        @Override
        public void close() throws IOException {
            try {
                this.innerStream.close();
            } finally {
                this.callback.onClose();
            }
        }

        @Override
        public void flush() throws IOException {
            this.innerStream.flush();
        }

        @Override
        public void write(byte[] buffer, int offset, int count) throws IOException {
            this.innerStream.write(buffer, offset, count);
        }

        @Override
        public void write(byte[] buffer) throws IOException {
            this.innerStream.write(buffer);
        }

        @Override
        public void write(int oneByte) throws IOException {
            this.innerStream.write(oneByte);
        }
    }

    private static final class CopyingInputStream extends InputStream {
        final InputStream input;
        final OutputStream output;

        CopyingInputStream(final InputStream input, final OutputStream output) {
            this.input = input;
            this.output = output;
        }

        @Override
        public int available() throws IOException {
            return input.available();
        }

        @Override
        public void close() throws IOException {
            // According to http://www.cs.cornell.edu/andru/javaspec/11.doc.html:
            //  "If a finally clause is executed because of abrupt completion of a try block and the finally clause
            //   itself completes abruptly, then the reason for the abrupt completion of the try block is discarded
            //   and the new reason for abrupt completion is propagated from there."
            //
            // Android does appear to behave like this.
            try {
                this.input.close();
            } finally {
                this.output.close();
            }
        }

        @Override
        public void mark(int readlimit) {
            throw new UnsupportedOperationException();
        }

        @Override
        public boolean markSupported() {
            return false;
        }

        @Override
        public int read(byte[] buffer) throws IOException {
            int count = input.read(buffer);
            if (count > 0) {
                output.write(buffer, 0, count);
            }
            return count;
        }

        @Override
        public int read() throws IOException {
            int b = input.read();
            if (b >= 0) {
                output.write(b);
            }
            return b;
        }

        @Override
        public int read(byte[] buffer, int offset, int length) throws IOException {
            int count = input.read(buffer, offset, length);
            if (count > 0) {
                output.write(buffer, offset, count);
            }
            return count;
        }

        @Override
        public synchronized void reset() {
            throw new UnsupportedOperationException();
        }

        @Override
        public long skip(long byteCount) throws IOException {
            byte[] buffer = new byte[1024];
            long total = 0;
            while (total < byteCount) {
                int count = read(buffer, 0, (int)Math.min(byteCount - total, buffer.length));
                if (count < 0) {
                    return total;
                }
                total += count;
            }
            return total;
        }
    }

    public static final class Limits {
        private int byteCount;
        private int fileCount;

        public Limits() {
            // A Samsung Galaxy Nexus can create 1k files in half a second.  By the time
            // it gets to 5k files it takes 5 seconds.  10k files took 15 seconds.  This
            // continues to slow down as files are added.  This assumes all files are in
            // a single directory.
            //
            // Following a git-like strategy where we partition MD5-named files based on
            // the first 2 characters is slower across the board.
            this.fileCount = 1024;
            this.byteCount = 1024 * 1024;
        }

        int getByteCount() {
            return byteCount;
        }

        int getFileCount() {
            return fileCount;
        }

        void setByteCount(int n) {
            if (n < 0) {
                throw new InvalidParameterException("Cache byte-count limit must be >= 0");
            }
            byteCount = n;
        }

        void setFileCount(int n) {
            if (n < 0) {
                throw new InvalidParameterException("Cache file count limit must be >= 0");
            }
            fileCount = n;
        }
    }

    // Caches the result of lastModified during sort/heap operations
    private final static class ModifiedFile implements Comparable<ModifiedFile> {
        private static final int HASH_SEED = 29; // Some random prime number
        private static final int HASH_MULTIPLIER = 37; // Some random prime number

        private final File file;
        private final long modified;

        ModifiedFile(File file) {
            this.file = file;
            this.modified = file.lastModified();
        }

        File getFile() {
            return file;
        }

        long getModified() {
            return modified;
        }

        @Override
        public int compareTo(ModifiedFile another) {
            if (getModified() < another.getModified()) {
                return -1;
            } else if (getModified() > another.getModified()) {
                return 1;
            } else {
                return getFile().compareTo(another.getFile());
            }
        }

        @Override
        public boolean equals(Object another) {
            return
                    (another instanceof ModifiedFile) &&
                    (compareTo((ModifiedFile)another) == 0);
        }

        @Override
        public int hashCode() {
            int result = HASH_SEED;

            result = (result * HASH_MULTIPLIER) + file.hashCode();
            result = (result * HASH_MULTIPLIER) + (int) (modified % Integer.MAX_VALUE);

            return result;
        }
    }

    private interface StreamCloseCallback {
        void onClose();
    }
}