diff --git a/constants.cc b/constants.cc
index 35ff835..d724564 100644
--- a/constants.cc
+++ b/constants.cc
@@ -23,18 +23,16 @@
 
 const char kPowerwashCommand[] = "safe fast keepimg reason=update_engine\n";
 
-const char kPowerwashSafePrefsDir[] =
-    "/mnt/stateful_partition/unencrypted/preserve/update_engine/prefs";
+const char kPowerwashSafePrefsSubDirectory[] = "update_engine/prefs";
 
-const char kPrefsDirectory[] = "/var/lib/update_engine/prefs";
+const char kPrefsSubDirectory[] = "prefs";
 
 const char kStatefulPartition[] = "/mnt/stateful_partition";
 
-const char kSystemRebootedMarkerFile[] = "/tmp/update_engine_update_recorded";
-
 // Constants defining keys for the persisted state of update engine.
 const char kPrefsAttemptInProgress[] = "attempt-in-progress";
 const char kPrefsBackoffExpiryTime[] = "backoff-expiry-time";
+const char kPrefsBootId[] = "boot-id";
 const char kPrefsCertificateReportToSendDownload[] =
     "certificate-report-to-send-download";
 const char kPrefsCertificateReportToSendUpdate[] =
diff --git a/constants.h b/constants.h
index c07ff48..211dc96 100644
--- a/constants.h
+++ b/constants.h
@@ -23,17 +23,14 @@
 // completes successfully so that the device is powerwashed on next reboot.
 extern const char kPowerwashMarkerFile[];
 
-// Path to the marker file we use to indicate we've recorded a system reboot.
-extern const char kSystemRebootedMarkerFile[];
-
 // The contents of the powerwash marker file.
 extern const char kPowerwashCommand[];
 
 // Directory for AU prefs that are preserved across powerwash.
-extern const char kPowerwashSafePrefsDir[];
+extern const char kPowerwashSafePrefsSubDirectory[];
 
 // The location where we store the AU preferences (state etc).
-extern const char kPrefsDirectory[];
+extern const char kPrefsSubDirectory[];
 
 // Path to the stateful partition on the root filesystem.
 extern const char kStatefulPartition[];
@@ -41,6 +38,7 @@
 // Constants related to preferences.
 extern const char kPrefsAttemptInProgress[];
 extern const char kPrefsBackoffExpiryTime[];
+extern const char kPrefsBootId[];
 extern const char kPrefsCertificateReportToSendDownload[];
 extern const char kPrefsCertificateReportToSendUpdate[];
 extern const char kPrefsCurrentBytesDownloaded[];
diff --git a/fake_hardware.h b/fake_hardware.h
index 686c1cc..6036a40 100644
--- a/fake_hardware.h
+++ b/fake_hardware.h
@@ -62,6 +62,14 @@
 
   int GetPowerwashCount() const override { return powerwash_count_; }
 
