diff --git a/src/com/android/browser/AddBookmarkPage.java b/src/com/android/browser/AddBookmarkPage.java
index e827a7e..191659a 100644
--- a/src/com/android/browser/AddBookmarkPage.java
+++ b/src/com/android/browser/AddBookmarkPage.java
@@ -142,7 +142,7 @@
                 setResult(RESULT_OK, (new Intent()).setAction(
                         getIntent().toString()).putExtras(mMap));
             } else {
-                Bookmarks.addBookmark(null, getContentResolver(), url, title);
+                Bookmarks.addBookmark(null, getContentResolver(), url, title, true);
                 setResult(RESULT_OK);
             }
         } catch (IllegalStateException e) {
diff --git a/src/com/android/browser/Bookmarks.java b/src/com/android/browser/Bookmarks.java
index 97e6b20..a3dc919 100644
--- a/src/com/android/browser/Bookmarks.java
+++ b/src/com/android/browser/Bookmarks.java
@@ -47,9 +47,13 @@
      *  @param cr The ContentResolver being used to add the bookmark to the db.
      *  @param url URL of the website to be bookmarked.
      *  @param name Provided name for the bookmark.
+     *  @param retainIcon Whether to retain the page's icon in the icon database.
+     *          This will usually be <code>true</code> except when bookmarks are
+     *          added by a settings restore agent.
      */
     /* package */ static void addBookmark(Context context,
-            ContentResolver cr, String url, String name) {
+            ContentResolver cr, String url, String name,
+            boolean retainIcon) {
         // Want to append to the beginning of the list
         long creationTime = new Date().getTime();
         // First we check to see if the user has already visited this
@@ -137,7 +141,9 @@
                 cr.insert(Browser.BOOKMARKS_URI, map);
             }
         }
