diff --git a/src/com/android/contacts/calllog/CallLogFragment.java b/src/com/android/contacts/calllog/CallLogFragment.java
index bcffd1c..31373cc 100644
--- a/src/com/android/contacts/calllog/CallLogFragment.java
+++ b/src/com/android/contacts/calllog/CallLogFragment.java
@@ -21,6 +21,7 @@
 import com.android.contacts.ContactPhotoManager;
 import com.android.contacts.ContactsUtils;
 import com.android.contacts.R;
+import com.android.contacts.util.ExpirableCache;
 import com.android.internal.telephony.CallerInfo;
 import com.google.common.annotations.VisibleForTesting;
 
@@ -68,7 +69,6 @@
 import android.widget.TextView;
 
 import java.lang.ref.WeakReference;
-import java.util.HashMap;
 import java.util.LinkedList;
 
 /**
@@ -78,6 +78,11 @@
         implements View.OnCreateContextMenuListener {
     private static final String TAG = "CallLogFragment";
 
+    /**
+     * The size of the cache of contact info.
+     */
+    private static final int CONTACT_INFO_CACHE_SIZE = 100;
+
     /** The query for the call log table */
     private static final class CallLogQuery {
         public static final String[] _PROJECTION = new String[] {
@@ -164,7 +169,7 @@
     /** Adapter class to fill in data for the Call Log */
     public final class CallLogAdapter extends GroupingListAdapter
             implements Runnable, ViewTreeObserver.OnPreDrawListener, View.OnClickListener {
-        HashMap<String,ContactInfo> mContactInfo;
+        ExpirableCache<String, ContactInfo> mContactInfoCache;
         private final LinkedList<CallerInfoQuery> mRequests;
         private volatile boolean mDone;
         private boolean mLoading = true;
@@ -228,7 +233,7 @@
         public CallLogAdapter() {
             super(getActivity());
 
-            mContactInfo = new HashMap<String,ContactInfo>();
+            mContactInfoCache = ExpirableCache.create(CONTACT_INFO_CACHE_SIZE);
             mRequests = new LinkedList<CallerInfoQuery>();
             mPreDrawListener = null;
 
@@ -268,7 +273,7 @@
         }
 
         public ContactInfo getContactInfo(String number) {
-            return mContactInfo.get(number);
+            return mContactInfoCache.getPossiblyExpired(number);
         }
 
         public void startRequestProcessing() {
@@ -292,10 +297,8 @@
             if (mCallerIdThread != null) mCallerIdThread.interrupt();
         }
 
-        public void clearCache() {
-            synchronized (mContactInfo) {
-                mContactInfo.clear();
-            }
+        public void invalidateCache() {
+            mContactInfoCache.expireAll();
         }
 
         private void updateCallLog(CallerInfoQuery ciq, ContactInfo ci) {
@@ -341,7 +344,7 @@
         private boolean queryContactInfo(CallerInfoQuery ciq) {
             // First check if there was a prior request for the same number
             // that was already satisfied
-            ContactInfo info = mContactInfo.get(ciq.number);
+            ContactInfo info = mContactInfoCache.get(ciq.number);
             boolean needNotify = false;
             if (info != null && info != ContactInfo.EMPTY) {
                 return true;
@@ -446,7 +449,7 @@
                     // cache. Any cache fills happen only on the GUI thread.
                     info.formattedNumber = null;
 
-                    mContactInfo.put(ciq.number, info);
+                    mContactInfoCache.put(ciq.number, info);
 
                     // Inform list to update this item, if in view
                     needNotify = true;
@@ -639,12 +642,15 @@
             }
 
             // Lookup contacts with this number
-            ContactInfo info = mContactInfo.get(number);
-            if (info == null) {
+            ExpirableCache.CachedValue<ContactInfo> cachedInfo =
+                    mContactInfoCache.getCachedValue(number);
+            ContactInfo info = cachedInfo == null ? null : cachedInfo.getValue();
+            if (cachedInfo == null) {
                 // Mark it as empty and queue up a request to find the name
                 // The db request should happen on a non-UI thread
                 info = ContactInfo.EMPTY;
-                mContactInfo.put(number, info);
+                mContactInfoCache.put(number, info);
+                Log.d(TAG, "Contact info missing: " + number);
                 enqueueRequest(number, c.getPosition(),
                         callerName, callerNumberType, callerNumberLabel, 0L);
             } else if (info != ContactInfo.EMPTY) { // Has been queried
@@ -655,8 +661,17 @@
                         || info.type != callerNumberType
                         || !TextUtils.equals(info.label, callerNumberLabel)) {
                     // Something is amiss, so sync up.
+                    Log.w(TAG, "Contact info inconsistent: " + number);
                     enqueueRequest(number, c.getPosition(),
                             callerName, callerNumberType, callerNumberLabel, info.photoId);
+                } else if (cachedInfo.isExpired()) {
+                    Log.d(TAG, "Contact info expired: " + number);
+                    // Put it back in the cache, therefore marking it as not expired, so that other
+                    // entries with the same number will not re-request it.
+                    mContactInfoCache.put(number, info);
+                    // The contact info is no longer up to date, we should request it.
+                    enqueueRequest(number, c.getPosition(), info.name, info.type, info.label,
+                            info.photoId);
                 }
 
                 // Format and cache phone number for found contact
@@ -809,10 +824,10 @@
 
     @Override
     public void onResume() {
-        // The adapter caches looked up numbers, clear it so they will get
-        // looked up again.
+        // Mark all entries in the contact info cache as out of date, so they will be looked up
+        // again once being shown.
         if (mAdapter != null) {
-            mAdapter.clearCache();
+            mAdapter.invalidateCache();
         }
 
         startQuery();
@@ -1032,7 +1047,7 @@
     private String getBetterNumberFromContacts(String number) {
         String matchingNumber = null;
         // Look in the cache first. If it's not found then query the Phones db
-        ContactInfo ci = mAdapter.mContactInfo.get(number);
+        ContactInfo ci = mAdapter.mContactInfoCache.getPossiblyExpired(number);
         if (ci != null && ci != ContactInfo.EMPTY) {
             matchingNumber = ci.number;
         } else {
diff --git a/src/com/android/contacts/util/ExpirableCache.java b/src/com/android/contacts/util/ExpirableCache.java
new file mode 100644
index 0000000..0ee3bbe
--- /dev/null
+++ b/src/com/android/contacts/util/ExpirableCache.java
@@ -0,0 +1,263 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * 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.android.contacts.util;
+
+import android.util.LruCache;
+
+import java.util.concurrent.atomic.AtomicInteger;
+
+import javax.annotation.concurrent.Immutable;
+import javax.annotation.concurrent.ThreadSafe;
+
+/**
+ * An LRU cache in which all items can be marked as expired at a given time and it is possible to
+ * query whether a particular cached value is expired or not.
+ * <p>
+ * A typical use case for this is caching of values which are expensive to compute but which are
+ * still useful when out of date.
+ * <p>
+ * Consider a cache for contact information:
+ * <pre>{@code
+ *     private ExpirableCache<String, Contact> mContactCache;}</pre>
+ * which stores the contact information for a given phone number.
+ * <p>
+ * When we need to store contact information for a given phone number, we can look up the info in
+ * the cache:
+ * <pre>{@code
+ *     CachedValue<Contact> cachedContact = mContactCache.getCachedValue(phoneNumber);
+ * }</pre>
+ * We might also want to fetch the contact information again if the item is expired.
+ * <pre>
+ *     if (cachedContact.isExpired()) {
+ *         fetchContactForNumber(phoneNumber,
+ *                 new FetchListener() {
+ *                     &#64;Override
+ *                     public void onFetched(Contact contact) {
+ *                         mContactCache.put(phoneNumber, contact);
+ *                     }
+ *                 });
+ *     }</pre>
+ * and insert it back into the cache when the fetch completes.
+ * <p>
+ * At a certain point we want to expire the content of the cache because we know the content may
+ * no longer be up-to-date, for instance, when resuming the activity this is shown into:
+ * <pre>
+ *     &#64;Override
+ *     protected onResume() {
+ *         // We were paused for some time, the cached value might no longer be up to date.
+ *         mContactCache.expireAll();
+ *         super.onResume();
+ *     }
+ * </pre>
+ * The values will be still available from the cache, but they will be expired.
+ * <p>
+ * If interested only in the value itself, not whether it is expired or not, one should use the
+ * {@link #getPossiblyExpired(Object)} method. If interested only in non-expired values, one should
+ * use the {@link #get(Object)} method instead.
+ * <p>
+ * This class wraps around an {@link LruCache} instance: it follows the {@link LruCache} behavior
+ * for evicting items when the cache is full. It is possible to supply your own subclass of LruCache
+ * by using the {@link #create(LruCache)} method, which can define a custom expiration policy.
+ * Since the underlying cache maps keys to cached values it can determine which items are expired
+ * and which are not, allowing for an implementation that evicts expired items before non expired
+ * ones.
+ * <p>
+ * This class is thread-safe.
+ *
+ * @param <K> the type of the keys
+ * @param <V> the type of the values
+ */
+@ThreadSafe
+public class ExpirableCache<K, V> {
+    /**
+     * A cached value stored inside the cache.
+     * <p>
+     * It provides access to the value stored in the cache but also allows to check whether the
+     * value is expired.
+     *
+     * @param <V> the type of value stored in the cache
+     */
+    public interface CachedValue<V> {
+        /** Returns the value stored in the cache for a given key. */
+        public V getValue();
+
+        /**
+         * Checks whether the value, while still being present in the cache, is expired.
+         *
+         * @return true if the value is expired
+         */
+        public boolean isExpired();
+    }
+
+    /**
+     * Cached values storing the generation at which they were added.
+     */
+    @Immutable
+    private static class GenerationalCachedValue<V> implements ExpirableCache.CachedValue<V> {
+        /** The value stored in the cache. */
+        public final V mValue;
+        /** The generation at which the value was added to the cache. */
+        private final int mGeneration;
+        /** The atomic integer storing the current generation of the cache it belongs to. */
+        private final AtomicInteger mCacheGeneration;
+
+        /**
+         * @param cacheGeneration the atomic integer storing the generation of the cache in which
+         *        this value will be stored
+         */
+        public GenerationalCachedValue(V value, AtomicInteger cacheGeneration) {
+            mValue = value;
+            mCacheGeneration = cacheGeneration;
+            // Snapshot the current generation.
+            mGeneration = mCacheGeneration.get();
+        }
+
+        @Override
+        public V getValue() {
+            return mValue;
+        }
+
+        @Override
+        public boolean isExpired() {
+            return mGeneration != mCacheGeneration.get();
+        }
+    }
+
+    /** The underlying cache used to stored the cached values. */
+    private LruCache<K, CachedValue<V>> mCache;
+
+    /**
+     * The current generation of items added to the cache.
+     * <p>
+     * Items in the cache can belong to a previous generation, but in that case they would be
+     * expired.
+     *
+     * @see ExpirableCache.CachedValue#isExpired()
+     */
+    private final AtomicInteger mGeneration;
+
+    private ExpirableCache(LruCache<K, CachedValue<V>> cache) {
+        mCache = cache;
+        mGeneration = new AtomicInteger(0);
+    }
+
+    /**
+     * Returns the cached value for the given key, or null if no value exists.
+     * <p>
+     * The cached value gives access both to the value associated with the key and whether it is
+     * expired or not.
+     * <p>
+     * If not interested in whether the value is expired, use {@link #getPossiblyExpired(Object)}
+     * instead.
+     * <p>
+     * If only wants values that are not expired, use {@link #get(Object)} instead.
+     *
+     * @param key the key to look up
+     */
+    public CachedValue<V> getCachedValue(K key) {
+        return mCache.get(key);
+    }
+
+    /**
+     * Returns the value for the given key, or null if no value exists.
+     * <p>
+     * When using this method, it is not possible to determine whether the value is expired or not.
+     * Use {@link #getCachedValue(Object)} to achieve that instead. However, if using
+     * {@link #getCachedValue(Object)} to determine if an item is expired, one should use the item
+     * within the {@link CachedValue} and not call {@link #getPossiblyExpired(Object)} to get the
+     * value afterwards, since that is not guaranteed to return the same value or that the newly
+     * returned value is in the same state.
+     *
+     * @param key the key to look up
+     */
+    public V getPossiblyExpired(K key) {
+        CachedValue<V> cachedValue = getCachedValue(key);
+        return cachedValue == null ? null : cachedValue.getValue();
+    }
+
+    /**
+     * Returns the value for the given key only if it is not expired, or null if no value exists or
+     * is expired.
+     * <p>
+     * This method will return null if either there is no value associated with this key or if the
+     * associated value is expired.
+     *
+     * @param key the key to look up
+     */
+    public V get(K key) {
+        CachedValue<V> cachedValue = getCachedValue(key);
+        return cachedValue == null || cachedValue.isExpired() ? null : cachedValue.getValue();
+    }
+
+    /**
+     * Puts an item in the cache.
+     * <p>
+     * Newly added item will not be expired until {@link #expireAll()} is next called.
+     *
+     * @param key the key to look up
+     * @param value the value to associate with the key
+     */
+    public void put(K key, V value) {
+        mCache.put(key, newCachedValue(value));
+    }
+
+    /**
+     * Mark all items currently in the cache as expired.
+     * <p>
+     * Newly added items after this call will be marked as not expired.
+     * <p>
+     * Expiring the items in the cache does not imply they will be evicted.
+     */
+    public void expireAll() {
+        mGeneration.incrementAndGet();
+    }
+
+    /**
+     * Creates a new {@link CachedValue} instance to be stored in this cache.
+     * <p>
+     * Implementation of {@link LruCache#create(K)} can use this method to create a new entry.
+     */
+    public CachedValue<V> newCachedValue(V value) {
+        return new GenerationalCachedValue<V>(value, mGeneration);
+    }
+
+    /**
+     * Creates a new {@link ExpirableCache} that wraps the given {@link LruCache}.
+     * <p>
+     * The created cache takes ownership of the cache passed in as an argument.
+     *
+     * @param <K> the type of the keys
+     * @param <V> the type of the values
+     * @param cache the cache to store the value in
+     * @return the newly created expirable cache
+     * @throws IllegalArgumentException if the cache is not empty
+     */
+    public static <K, V> ExpirableCache<K, V> create(LruCache<K, CachedValue<V>> cache) {
+        return new ExpirableCache<K, V>(cache);
+    }
+
+    /**
+     * Creates a new {@link ExpirableCache} with the given maximum size.
+     *
+     * @param <K> the type of the keys
+     * @param <V> the type of the values
+     * @return the newly created expirable cache
+     */
+    public static <K, V> ExpirableCache<K, V> create(int maxSize) {
+        return create(new LruCache<K, CachedValue<V>>(maxSize));
+    }
+}
diff --git a/tests/src/com/android/contacts/util/ExpirableCacheTest.java b/tests/src/com/android/contacts/util/ExpirableCacheTest.java
new file mode 100644
index 0000000..309cc0e
--- /dev/null
+++ b/tests/src/com/android/contacts/util/ExpirableCacheTest.java
@@ -0,0 +1,125 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * 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.android.contacts.util;
+
+import com.android.contacts.util.ExpirableCache.CachedValue;
+
+import android.test.AndroidTestCase;
+import android.test.suitebuilder.annotation.SmallTest;
+import android.util.LruCache;
+
+/**
+ * Unit tests for {@link ExpirableCache}.
+ */
+@SmallTest
+public class ExpirableCacheTest extends AndroidTestCase {
+    /** The object under test. */
+    private ExpirableCache<String, Integer> mCache;
+
+    @Override
+    protected void setUp() throws Exception {
+        super.setUp();
+        LruCache<String, CachedValue<Integer>> lruCache =
+            new LruCache<String, ExpirableCache.CachedValue<Integer>>(20);
+        mCache = ExpirableCache.create(lruCache);
+    }
+
+    @Override
+    protected void tearDown() throws Exception {
+        mCache = null;
+        super.tearDown();
+    }
+
+    public void testPut() {
+        mCache.put("a", 1);
+        mCache.put("b", 2);
+        assertEquals(1, mCache.getPossiblyExpired("a").intValue());
+        assertEquals(2, mCache.getPossiblyExpired("b").intValue());
+        mCache.put("a", 3);
+        assertEquals(3, mCache.getPossiblyExpired("a").intValue());
+    }
+
+    public void testGet_NotExisting() {
+        assertNull(mCache.getPossiblyExpired("a"));
+        mCache.put("b", 1);
+        assertNull(mCache.getPossiblyExpired("a"));
+    }
+
+    public void testGet_Expired() {
+        mCache.put("a", 1);
+        assertEquals(1, mCache.getPossiblyExpired("a").intValue());
+        mCache.expireAll();
+        assertEquals(1, mCache.getPossiblyExpired("a").intValue());
+    }
+
+    public void testGetNotExpired_NotExisting() {
+        assertNull(mCache.get("a"));
+        mCache.put("b", 1);
+        assertNull(mCache.get("a"));
+    }
+
+    public void testGetNotExpired_Expired() {
+        mCache.put("a", 1);
+        assertEquals(1, mCache.get("a").intValue());
+        mCache.expireAll();
+        assertNull(mCache.get("a"));
+    }
+
+    public void testGetCachedValue_NotExisting() {
+        assertNull(mCache.getCachedValue("a"));
+        mCache.put("b", 1);
+        assertNull(mCache.getCachedValue("a"));
+    }
+
+    public void testGetCachedValue_Expired() {
+        mCache.put("a", 1);
+        assertFalse("Should not be expired", mCache.getCachedValue("a").isExpired());
+        mCache.expireAll();
+        assertTrue("Should be expired", mCache.getCachedValue("a").isExpired());
+    }
+
+    public void testGetChangedValue_PutAfterExpired() {
+        mCache.put("a", 1);
+        mCache.expireAll();
+        mCache.put("a", 1);
+        assertFalse("Should not be expired", mCache.getCachedValue("a").isExpired());
+    }
+
+    public void testComputingCache() {
+        // Creates a cache in which all unknown values default to zero.
+        mCache = ExpirableCache.create(
+                new LruCache<String, ExpirableCache.CachedValue<Integer>>(10) {
+                    @Override
+                    protected CachedValue<Integer> create(String key) {
+                        return mCache.newCachedValue(0);
+                    }
+                });
+
+        // The first time we request a new value, we add it to the cache.
+        CachedValue<Integer> cachedValue = mCache.getCachedValue("a");
+        assertNotNull("Should have been created implicitly", cachedValue);
+        assertEquals(0, cachedValue.getValue().intValue());
+        assertFalse("Should not be expired", cachedValue.isExpired());
+
+        // If we expire all the values, the implicitly created value will also be marked as expired.
+        mCache.expireAll();
+        CachedValue<Integer> expiredCachedValue = mCache.getCachedValue("a");
+        assertNotNull("Should have been created implicitly", expiredCachedValue);
+        assertEquals(0, expiredCachedValue.getValue().intValue());
+        assertTrue("Should be expired", expiredCachedValue.isExpired());
+    }
+}