diff --git a/src/com/android/browser/Controller.java b/src/com/android/browser/Controller.java
index 6c9c440..6541ec0 100644
--- a/src/com/android/browser/Controller.java
+++ b/src/com/android/browser/Controller.java
@@ -997,6 +997,7 @@
 
     @Override
     public void bookmarkedStatusHasChanged(Tab tab) {
+        // TODO: Switch to using onTabDataChanged after b/3262950 is fixed
         mUi.bookmarkedStatusHasChanged(tab);
     }
 
diff --git a/src/com/android/browser/DataController.java b/src/com/android/browser/DataController.java
index be38d70..aa233fd 100644
--- a/src/com/android/browser/DataController.java
+++ b/src/com/android/browser/DataController.java
@@ -22,20 +22,45 @@
 import android.content.ContentValues;
 import android.content.Context;
 import android.database.Cursor;
+import android.database.sqlite.SQLiteException;
 import android.os.Handler;
-import android.os.HandlerThread;
-import android.os.Looper;
 import android.os.Message;
+import android.provider.BrowserContract;
 import android.provider.BrowserContract.History;
+import android.util.Log;
+
+import java.util.concurrent.BlockingQueue;
+import java.util.concurrent.LinkedBlockingQueue;
 
 public class DataController {
+    private static final String LOGTAG = "DataController";
     // Message IDs
     private static final int HISTORY_UPDATE_VISITED = 100;
     private static final int HISTORY_UPDATE_TITLE = 101;
+    public static final int QUERY_URL_IS_BOOKMARK = 200;
     private static DataController sInstance;
 
     private Context mContext;
-    private Handler mHandler;
+    private DataControllerHandler mDataHandler;
+    private Handler mCbHandler; // To respond on the UI thread
+
+    /* package */ static interface OnQueryUrlIsBookmark {
+        void onQueryUrlIsBookmark(String url, boolean isBookmark);
+    }
+    private static class CallbackContainer {
+        Object replyTo;
+        Object[] args;
+    }
+
+    private static class DCMessage {
+        int what;
+        Object obj;
+        Object replyTo;
+        DCMessage(int w, Object o) {
+            what = w;
+            obj = o;
+        }
+    }
 
     /* package */ static DataController getInstance(Context c) {
         if (sInstance == null) {
@@ -46,28 +71,68 @@
 
     private DataController(Context c) {
         mContext = c.getApplicationContext();
-        HandlerThread thread = new HandlerThread("DataController");
-        thread.setDaemon(true);
-        thread.start();
-        mHandler = new DataControllerHandler(thread.getLooper());
+        mDataHandler = new DataControllerHandler();
+        mDataHandler.setDaemon(true);
+        mDataHandler.start();
+        mCbHandler = new Handler() {
+            @Override
+            public void handleMessage(Message msg) {
+                CallbackContainer cc = (CallbackContainer) msg.obj;
+                switch (msg.what) {
+                    case QUERY_URL_IS_BOOKMARK: {
+                        OnQueryUrlIsBookmark cb = (OnQueryUrlIsBookmark) cc.replyTo;
+                        String url = (String) cc.args[0];
+                        boolean isBookmark = (Boolean) cc.args[1];
+                        cb.onQueryUrlIsBookmark(url, isBookmark);
+                        break;
+                    }
+                }
+            }
+        };
     }
 
     public void updateVisitedHistory(String url) {
-        mHandler.obtainMessage(HISTORY_UPDATE_VISITED, url).sendToTarget();
+        mDataHandler.sendMessage(HISTORY_UPDATE_VISITED, url);
     }
 
     public void updateHistoryTitle(String url, String title) {
-        mHandler.obtainMessage(HISTORY_UPDATE_TITLE, new String[] { url, title })
-                .sendToTarget();
+        mDataHandler.sendMessage(HISTORY_UPDATE_TITLE, new String[] { url, title });
     }
 
-    class DataControllerHandler extends Handler {
-        public DataControllerHandler(Looper looper) {
-            super(looper);
-        }
+    public void queryBookmarkStatus(String url, OnQueryUrlIsBookmark replyTo) {
+        mDataHandler.sendMessage(QUERY_URL_IS_BOOKMARK, url, replyTo);
+    }
+
+    // The standard Handler and Message classes don't allow the queue manipulation
+    // we want (such as peeking). So we use our own queue.
+    class DataControllerHandler extends Thread {
+        private BlockingQueue<DCMessage> mMessageQueue
+                = new LinkedBlockingQueue<DCMessage>();
 
         @Override
-        public void handleMessage(Message msg) {
+        public void run() {
+            super.run();
+            while (true) {
+                try {
+                    handleMessage(mMessageQueue.take());
+                } catch (InterruptedException ex) {
+                    break;
+                }
+            }
+        }
+
+        void sendMessage(int what, Object obj) {
+            DCMessage m = new DCMessage(what, obj);
+            mMessageQueue.add(m);
+        }
+
+        void sendMessage(int what, Object obj, Object replyTo) {
+            DCMessage m = new DCMessage(what, obj);
+            m.replyTo = replyTo;
+            mMessageQueue.add(m);
+        }
+
+        private void handleMessage(DCMessage msg) {
             switch (msg.what) {
             case HISTORY_UPDATE_VISITED:
                 doUpdateVisitedHistory((String) msg.obj);
@@ -76,43 +141,73 @@
                 String[] args = (String[]) msg.obj;
                 doUpdateHistoryTitle(args[0], args[1]);
                 break;
+            case QUERY_URL_IS_BOOKMARK:
+                // TODO: Look for identical messages in the queue and remove them
+                // TODO: Also, look for partial matches and merge them (such as
+                //       multiple callbacks querying the same URL)
+                doQueryBookmarkStatus((String) msg.obj, msg.replyTo);
+                break;
             }
         }
-    }
 
-    private void doUpdateVisitedHistory(String url) {
-        ContentResolver cr = mContext.getContentResolver();
-        Cursor c = null;
-        try {
-            c = cr.query(History.CONTENT_URI, new String[] { History._ID, History.VISITS },
-                    History.URL + "=?", new String[] { url }, null);
-            if (c.moveToFirst()) {
-                ContentValues values = new ContentValues();
-                values.put(History.VISITS, c.getInt(1) + 1);
-                values.put(History.DATE_LAST_VISITED, System.currentTimeMillis());
-                cr.update(ContentUris.withAppendedId(History.CONTENT_URI, c.getLong(0)),
-                        values, null, null);
-            } else {
-                android.provider.Browser.truncateHistory(cr);
-                ContentValues values = new ContentValues();
-                values.put(History.URL, url);
-                values.put(History.VISITS, 1);
-                values.put(History.DATE_LAST_VISITED, System.currentTimeMillis());
-                values.put(History.TITLE, url);
-                values.put(History.DATE_CREATED, 0);
-                values.put(History.USER_ENTERED, 0);
-                cr.insert(History.CONTENT_URI, values);
+        private void doUpdateVisitedHistory(String url) {
+            ContentResolver cr = mContext.getContentResolver();
+            Cursor c = null;
+            try {
+                c = cr.query(History.CONTENT_URI, new String[] { History._ID, History.VISITS },
+                        History.URL + "=?", new String[] { url }, null);
+                if (c.moveToFirst()) {
+                    ContentValues values = new ContentValues();
+                    values.put(History.VISITS, c.getInt(1) + 1);
+                    values.put(History.DATE_LAST_VISITED, System.currentTimeMillis());
+                    cr.update(ContentUris.withAppendedId(History.CONTENT_URI, c.getLong(0)),
+                            values, null, null);
+                } else {
+                    android.provider.Browser.truncateHistory(cr);
+                    ContentValues values = new ContentValues();
+                    values.put(History.URL, url);
+                    values.put(History.VISITS, 1);
+                    values.put(History.DATE_LAST_VISITED, System.currentTimeMillis());
+                    values.put(History.TITLE, url);
+                    values.put(History.DATE_CREATED, 0);
+                    values.put(History.USER_ENTERED, 0);
+                    cr.insert(History.CONTENT_URI, values);
+                }
+            } finally {
+                if (c != null) c.close();
             }
-        } finally {
-            if (c != null) c.close();
         }
-    }
 
-    private void doUpdateHistoryTitle(String url, String title) {
-        ContentResolver cr = mContext.getContentResolver();
-        ContentValues values = new ContentValues();
-        values.put(History.TITLE, title);
-        cr.update(History.CONTENT_URI, values, History.URL + "=?",
-                new String[] { url });
+        private void doQueryBookmarkStatus(String url, Object replyTo) {
+            ContentResolver cr = mContext.getContentResolver();
+            // Check to see if the site is bookmarked
+            Cursor cursor = null;
+            boolean isBookmark = false;
+            try {
+                cursor = mContext.getContentResolver().query(
+                        BookmarkUtils.getBookmarksUri(mContext),
+                        new String[] { BrowserContract.Bookmarks.URL },
+                        BrowserContract.Bookmarks.URL + " == ?",
+                        new String[] { url },
+                        null);
+                isBookmark = cursor.moveToFirst();
+            } catch (SQLiteException e) {
+                Log.e(LOGTAG, "Error checking for bookmark: " + e);
+            } finally {
+                if (cursor != null) cursor.close();
+            }
+            CallbackContainer cc = new CallbackContainer();
+            cc.replyTo = replyTo;
+            cc.args = new Object[] { url, isBookmark };
+            mCbHandler.obtainMessage(QUERY_URL_IS_BOOKMARK, cc).sendToTarget();
+        }
+
+        private void doUpdateHistoryTitle(String url, String title) {
+            ContentResolver cr = mContext.getContentResolver();
+            ContentValues values = new ContentValues();
+            values.put(History.TITLE, title);
+            cr.update(History.CONTENT_URI, values, History.URL + "=?",
+                    new String[] { url });
+        }
     }
 }
diff --git a/src/com/android/browser/Tab.java b/src/com/android/browser/Tab.java
index 491c260..c4edda6 100644
--- a/src/com/android/browser/Tab.java
+++ b/src/com/android/browser/Tab.java
@@ -26,17 +26,13 @@
 import android.content.DialogInterface;
 import android.content.DialogInterface.OnCancelListener;
 import android.content.Intent;
-import android.database.Cursor;
-import android.database.sqlite.SQLiteException;
 import android.graphics.Bitmap;
 import android.graphics.BitmapFactory;
 import android.net.Uri;
 import android.net.http.SslError;
-import android.os.AsyncTask;
 import android.os.Bundle;
 import android.os.Message;
 import android.os.SystemClock;
-import android.provider.BrowserContract;
 import android.speech.RecognizerResultsIntent;
 import android.util.Log;
 import android.view.KeyEvent;
@@ -132,6 +128,7 @@
     private final DownloadListener mDownloadListener;
     // Listener used to know when we move forward or back in the history list.
     private final WebBackForwardListClient mWebBackForwardListClient;
+    private DataController mDataController;
 
     // AsyncTask for downloading touch icons
     DownloadTouchIcon mTouchIconLoader;
@@ -142,6 +139,7 @@
         String mTitle;
         LockIcon mLockIcon;
         Bitmap mFavicon;
+        Boolean mIsBookmarkedSite = false;
 
         PageState(Context c, boolean incognito) {
             if (incognito) {
@@ -183,14 +181,6 @@
     // The current/loading page's state
     private PageState mCurrentState;
 
-    // Whether or not the currently shown page is a bookmarked site.  Will be
-    // out of date when loading a new page until the mBookmarkAsyncTask returns.
-    private boolean mIsBookmarkedSite;
-    // Used to determine whether the current site is bookmarked.
-    private AsyncTask<Void, Void, Boolean> mBookmarkAsyncTask;
-
-    public boolean isBookmarkedSite() { return mIsBookmarkedSite; }
-
     // Used for saving and restoring each Tab
     // TODO: Figure out who uses what and where
     //       Some of these aren't use in this class, and some are only used in
@@ -544,7 +534,7 @@
             // finally update the UI in the activity if it is in the foreground
             mWebViewController.onPageStarted(Tab.this, view, url, favicon);
 
-            updateBookmarkedStatusForUrl(url);
+            updateBookmarkedStatus();
         }
 
         @Override
@@ -1260,11 +1250,11 @@
         mActivity = mWebViewController.getActivity();
         mCloseOnExit = closeOnExit;
         mAppId = appId;
+        mDataController = DataController.getInstance(mActivity);
         mCurrentState = new PageState(mActivity, w.isPrivateBrowsingEnabled());
         mInPageLoad = false;
         mInForeground = false;
 
-
         mDownloadListener = new DownloadListener() {
             public void onDownloadStart(String url, String userAgent,
                     String contentDisposition, String mimetype,
@@ -1595,6 +1585,9 @@
         return mCurrentState.mFavicon;
     }
 
+    public boolean isBookmarkedSite() {
+        return mCurrentState.mIsBookmarkedSite;
+    }
 
     /**
      * Return the tab's error console. Creates the console if createIfNEcessary
@@ -1729,53 +1722,17 @@
     }
 
     public void updateBookmarkedStatus() {
-        if (mMainView == null) {
-            return;
-        }
-        String url = mMainView.getUrl();
-        if (url == null) {
-            return;
-        }
-        updateBookmarkedStatusForUrl(url);
+        mDataController.queryBookmarkStatus(getUrl(), mIsBookmarkCallback);
     }
 
-    /**
-     * Update mIsBookmarkedSite, using urlInQuestion to compare.
-     * @param urlInQuestion URL of the current page, to be checked in the
-     *          bookmarks database.
-     */
-    private void updateBookmarkedStatusForUrl(final String urlInQuestion) {
-        if (mBookmarkAsyncTask != null) {
-            mBookmarkAsyncTask.cancel(true);
+    private DataController.OnQueryUrlIsBookmark mIsBookmarkCallback
+            = new DataController.OnQueryUrlIsBookmark() {
+        @Override
+        public void onQueryUrlIsBookmark(String url, boolean isBookmark) {
+            if (mCurrentState.mUrl.equals(url)) {
+                mCurrentState.mIsBookmarkedSite = isBookmark;
+                mWebViewController.bookmarkedStatusHasChanged(Tab.this);
+            }
         }
-        mBookmarkAsyncTask = new AsyncTask<Void, Void, Boolean>() {
-            @Override
-            protected Boolean doInBackground(Void... unused) {
-                // Check to see if the site is bookmarked
-                Cursor cursor = null;
-                try {
-                    cursor = mActivity.getContentResolver().query(
-                            BrowserContract.Bookmarks.CONTENT_URI,
-                            new String[] { BrowserContract.Bookmarks.URL },
-                            BrowserContract.Bookmarks.URL + " == ?",
-                            new String[] { urlInQuestion },
-                            null);
-                    return cursor.moveToFirst();
-                } catch (SQLiteException e) {
-                    Log.e(LOGTAG, "Error checking for bookmark: " + e);
-                    return false;
-                } finally {
-                    if (cursor != null) cursor.close();
-                }
-            }
-            @Override
-            protected void onPostExecute(Boolean isBookmarked) {
-                if (this == mBookmarkAsyncTask) {
-                    mIsBookmarkedSite = isBookmarked;
-                    mWebViewController.bookmarkedStatusHasChanged(Tab.this);
-                }
-            }
-        };
-        mBookmarkAsyncTask.execute();
-    }
+    };
 }