-        WebIconDatabase.getInstance().retainIconForPageUrl(url);
+        if (retainIcon) {
+            WebIconDatabase.getInstance().retainIconForPageUrl(url);
+        }
         cursor.deactivate();
         if (context != null) {
             Toast.makeText(context, R.string.added_to_bookmarks,
diff --git a/src/com/android/browser/BrowserBackupAgent.java b/src/com/android/browser/BrowserBackupAgent.java
index 9e10370..c239b12 100644
--- a/src/com/android/browser/BrowserBackupAgent.java
+++ b/src/com/android/browser/BrowserBackupAgent.java
@@ -25,14 +25,16 @@
 import android.os.ParcelFileDescriptor;
 import android.provider.Browser;
 import android.provider.Browser.BookmarkColumns;
+import android.util.Log;
 
+import java.io.ByteArrayOutputStream;
 import java.io.DataInputStream;
 import java.io.DataOutputStream;
 import java.io.EOFException;
 import java.io.File;
 import java.io.FileInputStream;
 import java.io.FileOutputStream;
-
+import java.util.ArrayList;
 import java.util.zip.CRC32;
 
 /**
@@ -40,9 +42,16 @@
  * stored is the set of bookmarks.  It's okay if I/O exceptions are thrown
  * out of the agent; the calling code handles it and the backup operation
  * simply fails.
+ *
+ * @hide
  */
 public class BrowserBackupAgent extends BackupAgent {
+    static final String TAG = "BrowserBookmarkAgent";
+    static final boolean DEBUG = true;
+
     static final String BOOKMARK_KEY = "_bookmarks_";
+    /** this version num MUST be incremented if the flattened-file schema ever changes */
+    static final int BACKUP_AGENT_VERSION = 0;
 
     /**
      * In order to determine whether the bookmark set has changed since the
@@ -51,6 +60,7 @@
      *
      * 1. the size of the flattened bookmark file
      * 2. the CRC32 of that file
+     * 3. the agent version number [relevant following an OTA]
      *
      * After we flatten the bookmarks file here in onBackup, we compare its
      * metrics with the values from the saved state.  If they match, it means
@@ -63,6 +73,7 @@
             ParcelFileDescriptor newState) throws IOException {
         long savedFileSize = -1;
         long savedCrc = -1;
+        int savedVersion = -1;
 
         // Extract the previous bookmark file size & CRC from the saved state
         DataInputStream in = new DataInputStream(
@@ -70,59 +81,28 @@
         try {
             savedFileSize = in.readLong();
             savedCrc = in.readLong();
+            savedVersion = in.readInt();
         } catch (EOFException e) {
             // It means we had no previous state; that's fine
         }
 
-        // TODO: BUILD THE FLATTENED BOOKMARK FILE FROM THE DB (into tmpfile)
-        File tmpfile = getFilesDir().createTempFile("bkp", null);
-        CRC32 crc = new CRC32();
+        // Build a flattened representation of the bookmarks table
+        File tmpfile = File.createTempFile("bkp", null, getCacheDir());
         try {
-            Cursor cursor = getContentResolver().query(Browser.BOOKMARKS_URI,
-                    new String[] { BookmarkColumns.URL, BookmarkColumns.VISITS,
-                    BookmarkColumns.DATE, BookmarkColumns.CREATED,
-                    BookmarkColumns.TITLE },
-                    BookmarkColumns.BOOKMARK + " == 1 ", null, null);
-            int count = cursor.getCount();
-            FileOutputStream out = new FileOutputStream(tmpfile);
-            for (int i = 0; i < count; i++) {
-                StringBuilder sb = new StringBuilder();
-                // URL
-                sb.append("'");
-                sb.append(cursor.getString(0));
-                sb.append("','");
-                // VISITS
-                sb.append(cursor.getInt(1));
-                sb.append("','");
-                // DATE
-                sb.append(cursor.getLong(2));
-                sb.append("','");
-                // CREATED
-                sb.append(cursor.getLong(3));
-                sb.append("','");
-                // TITLE
-                sb.append(cursor.getString(4));
-                sb.append("'");
-                out.write(sb.toString().getBytes());
+            FileOutputStream outfstream = new FileOutputStream(tmpfile);
+            long newCrc = buildBookmarkFile(outfstream);
+            outfstream.close();
 
-                cursor.moveToNext();
-            }
-            out.close();
-            /*
-                    android.util.Log.d("s", "backing up data" +
-                            getContentResolver().openFileDescriptor(Browser.BOOKMARKS_URI, "r").toString());
-             */
-            // NOTE: feed the flattened data through the crc engine on the fly
-            // to save re-reading it later just to checksum it
-
-            // Once the file is built, compare its metrics with the saved ones
-            if ((crc.getValue() != savedCrc) || (tmpfile.length() != savedFileSize)) {
+            // Any changes since the last backup?
+            if ((savedVersion != BACKUP_AGENT_VERSION)
+                    || (newCrc != savedCrc)
+                    || (tmpfile.length() != savedFileSize)) {
                 // Different checksum or different size, so we need to back it up
                 copyFileToBackup(BOOKMARK_KEY, tmpfile, data);
             }
 
-            // Last, record the metrics of the bookmark file that we just stored
-            writeBackupState(tmpfile.length(), crc.getValue(), newState);
+            // Record our backup state and we're done
+            writeBackupState(tmpfile.length(), newCrc, newState);
         } finally {
             // Make sure to tidy up when we're done
             tmpfile.delete();
@@ -138,14 +118,60 @@
     public void onRestore(BackupDataInput data, int appVersionCode,
             ParcelFileDescriptor newState) throws IOException {
         long crc = -1;
-        File tmpfile = getFilesDir().createTempFile("rst", null);
+        File tmpfile = File.createTempFile("rst", null, getFilesDir());
         try {
             while (data.readNextHeader()) {
                 if (BOOKMARK_KEY.equals(data.getKey())) {
                     // Read the flattened bookmark data into a temp file
                     crc = copyBackupToFile(data, tmpfile, data.getDataSize());
 
-                    // TODO: READ THE FLAT BOOKMARKS FILE 'tmpfile' AND REBUILD THE DB TABLE
+                    FileInputStream infstream = new FileInputStream(tmpfile);
+                    DataInputStream in = new DataInputStream(infstream);
+
+                    try {
+                        int count = in.readInt();
+                        ArrayList<Bookmark> bookmarks = new ArrayList<Bookmark>(count);
+
+                        // Read all the bookmarks, then process later -- if we can't read
+                        // all the data successfully, we don't touch the bookmarks table
+                        for (int i = 0; i < count; i++) {
+                            Bookmark mark = new Bookmark();
+                            mark.url = in.readUTF();
+                            mark.visits = in.readInt();
+                            mark.date = in.readLong();
+                            mark.created = in.readLong();
+                            mark.title = in.readUTF();
+                            bookmarks.add(mark);
+                        }
+
+                        // Okay, we have all the bookmarks -- now see if we need to add
+                        // them to the browser's database
+                        int N = bookmarks.size();
+                        if (DEBUG) Log.v(TAG, "Restoring " + N + " bookmarks");
+                        String[] urlCol = new String[] { BookmarkColumns.URL };
+                        for (int i = 0; i < N; i++) {
+                            Bookmark mark = bookmarks.get(i);
+
+                            // Does this URL exist in the bookmark table?
+                            Cursor cursor = getContentResolver().query(Browser.BOOKMARKS_URI,
+                                    urlCol,  BookmarkColumns.URL + " == '" + mark.url + "' AND " +
+                                    BookmarkColumns.BOOKMARK + " == 1 ", null, null);
+                            // if not, insert it
+                            if (cursor.getCount() <= 0) {
+                                Log.v(TAG, "Did not see url: " + mark.url);
+                                // Right now we do not reconstruct the db entry in its
+                                // entirety; we just add a new bookmark with the same data
+                                Bookmarks.addBookmark(null, getContentResolver(),
+                                        mark.url, mark.title, false);
+                            } else {
+                                Log.v(TAG, "Skipping extant url: " + mark.url);
+                            }
+                            cursor.close();
+                        }
+                    } catch (IOException ioe) {
+                        Log.w(TAG, "Bad backup data; not restoring");
+                        crc = -1;
+                    }
                 }
 
                 // Last, write the state we just restored from so we can discern
@@ -158,10 +184,67 @@
         }
     }
 
+    class Bookmark {
+        public String url;
+        public int visits;
+        public long date;
+        public long created;
+        public String title;
+    }
     /*
      * Utility functions
      */
 
+    // Flatten the bookmarks table into the given file, calculating its CRC in the process
+    private long buildBookmarkFile(FileOutputStream outfstream) throws IOException {
+        CRC32 crc = new CRC32();
+        ByteArrayOutputStream bufstream = new ByteArrayOutputStream(512);
+        DataOutputStream bout = new DataOutputStream(bufstream);
+
+        Cursor cursor = getContentResolver().query(Browser.BOOKMARKS_URI,
+                new String[] { BookmarkColumns.URL, BookmarkColumns.VISITS,
+                BookmarkColumns.DATE, BookmarkColumns.CREATED,
+                BookmarkColumns.TITLE },
+                BookmarkColumns.BOOKMARK + " == 1 ", null, null);
+
+        // The first thing in the file is the row count...
+        int count = cursor.getCount();
+        if (DEBUG) Log.v(TAG, "Backing up " + count + " bookmarks");
+        bout.writeInt(count);
+        byte[] record = bufstream.toByteArray();
+        crc.update(record);
+        outfstream.write(record);
+
+        // ... followed by the data for each row
+        for (int i = 0; i < count; i++) {
+            cursor.moveToNext();
+
+            String url = cursor.getString(0);
+            int visits = cursor.getInt(1);
+            long date = cursor.getLong(2);
+            long created = cursor.getLong(3);
+            String title = cursor.getString(4);
+
+            // construct the flattened record in a byte array
+            bufstream.reset();
+            bout.writeUTF(url);
+            bout.writeInt(visits);
+            bout.writeLong(date);
+            bout.writeLong(created);
+            bout.writeUTF(title);
+
+            // Update the CRC and write the record to the temp file
+            record = bufstream.toByteArray();
+            crc.update(record);
+            outfstream.write(record);
+
+            if (DEBUG) Log.v(TAG, "   wrote url " + url);
+        }
+
+        cursor.close();
+        return crc.getValue();
+    }
+
     // Write the file to backup as a single record under the given key
     private void copyFileToBackup(String key, File file, BackupDataOutput data)
             throws IOException {
@@ -187,13 +270,16 @@
         final int CHUNK = 8192;
         byte[] buf = new byte[CHUNK];
         CRC32 crc = new CRC32();
+        FileOutputStream out = new FileOutputStream(file);
 
         while (toRead > 0) {
             int numRead = data.readEntityData(buf, 0, CHUNK);
             crc.update(buf, 0, numRead);
+            out.write(buf, 0, numRead);
             toRead -= numRead;
         }
 
+        out.close();
         return crc.getValue();
     }
 
@@ -204,5 +290,6 @@
                 new FileOutputStream(stateFile.getFileDescriptor()));
         out.writeLong(fileSize);
         out.writeLong(crc);
+        out.writeInt(BACKUP_AGENT_VERSION);
     }
 }
diff --git a/src/com/android/browser/BrowserProvider.java b/src/com/android/browser/BrowserProvider.java
index 29c65e8..b74c9eb 100644
--- a/src/com/android/browser/BrowserProvider.java
+++ b/src/com/android/browser/BrowserProvider.java
@@ -19,6 +19,7 @@
 import com.google.android.providers.GoogleSettings.Partner;
 
 import android.app.SearchManager;
+import android.backup.BackupManager;
 import android.content.ComponentName;
 import android.content.ContentProvider;
 import android.content.ContentUris;
@@ -54,6 +55,7 @@
 public class BrowserProvider extends ContentProvider {
 
     private SQLiteOpenHelper mOpenHelper;
+    private BackupManager mBackupManager;
     private static final String sDatabaseName = "browser.db";
     private static final String TAG = "BrowserProvider";
     private static final String ORDER_BY = "visits DESC, date DESC";
@@ -264,6 +266,7 @@
     public boolean onCreate() {
         final Context context = getContext();
         mOpenHelper = new DatabaseHelper(context);
+        mBackupManager = new BackupManager(context);
         // we added "picasa web album" into default bookmarks for version 19.
         // To avoid erasing the bookmark table, we added it explicitly for
         // version 18 and 19 as in the other cases, we will erase the table.
@@ -736,6 +739,7 @@
 
     @Override
     public Uri insert(Uri url, ContentValues initialValues) {
+        boolean isBookmarkTable = false;
         SQLiteDatabase db = mOpenHelper.getWritableDatabase();
 
         int match = URI_MATCHER.match(url);
@@ -749,6 +753,7 @@
                     uri = ContentUris.withAppendedId(Browser.BOOKMARKS_URI,
                             rowID);
                 }
+                isBookmarkTable = true;
                 break;
             }
 
@@ -771,6 +776,11 @@
             throw new IllegalArgumentException("Unknown URL");
         }
         getContext().getContentResolver().notifyChange(uri, null);
+
+        // back up the new bookmark set if we just inserted one
+        if (isBookmarkTable) {
+            mBackupManager.dataChanged();
+        }
         return uri;
     }
 
@@ -783,7 +793,10 @@
             throw new IllegalArgumentException("Unknown URL");
         }
 