+  bool GetNonVolatileDirectory(base::FilePath* path) const override {
+    return false;
+  }
+
+  bool GetPowerwashSafeDirectory(base::FilePath* path) const override {
+    return false;
+  }
+
   // Setters
   void SetIsOfficialBuild(bool is_official_build) {
     is_official_build_ = is_official_build;
diff --git a/hardware_android.cc b/hardware_android.cc
index 73fef99..6df5cd9 100644
--- a/hardware_android.cc
+++ b/hardware_android.cc
@@ -16,12 +16,20 @@
 
 #include "update_engine/hardware_android.h"
 
+#include <base/files/file_util.h>
 #include <chromeos/make_unique_ptr.h>
 
 #include "update_engine/hardware.h"
 
 using std::string;
 
+namespace {
+
+// The stateful directory used by update_engine.
+const char kNonVolatileDirectory[] = "/data/misc/update_engine";
+
+}  // namespace
+
 namespace chromeos_update_engine {
 
 namespace hardware {
@@ -74,4 +82,19 @@
   return 0;
 }
 
+bool HardwareAndroid::GetNonVolatileDirectory(base::FilePath* path) const {
+  base::FilePath local_path(kNonVolatileDirectory);
+  if (!base::PathExists(local_path)) {
+    LOG(ERROR) << "Non-volatile directory not found: " << local_path.value();
+    return false;
+  }
+  *path = local_path;
+  return true;
+}
+
+bool HardwareAndroid::GetPowerwashSafeDirectory(base::FilePath* path) const {
+  // On Android, we don't have a directory persisted across powerwash.
+  return false;
+}
+
 }  // namespace chromeos_update_engine
diff --git a/hardware_android.h b/hardware_android.h
index 0a341c0..03bc9fc 100644
--- a/hardware_android.h
+++ b/hardware_android.h
@@ -41,6 +41,8 @@
   std::string GetFirmwareVersion() const override;
   std::string GetECVersion() const override;
   int GetPowerwashCount() const override;
+  bool GetNonVolatileDirectory(base::FilePath* path) const override;
+  bool GetPowerwashSafeDirectory(base::FilePath* path) const override;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HardwareAndroid);
diff --git a/hardware_chromeos.cc b/hardware_chromeos.cc
index 888772d..d8c659a 100644
--- a/hardware_chromeos.cc
+++ b/hardware_chromeos.cc
@@ -37,13 +37,21 @@
 
 namespace {
 
-static const char kOOBECompletedMarker[] = "/home/chronos/.oobe_completed";
+const char kOOBECompletedMarker[] = "/home/chronos/.oobe_completed";
+
+// The stateful directory used by update_engine to store powerwash-safe files.
+// The files stored here must be whitelisted in the powerwash scripts.
+const char kPowerwashSafeDirectory[] =
+    "/mnt/stateful_partition/unencrypted/preserve";
 
 // The powerwash_count marker file contains the number of times the device was
 // powerwashed. This value is incremented by the clobber-state script when
 // a powerwash is performed.
-static const char kPowerwashCountMarker[] =
-    "/mnt/stateful_partition/unencrypted/preserve/powerwash_count";
+const char kPowerwashCountMarker[] = "powerwash_count";
+
+// The stateful directory used by update_engine. This directory is wiped during
+// powerwash.
+const char kNonVolatileDirectory[] = "/var/lib/update_engine";
 
 }  // namespace
 
@@ -125,8 +133,10 @@
 
 int HardwareChromeOS::GetPowerwashCount() const {
   int powerwash_count;
+  base::FilePath marker_path = base::FilePath(kPowerwashSafeDirectory).Append(
+      kPowerwashCountMarker);
   string contents;
-  if (!utils::ReadFile(kPowerwashCountMarker, &contents))
+  if (!utils::ReadFile(marker_path.value(), &contents))
     return -1;
   base::TrimWhitespaceASCII(contents, base::TRIM_TRAILING, &contents);
   if (!base::StringToInt(contents, &powerwash_count))
@@ -134,4 +144,14 @@
   return powerwash_count;
 }
 
+bool HardwareChromeOS::GetNonVolatileDirectory(base::FilePath* path) const {
+  *path = base::FilePath(kNonVolatileDirectory);
+  return true;
+}
+
+bool HardwareChromeOS::GetPowerwashSafeDirectory(base::FilePath* path) const {
+  *path = base::FilePath(kPowerwashSafeDirectory);
+  return true;
+}
+
 }  // namespace chromeos_update_engine
diff --git a/hardware_chromeos.h b/hardware_chromeos.h
index 56f5ba8..e7fe486 100644
--- a/hardware_chromeos.h
+++ b/hardware_chromeos.h
@@ -42,6 +42,8 @@
   std::string GetFirmwareVersion() const override;
   std::string GetECVersion() const override;
   int GetPowerwashCount() const override;
