diff --git a/delta_performer.cc b/delta_performer.cc
index 3f549cd..c299d79 100644
--- a/delta_performer.cc
+++ b/delta_performer.cc
@@ -39,6 +39,10 @@
 const uint64_t DeltaPerformer::kDeltaManifestSizeSize = 8;
 const char DeltaPerformer::kUpdatePayloadPublicKeyPath[] =
     "/usr/share/update_engine/update-payload-key.pub.pem";
+const unsigned DeltaPerformer::kProgressLogMaxChunks = 10;
+const unsigned DeltaPerformer::kProgressLogTimeoutSeconds = 30;
+const unsigned DeltaPerformer::kProgressDownloadWeight = 50;
+const unsigned DeltaPerformer::kProgressOperationsWeight = 50;
 
 namespace {
 const int kUpdateStateOperationInvalid = -1;
@@ -114,6 +118,103 @@
 
 }  // namespace {}
 
+
+// Computes the ratio of |part| and |total|, scaled to |norm|, using integer
+// arithmetic.
+static uint64_t IntRatio(uint64_t part, uint64_t total, uint64_t norm) {
+  return part * norm / total;
+}
+
+void DeltaPerformer::LogProgress(const char* message_prefix) {
+  // Format operations total count and percentage.
+  string total_operations_str("?");
+  string completed_percentage_str("");
+  if (num_total_operations_) {
+    total_operations_str = StringPrintf("%zu", num_total_operations_);
+    // Upcasting to 64-bit to avoid overflow, back to size_t for formatting.
+    completed_percentage_str =
+        StringPrintf(" (%llu%%)",
+                     IntRatio(next_operation_num_, num_total_operations_,
+                              100));
+  }
+
+  // Format download total count and percentage.
+  size_t payload_size = install_plan_->payload_size;
+  string payload_size_str("?");
+  string downloaded_percentage_str("");
+  if (payload_size) {
+    payload_size_str = StringPrintf("%zu", payload_size);
+    // Upcasting to 64-bit to avoid overflow, back to size_t for formatting.
+    downloaded_percentage_str =
+        StringPrintf(" (%llu%%)",
+                     IntRatio(total_bytes_received_, payload_size, 100));
+  }
+
+  LOG(INFO) << (message_prefix ? message_prefix : "") << next_operation_num_
+            << "/" << total_operations_str << " operations"
+            << completed_percentage_str << ", " << total_bytes_received_
+            << "/" << payload_size_str << " bytes downloaded"
+            << downloaded_percentage_str << ", overall progress "
+            << overall_progress_ << "%";
+}
+
+void DeltaPerformer::UpdateOverallProgress(bool force_log,
+                                           const char* message_prefix) {
+  // Compute our download and overall progress.
+  unsigned new_overall_progress = 0;
+  COMPILE_ASSERT(kProgressDownloadWeight + kProgressOperationsWeight == 100,
+                 progress_weight_dont_add_up);
+  // Only consider download progress if its total size is known; otherwise
+  // adjust the operations weight to compensate for the absence of download
+  // progress. Also, make sure to cap the download portion at
+  // kProgressDownloadWeight, in case we end up downloading more than we
+  // initially expected (this indicates a problem, but could generally happen).
+  // TODO(garnold) the correction of operations weight when we do not have the
+  // total payload size, as well as the conditional guard below, should both be
+  // eliminated once we ensure that the payload_size in the install plan is
+  // always given and is non-zero. This currently isn't the case during unit
+  // tests (see chromium-os:37969).
+  size_t payload_size = install_plan_->payload_size;
+  unsigned actual_operations_weight = kProgressOperationsWeight;
+  if (payload_size)
+    new_overall_progress += min(
+        static_cast<unsigned>(IntRatio(total_bytes_received_, payload_size,
+                                       kProgressDownloadWeight)),
+        kProgressDownloadWeight);
+  else
+    actual_operations_weight += kProgressDownloadWeight;
+
+  // Only add completed operations if their total number is known; we definitely
+  // expect an update to have at least one operation, so the expectation is that
+  // this will eventually reach |actual_operations_weight|.
+  if (num_total_operations_)
+    new_overall_progress += IntRatio(next_operation_num_, num_total_operations_,
+                                     actual_operations_weight);
+
+  // Progress ratio cannot recede, unless our assumptions about the total
+  // payload size, total number of operations, or the monotonicity of progress
+  // is breached.
+  if (new_overall_progress < overall_progress_) {
+    LOG(WARNING) << "progress counter receded from " << overall_progress_
+                 << "% down to " << new_overall_progress << "%; this is a bug";
+    force_log = true;
+  }
+  overall_progress_ = new_overall_progress;
+
+  // Update chunk index, log as needed: if forced by called, or we completed a
+  // progress chunk, or a timeout has expired.
+  base::Time curr_time = base::Time::Now();
+  unsigned curr_progress_chunk =
+      overall_progress_ * kProgressLogMaxChunks / 100;
+  if (force_log || curr_progress_chunk > last_progress_chunk_ ||
+      curr_time > forced_progress_log_time_) {
+    forced_progress_log_time_ = curr_time + forced_progress_log_wait_;
+    LogProgress(message_prefix);
+  }
+  last_progress_chunk_ = curr_progress_chunk;
+}
+
+
 // Returns true if |op| is idempotent -- i.e., if we can interrupt it and repeat
 // it safely. Returns false otherwise.
 bool DeltaPerformer::IsIdempotentOperation(
@@ -316,6 +417,11 @@
   const char* c_bytes = reinterpret_cast<const char*>(bytes);
   buffer_.insert(buffer_.end(), c_bytes, c_bytes + count);
   system_state_->payload_state()->DownloadProgress(count);
+
+  // Update the total byte downloaded count and the progress logs.
+  total_bytes_received_ += count;
+  UpdateOverallProgress(false, "Completed ");
+
   if (!manifest_valid_) {
     MetadataParseResult result = ParsePayloadMetadata(buffer_,
                                                       &manifest_,
@@ -341,24 +447,29 @@
       LOG(ERROR) << "Unable to prime the update state.";
       return false;
     }
+
+    num_rootfs_operations_ = manifest_.install_operations_size();
+    num_total_operations_ =
+        num_rootfs_operations_ + manifest_.kernel_install_operations_size();
+    if (next_operation_num_ > 0)
+      UpdateOverallProgress(true, "Resuming after ");
+    LOG(INFO) << "Starting to apply update payload operations";
   }
-  ssize_t total_operations = manifest_.install_operations_size() +
-      manifest_.kernel_install_operations_size();
-  while (next_operation_num_ < total_operations) {
+
+  while (next_operation_num_ < num_total_operations_) {
+    const bool is_kernel_partition =
+        (next_operation_num_ >= num_rootfs_operations_);
     const DeltaArchiveManifest_InstallOperation &op =
-        next_operation_num_ < manifest_.install_operations_size() ?
-        manifest_.install_operations(next_operation_num_) :
+        is_kernel_partition ?
         manifest_.kernel_install_operations(
-            next_operation_num_ - manifest_.install_operations_size());
+            next_operation_num_ - num_rootfs_operations_) :
+        manifest_.install_operations(next_operation_num_);
     if (!CanPerformInstallOperation(op)) {
       // This means we don't have enough bytes received yet to carry out the
       // next operation.
       return true;
     }
 
-    bool should_log = (next_operation_num_ % 1000 == 0 ||
-                       next_operation_num_ == total_operations - 1);
-
     // Validate the operation only if the metadata signature is present.
     // Otherwise, keep the old behavior. This serves as a knob to disable
     // the validation logic in case we find some regression after rollout.
@@ -369,7 +480,7 @@
       // Note: Validate must be called only if CanPerformInstallOperation is
       // called. Otherwise, we might be failing operations before even if there
       // isn't sufficient data to compute the proper hash.
-      *error = ValidateOperationHash(op, should_log);
+      *error = ValidateOperationHash(op);
       if (*error != kActionCodeSuccess) {
         if (install_plan_->hash_checks_mandatory) {
           LOG(ERROR) << "Mandatory operation hash check failed";
@@ -387,12 +498,6 @@
     ScopedTerminatorExitUnblocker exit_unblocker =
         ScopedTerminatorExitUnblocker();  // Avoids a compiler unused var bug.
     // Log every thousandth operation, and also the first and last ones
-    if (should_log) {
-      LOG(INFO) << "Performing operation " << (next_operation_num_ + 1) << "/"
-                << total_operations;
-    }
-    bool is_kernel_partition =
-        (next_operation_num_ >= manifest_.install_operations_size());
     if (op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
         op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
       if (!PerformReplaceOperation(op, is_kernel_partition)) {
@@ -416,7 +521,9 @@
         return false;
       }
     }
+
     next_operation_num_++;
+    UpdateOverallProgress(false, "Completed ");
     CheckpointUpdateProgress();
   }
   return true;
@@ -754,8 +861,7 @@
 }
 
 ActionExitCode DeltaPerformer::ValidateOperationHash(
-    const DeltaArchiveManifest_InstallOperation& operation,
-    bool should_log) {
+    const DeltaArchiveManifest_InstallOperation& operation) {
 
   if (!operation.data_sha256_hash().size()) {
     if (!operation.data_length()) {
@@ -818,9 +924,6 @@
     return kActionCodeDownloadOperationHashMismatch;
   }
 
-  if (should_log)
-    LOG(INFO) << "Validated operation " << next_operation_num_ + 1;
-
   return kActionCodeSuccess;
 }
 
@@ -1107,6 +1210,10 @@
                         manifest_metadata_size > 0);
   manifest_metadata_size_ = manifest_metadata_size;
 
+  // Advance the download progress to reflect what doesn't need to be
+  // re-downloaded.
+  total_bytes_received_ += buffer_offset_;
+
   // Speculatively count the resume as a failure.
   int64_t resumed_update_failures;
   if (prefs_->GetInt64(kPrefsResumedUpdateFailures, &resumed_update_failures)) {
diff --git a/delta_performer.h b/delta_performer.h
index 2010765..8370b81 100644
--- a/delta_performer.h
+++ b/delta_performer.h
@@ -9,6 +9,7 @@
 
 #include <vector>
 
+#include <base/time.h>
 #include <google/protobuf/repeated_field.h>
 #include <gtest/gtest_prod.h>  // for FRIEND_TEST
 
@@ -37,6 +38,19 @@
   static const uint64_t kDeltaManifestSizeSize;
   static const char kUpdatePayloadPublicKeyPath[];
 
+  // Defines the granularity of progress logging in terms of how many "completed
+  // chunks" we want to report at the most.
+  static const unsigned kProgressLogMaxChunks;
+  // Defines a timeout since the last progress was logged after which we want to
+  // force another log message (even if the current chunk was not completed).
+  static const unsigned kProgressLogTimeoutSeconds;
+  // These define the relative weights (0-100) we give to the different work
+  // components associated with an update when computing an overall progress.
+  // Currently they include the download progress and the number of completed
+  // operations. They must add up to one hundred (100).
+  static const unsigned kProgressDownloadWeight;
+  static const unsigned kProgressOperationsWeight;
+
   DeltaPerformer(PrefsInterface* prefs,
                  SystemState* system_state,
                  InstallPlan* install_plan)
@@ -51,7 +65,14 @@
         buffer_offset_(0),
         last_updated_buffer_offset_(kuint64max),
         block_size_(0),
-        public_key_path_(kUpdatePayloadPublicKeyPath) {}
+        public_key_path_(kUpdatePayloadPublicKeyPath),
+        total_bytes_received_(0),
+        num_rootfs_operations_(0),
+        num_total_operations_(0),
+        overall_progress_(0),
+        last_progress_chunk_(0),
+        forced_progress_log_wait_(
+            base::TimeDelta::FromSeconds(kProgressLogTimeoutSeconds)) {}
 
   // Opens the kernel. Should be called before or after Open(), but before
   // Write(). The kernel file will be close()d when Close() is called.
@@ -152,6 +173,12 @@
   friend class DeltaPerformerTest;
   FRIEND_TEST(DeltaPerformerTest, IsIdempotentOperationTest);
 
+  // Logs the progress of downloading/applying an update.
+  void LogProgress(const char* message_prefix);
+
+  // Update overall progress metrics, log as necessary.
+  void UpdateOverallProgress(bool force_log, const char* message_prefix);
+
   static bool IsIdempotentOperation(
       const DeltaArchiveManifest_InstallOperation& op);
 
@@ -170,7 +197,7 @@
   // matches what's specified in the manifest in the payload.
   // Returns kActionCodeSuccess on match or a suitable error code otherwise.
   ActionExitCode ValidateOperationHash(
-      const DeltaArchiveManifest_InstallOperation& operation, bool should_log);
+      const DeltaArchiveManifest_InstallOperation& operation);
 
   // Interprets the given |protobuf| as a DeltaArchiveManifest protocol buffer
   // of the given protobuf_length and verifies that the signed hash of the
@@ -242,7 +269,7 @@
   uint64_t manifest_metadata_size_;
 
   // Index of the next operation to perform in the manifest.
-  int next_operation_num_;
+  size_t next_operation_num_;
 
   // buffer_ is a window of the data that's been downloaded. At first,
   // it contains the beginning of the download, but after the protobuf
@@ -271,6 +298,25 @@
   // override with test keys.
   std::string public_key_path_;
 
+  // The number of bytes received so far, used for progress tracking.
+  size_t total_bytes_received_;
+
+  // The number rootfs and total operations in a payload, once we know them.
+  size_t num_rootfs_operations_;
+  size_t num_total_operations_;
+
+  // An overall progress counter, which should reflect both download progress
+  // and the ratio of applied operations. Range is 0-100.
+  unsigned overall_progress_;
+
+  // The last progress chunk recorded.
+  unsigned last_progress_chunk_;
+
+  // The timeout after which we should force emitting a progress log (constant),
+  // and the actual point in time for the next forced log to be emitted.
+  const base::TimeDelta forced_progress_log_wait_;
+  base::Time forced_progress_log_time_;
+
   DISALLOW_COPY_AND_ASSIGN(DeltaPerformer);
 };