-        if (match == URI_MATCH_BOOKMARKS_ID || match == URI_MATCH_SEARCHES_ID) {
+        // need to know whether it's the bookmarks table for a couple fo reasons
+        boolean isBookmarkTable = (match == URI_MATCH_BOOKMARKS_ID);
+
+        if (isBookmarkTable || match == URI_MATCH_SEARCHES_ID) {
             StringBuilder sb = new StringBuilder();
             if (where != null && where.length() > 0) {
                 sb.append("( ");
@@ -797,6 +810,11 @@
 
         int count = db.delete(TABLE_NAMES[match % 10], where, whereArgs);
         getContext().getContentResolver().notifyChange(url, null);
+
+        // back up the new bookmark set if we just deleted one
+        if (isBookmarkTable) {
+            mBackupManager.dataChanged();
+        }
         return count;
     }
 
@@ -810,7 +828,9 @@
             throw new IllegalArgumentException("Unknown URL");
         }
 
-        if (match == URI_MATCH_BOOKMARKS_ID || match == URI_MATCH_SEARCHES_ID) {
+        boolean isBookmarkTable = (match == URI_MATCH_BOOKMARKS_ID);
+
+        if (isBookmarkTable || match == URI_MATCH_SEARCHES_ID) {
             StringBuilder sb = new StringBuilder();
             if (where != null && where.length() > 0) {
                 sb.append("( ");
@@ -824,6 +844,11 @@
 
         int ret = db.update(TABLE_NAMES[match % 10], values, where, whereArgs);
         getContext().getContentResolver().notifyChange(url, null);
+
+        // back up the new bookmark set if we just changed one
+        if (isBookmarkTable) {
+            mBackupManager.dataChanged();
+        }
         return ret;
     }
 
diff --git a/src/com/android/browser/HistoryItem.java b/src/com/android/browser/HistoryItem.java
index b37a3bd..8a994f3 100644
--- a/src/com/android/browser/HistoryItem.java
+++ b/src/com/android/browser/HistoryItem.java
@@ -46,7 +46,7 @@
                     boolean isChecked) {
                 if (isChecked) {
                     Bookmarks.addBookmark(mContext,
-                            mContext.getContentResolver(), mUrl, getName());
+                            mContext.getContentResolver(), mUrl, getName(), true);
                 } else {
                     Bookmarks.removeFromBookmarks(mContext,
                             mContext.getContentResolver(), mUrl);