+  bool GetNonVolatileDirectory(base::FilePath* path) const override;
+  bool GetPowerwashSafeDirectory(base::FilePath* path) const override;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(HardwareChromeOS);
diff --git a/hardware_interface.h b/hardware_interface.h
index 7dc4e53..df8f227 100644
--- a/hardware_interface.h
+++ b/hardware_interface.h
@@ -20,6 +20,7 @@
 #include <string>
 #include <vector>
 
+#include <base/files/file_path.h>
 #include <base/time/time.h>
 
 namespace chromeos_update_engine {
@@ -60,6 +61,16 @@
   // or is invalid, returns -1. Brand new machines out of the factory or after
   // recovery don't have this value set.
   virtual int GetPowerwashCount() const = 0;
+
+  // Store in |path| the path to a non-volatile directory (persisted across
+  // reboots) available for this daemon. In case of an error, such as no
+  // directory available, returns false.
+  virtual bool GetNonVolatileDirectory(base::FilePath* path) const = 0;
+
+  // Store in |path| the path to a non-volatile directory persisted across
+  // powerwash cycles. In case of an error, such as no directory available,
+  // returns false.
+  virtual bool GetPowerwashSafeDirectory(base::FilePath* path) const = 0;
 };
 
 }  // namespace chromeos_update_engine
diff --git a/mock_hardware.h b/mock_hardware.h
index e082a4f..ff387f4 100644
--- a/mock_hardware.h
+++ b/mock_hardware.h
@@ -51,6 +51,12 @@
     ON_CALL(*this, GetPowerwashCount())
       .WillByDefault(testing::Invoke(&fake_,
             &FakeHardware::GetPowerwashCount));
+    ON_CALL(*this, GetNonVolatileDirectory(testing::_))
+      .WillByDefault(testing::Invoke(&fake_,
+            &FakeHardware::GetNonVolatileDirectory));
+    ON_CALL(*this, GetPowerwashSafeDirectory(testing::_))
+      .WillByDefault(testing::Invoke(&fake_,
+            &FakeHardware::GetPowerwashSafeDirectory));
   }
 
   ~MockHardware() override = default;
@@ -63,6 +69,8 @@
   MOCK_CONST_METHOD0(GetFirmwareVersion, std::string());
   MOCK_CONST_METHOD0(GetECVersion, std::string());
   MOCK_CONST_METHOD0(GetPowerwashCount, int());
+  MOCK_CONST_METHOD1(GetNonVolatileDirectory, bool(base::FilePath*));
+  MOCK_CONST_METHOD1(GetPowerwashSafeDirectory, bool(base::FilePath*));
 
   // Returns a reference to the underlying FakeHardware.
   FakeHardware& fake() {
diff --git a/real_system_state.cc b/real_system_state.cc
index 03cbe2e..34ac5ed 100644
--- a/real_system_state.cc
+++ b/real_system_state.cc
@@ -53,21 +53,44 @@
     return false;
   }
 
-  if (!prefs_.Init(base::FilePath(kPrefsDirectory))) {
+  // Initialize standard and powerwash-safe prefs.
+  base::FilePath non_volatile_path;
+  // TODO(deymo): Fall back to in-memory prefs if there's no physical directory
+  // available.
+  if (!hardware_->GetNonVolatileDirectory(&non_volatile_path)) {
+    LOG(ERROR) << "Failed to get a non-volatile directory.";
+    return false;
+  }
+  Prefs* prefs;
+  prefs_.reset(prefs = new Prefs());
+  if (!prefs->Init(non_volatile_path.Append(kPrefsSubDirectory))) {
     LOG(ERROR) << "Failed to initialize preferences.";
     return false;
   }
 
-  if (!powerwash_safe_prefs_.Init(base::FilePath(kPowerwashSafePrefsDir))) {
+  base::FilePath powerwash_safe_path;
+  if (!hardware_->GetPowerwashSafeDirectory(&powerwash_safe_path)) {
+    // TODO(deymo): Fall-back to in-memory prefs if there's no powerwash-safe
+    // directory, or disable powerwash feature.
+    powerwash_safe_path = non_volatile_path.Append("powerwash-safe");
+    LOG(WARNING) << "No powerwash-safe directory, using non-volatile one.";
+  }
+  powerwash_safe_prefs_.reset(prefs = new Prefs());
+  if (!prefs->Init(
+          powerwash_safe_path.Append(kPowerwashSafePrefsSubDirectory))) {
     LOG(ERROR) << "Failed to initialize powerwash preferences.";
     return false;
   }
 
-  if (!utils::FileExists(kSystemRebootedMarkerFile)) {
-    if (!utils::WriteFile(kSystemRebootedMarkerFile, "", 0)) {
-      LOG(ERROR) << "Could not create reboot marker file";
-      return false;
-    }
+  // Check the system rebooted marker file.
+  std::string boot_id;
+  if (utils::GetBootId(&boot_id)) {
+    std::string prev_boot_id;
+    system_rebooted_ = (!prefs_->GetString(kPrefsBootId, &prev_boot_id) ||
+                        prev_boot_id != boot_id);
+    prefs_->SetString(kPrefsBootId, boot_id);
+  } else {
+    LOG(WARNING) << "Couldn't detect the bootid, assuming system was rebooted.";
     system_rebooted_ = true;
   }
 
diff --git a/real_system_state.h b/real_system_state.h
index 5797d18..fd2a684 100644
--- a/real_system_state.h
+++ b/real_system_state.h
@@ -77,11 +77,11 @@
     return &metrics_lib_;
   }
 
-  inline PrefsInterface* prefs() override { return &prefs_; }
+  inline PrefsInterface* prefs() override { return prefs_.get(); }
 
   inline PrefsInterface* powerwash_safe_prefs() override {
-      return &powerwash_safe_prefs_;
-    }
+    return powerwash_safe_prefs_.get();
+  }
 
   inline PayloadStateInterface* payload_state() override {
     return &payload_state_;
@@ -136,10 +136,10 @@
   MetricsLibrary metrics_lib_;
 
   // Interface for persisted store.
-  Prefs prefs_;
+  std::unique_ptr<PrefsInterface> prefs_;
 
   // Interface for persisted store that persists across powerwashes.
-  Prefs powerwash_safe_prefs_;
+  std::unique_ptr<PrefsInterface> powerwash_safe_prefs_;
 
   // All state pertaining to payload state such as response, URL, backoff
   // states.
diff --git a/utils.cc b/utils.cc
index 2baa087..cf7913c 100644
--- a/utils.cc
+++ b/utils.cc
@@ -85,6 +85,9 @@
 // in GetFileFormat.
 const int kGetFileFormatMaxHeaderSize = 32;
 
+// The path to the kernel's boot_id.
+const char kBootIdPath[] = "/proc/sys/kernel/random/boot_id";
+
 // Return true if |disk_name| is an MTD or a UBI device. Note that this test is
 // simply based on the name of the device.
 bool IsMtdDeviceName(const string& disk_name) {
@@ -1609,6 +1612,13 @@
   return true;
 }
 
+bool GetBootId(string* boot_id) {
+  TEST_AND_RETURN_FALSE(
+      base::ReadFileToString(base::FilePath(kBootIdPath), boot_id));
+  base::TrimWhitespaceASCII(*boot_id, base::TRIM_TRAILING, boot_id);
+  return true;
+}
+
 }  // namespace utils
 
 }  // namespace chromeos_update_engine
diff --git a/utils.h b/utils.h
index 803a0d6..6668c39 100644
--- a/utils.h
+++ b/utils.h
@@ -416,6 +416,11 @@
                  chromeos::Blob* out_data, ssize_t out_data_size,
                  size_t block_size);
 
+// Read the current boot identifier and store it in |boot_id|. This identifier
+// is constants during the same boot of the kernel and is regenerated after
+// reboot. Returns whether it succeeded getting the boot_id.
+bool GetBootId(std::string* boot_id);
+
 }  // namespace utils