// Copyright 2018 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "third_party/blink/renderer/modules/storage/cached_storage_area.h"

#include <inttypes.h>

#include <algorithm>

#include "base/compiler_specific.h"
#include "base/feature_list.h"
#include "base/functional/callback_helpers.h"
#include "base/memory/scoped_refptr.h"
#include "base/metrics/field_trial_params.h"
#include "base/metrics/histogram_functions.h"
#include "base/numerics/safe_conversions.h"
#include "base/time/time.h"
#include "base/trace_event/memory_dump_manager.h"
#include "third_party/blink/renderer/core/frame/local_dom_window.h"
#include "third_party/blink/renderer/platform/scheduler/public/main_thread.h"
#include "third_party/blink/renderer/platform/weborigin/kurl.h"
#include "third_party/blink/renderer/platform/wtf/functional.h"
#include "third_party/blink/renderer/platform/wtf/text/copy_lchars_from_uchar_source.h"
#include "third_party/blink/renderer/platform/wtf/text/format.h"
#include "third_party/blink/renderer/platform/wtf/text/string_buffer.h"
#include "third_party/blink/renderer/platform/wtf/text/string_utf8_adaptor.h"
#include "third_party/blink/renderer/platform/wtf/text/unicode.h"
#include "third_party/blink/renderer/platform/wtf/text/utf8.h"

namespace blink {

namespace {

// Don't change or reorder any of the values in this enum, as these values
// are serialized on disk.
enum class StorageFormat : uint8_t { UTF16 = 0, Latin1 = 1 };

// Default values used when a StorageAreaSource is null (e.g. browser-initiated
// mutations like clearing browsing data).
constexpr base::Token kNoSourceId;

// Makes a callback which holds onto a paused WebScopedVirtualTimePauser until
// invoked, ensuring virtual time remains paused for the duration of the async
// operation.
base::OnceClosure MakeVirtualTimePauserCallback(
    CachedStorageArea::Source* source) {
  WebScopedVirtualTimePauser virtual_time_pauser =
      source->CreateWebScopedVirtualTimePauser(
          "CachedStorageArea",
          WebScopedVirtualTimePauser::VirtualTaskDuration::kNonInstant);
  virtual_time_pauser.PauseVirtualTime();
  return BindOnce([](WebScopedVirtualTimePauser) {},
                  std::move(virtual_time_pauser));
}

}  // namespace

unsigned CachedStorageArea::GetLength() {
  EnsureLoaded();
  return map_->GetLength();
}

String CachedStorageArea::GetKey(unsigned index) {
  EnsureLoaded();
  return map_->GetKey(index);
}

String CachedStorageArea::GetItem(const String& key) {
  EnsureLoaded();
  return map_->GetItem(key);
}

bool CachedStorageArea::SetItem(const String& key,
                                const String& value,
                                Source* source) {
  DCHECK(areas_->Contains(source));

  // A quick check to reject obviously overbudget items to avoid priming the
  // cache.
  if ((key.length() + value.length()) * 2 >
      mojom::blink::StorageArea::kPerStorageAreaQuota) {
    return false;
  }

  EnsureLoaded();
  String old_value;
  if (!map_->SetItem(key, value, &old_value))
    return false;

  const FormatOption value_format = GetValueFormat();
  std::optional<Vector<uint8_t>> optional_old_value;
  if (!old_value.IsNull() && should_send_old_value_on_mutations_)
    optional_old_value = StringToUint8Vector(old_value, value_format);
  KURL page_url = source->GetPageUrl();
  base::Token source_id = areas_->at(source);

  if (!is_session_storage_for_prerendering_) {
    remote_area_->Put(
        StringToUint8Vector(key, GetKeyFormat()),
        StringToUint8Vector(value, value_format), optional_old_value,
        mojom::blink::StorageAreaSource::New(page_url, source_id),
        base::IgnoreArgs<bool>(MakeVirtualTimePauserCallback(source)));
  }
  if (!IsSessionStorage())
    EnqueuePendingMutation(key, value, old_value, source_id);
  else if (old_value != value)
    EnqueueStorageEvent(key, old_value, value, page_url, source_id);
  return true;
}

void CachedStorageArea::RemoveItem(const String& key, Source* source) {
  DCHECK(areas_->Contains(source));

  EnsureLoaded();
  String old_value;
  if (!map_->RemoveItem(key, &old_value))
    return;

  std::optional<Vector<uint8_t>> optional_old_value;
  if (should_send_old_value_on_mutations_)
    optional_old_value = StringToUint8Vector(old_value, GetValueFormat());
  KURL page_url = source->GetPageUrl();
  base::Token source_id = areas_->at(source);
  if (!is_session_storage_for_prerendering_) {
    remote_area_->Delete(
        StringToUint8Vector(key, GetKeyFormat()), optional_old_value,
        mojom::blink::StorageAreaSource::New(page_url, source_id),
        MakeVirtualTimePauserCallback(source));
  }
  if (!IsSessionStorage())
    EnqueuePendingMutation(key, String(), old_value, source_id);
  else
    EnqueueStorageEvent(key, old_value, String(), page_url, source_id);
}

void CachedStorageArea::Clear(Source* source) {
  DCHECK(areas_->Contains(source));

  mojo::PendingRemote<mojom::blink::StorageAreaObserver> new_observer;
  bool already_empty = false;
  if (IsSessionStorage()) {
    EnsureLoaded();
    already_empty = map_->GetLength() == 0u;
  } else if (!map_) {
    // If this is our first operation on the StorageArea, |map_| is null and
    // |receiver_| is still bound to the initial StorageAreaObserver pipe
    // created upon CachedStorageArea construction. We rebind |receiver_| here
    // with a new pipe whose event sequence will be synchronized against the
    // backend from the exact point at which the impending |DeleteAll()|
    // operation takes place. The first event observed after this will always
    // be a corresponding |AllDeleted()| from |source|.
    DCHECK(pending_mutations_by_source_.empty());
    DCHECK(pending_mutations_by_key_.empty());
    receiver_.reset();
    new_observer = receiver_.BindNewPipeAndPassRemote();
  }

  map_ = std::make_unique<StorageAreaMap>(
      mojom::blink::StorageArea::kPerStorageAreaQuota);

  KURL page_url = source->GetPageUrl();
  base::Token source_id = areas_->at(source);
  if (!is_session_storage_for_prerendering_) {
    remote_area_->DeleteAll(
        mojom::blink::StorageAreaSource::New(page_url, source_id),
        std::move(new_observer), MakeVirtualTimePauserCallback(source));
  }
  if (!IsSessionStorage())
    EnqueuePendingMutation(String(), String(), String(), source_id);
  else if (!already_empty)
    EnqueueStorageEvent(String(), String(), String(), page_url, source_id);
}

base::Token CachedStorageArea::RegisterSource(Source* source) {
  base::Token id = base::Token::CreateRandom();
  areas_->insert(source, id);
  return id;
}

CachedStorageArea::CachedStorageArea(
    AreaType type,
    const BlinkStorageKey& storage_key,
    LocalDOMWindow* local_dom_window,
    StorageNamespace* storage_namespace,
    bool is_session_storage_for_prerendering,
    mojo::PendingRemote<mojom::blink::StorageArea> storage_area)
    : type_(type),
      storage_key_(storage_key),
      storage_namespace_(storage_namespace),
      is_session_storage_for_prerendering_(is_session_storage_for_prerendering),
      areas_(MakeGarbageCollected<
             GCedHeapHashMap<WeakMember<Source>, base::Token>>()) {
  BindStorageArea(std::move(storage_area), local_dom_window);
  base::trace_event::MemoryDumpManager::GetInstance()->RegisterDumpProvider(
      this, "DOMStorage",
      Thread::MainThread()->GetTaskRunner(MainThreadTaskRunnerRestricted()));
}

CachedStorageArea::~CachedStorageArea() {
  base::trace_event::MemoryDumpManager::GetInstance()->UnregisterDumpProvider(
      this);
}

LocalDOMWindow* CachedStorageArea::GetBestCurrentDOMWindow() {
  for (auto key : areas_->Keys()) {
    if (!key->GetDOMWindow()) {
      continue;
    }
    return key->GetDOMWindow();
  }
  return nullptr;
}

void CachedStorageArea::BindStorageArea(
    mojo::PendingRemote<mojom::blink::StorageArea> new_area,
    LocalDOMWindow* local_dom_window) {
  // Some tests may not provide a StorageNamespace.
  DCHECK(!remote_area_);
  if (!local_dom_window)
    local_dom_window = GetBestCurrentDOMWindow();
  if (!local_dom_window) {
    // If there isn't a local_dom_window to bind to, clear out storage areas and
    // mutations. When EnsureLoaded is called it will attempt to re-bind.
    map_ = nullptr;
    pending_mutations_by_key_.clear();
    pending_mutations_by_source_.clear();
    return;
  }

  // Because the storage area is keyed by the BlinkStorageKey it could be
  // reused by other frames in the same agent cluster so we use the
  // associated AgentGroupScheduler's task runner.
  auto task_runner = local_dom_window->GetFrame()
                         ->GetFrameScheduler()
                         ->GetAgentGroupScheduler()
                         ->DefaultTaskRunner();
  if (new_area) {
    remote_area_.Bind(std::move(new_area), task_runner);
  } else if (storage_namespace_) {
    storage_namespace_->BindStorageArea(
        storage_key_, local_dom_window->GetLocalFrameToken(),
        remote_area_.BindNewPipeAndPassReceiver(task_runner));
  } else {
    return;
  }

  receiver_.reset();
  remote_area_->AddObserver(receiver_.BindNewPipeAndPassRemote(task_runner));
}

void CachedStorageArea::ResetConnection(
    mojo::PendingRemote<mojom::blink::StorageArea> new_area) {
  DCHECK(!is_session_storage_for_prerendering_);
  remote_area_.reset();
  BindStorageArea(std::move(new_area));

  // If we had not yet initialized a local cache, there's no synchronization to
  // be done.
  if (!map_)
    return;

  std::unique_ptr<StorageAreaMap> old_map;
  std::swap(map_, old_map);
  pending_mutations_by_key_.clear();
  pending_mutations_by_source_.clear();

  // Fully repopulate the cache from the loaded backend state.
  EnsureLoaded();

  // The data received from the backend may differ from what we had cached
  // previously. How we proceed depends on the type of storage. First we
  // compute the full diff between our old cache and the restored cache.
  struct ValueDelta {
    String previously_cached_value;
    String restored_value;
  };
  HashMap<String, ValueDelta> deltas;
  for (unsigned i = 0; i < map_->GetLength(); ++i) {
    const String key = map_->GetKey(i);
    const String previously_cached_value = old_map->GetItem(key);
    const String restored_value = map_->GetItem(key);
    if (previously_cached_value != restored_value)
      deltas.insert(key, ValueDelta{previously_cached_value, restored_value});
  }

  // Make sure we also get values for keys that weren't stored in the backend.
  for (unsigned i = 0; i < old_map->GetLength(); ++i) {
    const String key = old_map->GetKey(i);
    const String previously_cached_value = old_map->GetItem(key);
    // This key will already be covered if it's also present in the restored
    // cache.
    if (!map_->GetItem(key).IsNull())
      continue;
    deltas.insert(key, ValueDelta{previously_cached_value, String()});
  }

  if (!IsSessionStorage()) {
    // For Local Storage we have no way of knowing whether changes not reflected
    // by the backend were merely dropped, or if they were landed and
    // overwritten by another client. For simplicity we treat them as dropped,
    // use the restored cache without modification, and notify script about any
    // deltas from the previously cached state.
    for (const auto& delta : deltas) {
      EnqueueStorageEvent(delta.key, delta.value.previously_cached_value,
                          delta.value.restored_value, NullUrl(), kNoSourceId);
    }
    return;
  }

  // For Session Storage, we're the source of truth for our own data, so we
  // can simply push any needed updates down to the backend and continue
  // using our previous cache.
  map_ = std::move(old_map);
  for (const auto& delta : deltas) {
    if (delta.value.previously_cached_value.IsNull()) {
      remote_area_->Delete(
          StringToUint8Vector(delta.key, GetKeyFormat()),
          StringToUint8Vector(delta.value.restored_value, GetValueFormat()),
          /*source=*/nullptr, base::DoNothing());
    } else {
      const FormatOption value_format = GetValueFormat();
      remote_area_->Put(
          StringToUint8Vector(delta.key, GetKeyFormat()),
          StringToUint8Vector(delta.value.previously_cached_value,
                              value_format),
          StringToUint8Vector(delta.value.restored_value, value_format),
          /*source=*/nullptr, base::DoNothing());
    }
  }
}

void CachedStorageArea::KeyChanged(
    const Vector<uint8_t>& key,
    const Vector<uint8_t>& new_value,
    const std::optional<Vector<uint8_t>>& old_value,
    mojom::blink::StorageAreaSourcePtr source) {
  DCHECK(!IsSessionStorage());

  const base::Token source_id =
      source ? std::move(source->storage_area_id) : kNoSourceId;
  const KURL source_page_url = source ? std::move(source->page_url) : NullUrl();

  String key_string =
      Uint8VectorToString(key, FormatOption::kLocalStorageDetectFormat);
  String new_value_string =
      Uint8VectorToString(new_value, FormatOption::kLocalStorageDetectFormat);
  String old_value_string;
  if (old_value) {
    old_value_string = Uint8VectorToString(
        *old_value, FormatOption::kLocalStorageDetectFormat);
  }

  std::unique_ptr<PendingMutation> local_mutation =
      PopPendingMutation(source_id);
  if (map_ && !local_mutation)
    MaybeApplyNonLocalMutationForKey(key_string, new_value_string);

  // If we did pop a mutation, it had better be for the same key this event
  // references.
  DCHECK(!local_mutation || local_mutation->key == key_string);

  EnqueueStorageEvent(key_string, old_value_string, new_value_string,
                      source_page_url, source_id);
}

void CachedStorageArea::KeyChangeFailed(
    const Vector<uint8_t>& key,
    mojom::blink::StorageAreaSourcePtr source) {
  DCHECK(!IsSessionStorage());

  const base::Token source_id =
      source ? std::move(source->storage_area_id) : kNoSourceId;
  const KURL source_page_url = source ? std::move(source->page_url) : NullUrl();

  String key_string =
      Uint8VectorToString(key, FormatOption::kLocalStorageDetectFormat);
  std::unique_ptr<PendingMutation> local_mutation =
      PopPendingMutation(source_id);

  // We don't care about failed changes from other clients.
  if (!local_mutation)
    return;

  // If we did pop a mutation, it had better be for the same key this event
  // references.
  DCHECK_EQ(local_mutation->key, key_string);

  // A pending local mutation was rejected by the backend.
  String old_value = local_mutation->old_value;
  auto key_queue_iter = pending_mutations_by_key_.find(key_string);
  if (key_queue_iter == pending_mutations_by_key_.end()) {
    // If this was the only pending local mutation for the key, we simply revert
    // the cache to the stored |old_value|. Note that this may not be the value
    // originally stored before the corresponding |Put()| which enqueued this
    // mutation: see logic below and in |MaybeApplyNonLocalMutationForKey()| for
    // potential updates to the stored |old_value|.
    DCHECK(map_);
    String invalid_cached_value = map_->GetItem(key_string);
    if (old_value.IsNull())
      map_->RemoveItem(key_string, nullptr);
    else
      map_->SetItemIgnoringQuota(key_string, old_value);

    EnqueueStorageEvent(key_string, invalid_cached_value, old_value,
                        source_page_url, source_id);
    return;
  }

  // This was NOT the only pending local mutation for the key, so its failure
  // is irrelevant to the current cache state (i.e. something has already
  // overwritten its local change.) In this case, there's no event to dispatch
  // and no cache update to make. We do however need to propagate the stored
  // |old_value| to the next queued PendingMutation so that *it* can restore the
  // correct value if it fails.
  key_queue_iter->value.front()->old_value = old_value;
}

void CachedStorageArea::KeyDeleted(
    const Vector<uint8_t>& key,
    const std::optional<Vector<uint8_t>>& old_value,
    mojom::blink::StorageAreaSourcePtr source) {
  DCHECK(!IsSessionStorage());

  const base::Token source_id =
      source ? std::move(source->storage_area_id) : kNoSourceId;
  const KURL source_page_url = source ? std::move(source->page_url) : NullUrl();

  String key_string =
      Uint8VectorToString(key, FormatOption::kLocalStorageDetectFormat);
  std::unique_ptr<PendingMutation> local_mutation =
      PopPendingMutation(source_id);

  if (map_ && !local_mutation)
    MaybeApplyNonLocalMutationForKey(key_string, String());

  // If we did pop a mutation, it had better be for the same key this event
  // references.
  DCHECK(!local_mutation || local_mutation->key == key_string);

  if (old_value) {
    EnqueueStorageEvent(
        key_string,
        Uint8VectorToString(*old_value,
                            FormatOption::kLocalStorageDetectFormat),
        String(), source_page_url, source_id);
  }
}

void CachedStorageArea::AllDeleted(bool was_nonempty,
                                   mojom::blink::StorageAreaSourcePtr source) {
  const base::Token source_id =
      source ? std::move(source->storage_area_id) : kNoSourceId;
  const KURL source_page_url = source ? std::move(source->page_url) : NullUrl();

  std::unique_ptr<PendingMutation> local_mutation =
      PopPendingMutation(source_id);

  // Note that if this event was from a local source, we've already cleared the
  // cache when |Clear()| was called so there's nothing to do other than
  // broadcast the StorageEvent (see below). Broadcast was deferred until now in
  // that case because we needed to know whether the StorageArea was actually
  // non-empty prior to the call.
  if (!local_mutation) {
    map_ = std::make_unique<StorageAreaMap>(
        mojom::blink::StorageArea::kPerStorageAreaQuota);

    // Re-apply the most recent local mutations for each key. These must have
    // occurred after the deletion, because we haven't observed events for them
    // yet. Since they would eventually need to be restored by those impending
    // events otherwise, we instead restore them now to avoid observable churn
    // in the storage state.
    for (const auto& key_mutations : pending_mutations_by_key_) {
      DCHECK(!key_mutations.value.empty());
      PendingMutation* const most_recent_mutation = key_mutations.value.back();
      if (!most_recent_mutation->new_value.IsNull()) {
        map_->SetItemIgnoringQuota(key_mutations.key,
                                   most_recent_mutation->new_value);
      }

      // And now the first unacked mutation should revert to an empty value on
      // failure since that's the state in the backend.
      key_mutations.value.front()->old_value = String();
    }
  }

  // If we did pop a mutation, it had better be from a corresponding |Clear()|,
  // i.e. with no key value.
  DCHECK(!local_mutation || local_mutation->key.IsNull());

  if (was_nonempty) {
    EnqueueStorageEvent(String(), String(), String(), source_page_url,
                        source_id);
  }
}

void CachedStorageArea::ShouldSendOldValueOnMutations(bool value) {
  DCHECK(!IsSessionStorage());
  should_send_old_value_on_mutations_ = value;
}

bool CachedStorageArea::OnMemoryDump(
    const base::trace_event::MemoryDumpArgs& args,
    base::trace_event::ProcessMemoryDump* pmd) {
  using base::trace_event::MemoryAllocatorDump;

  String dump_name =
      Format("site_storage/{}/0x{:X}/cache_size",
             IsSessionStorage() ? "session_storage" : "local_storage",
             reinterpret_cast<uintptr_t>(this));
  MemoryAllocatorDump* dump = pmd->CreateAllocatorDump(dump_name.Utf8());
  dump->AddScalar(MemoryAllocatorDump::kNameSize,
                  MemoryAllocatorDump::kUnitsBytes, memory_used());
  pmd->AddSuballocation(dump->guid(), Partitions::kAllocatedObjectPoolName);
  return true;
}

void CachedStorageArea::EnqueuePendingMutation(const String& key,
                                               const String& new_value,
                                               const String& old_value,
                                               const base::Token& source_id) {
  CHECK(!source_id.is_zero());
  // Track this pending mutation until we observe a corresponding event on
  // our StorageAreaObserver interface. As long as this operation is pending,
  // we will effectively ignore other observed mutations on this key. Note that
  // |old_value| may be updated while this PendingMutation sits in queue, if
  // non-local mutations are observed while waiting for this local mutation to
  // be acknowledged. See logic in |MaybeApplyNonLocalMutationForKey()|.
  auto mutation = std::make_unique<PendingMutation>();
  mutation->key = key;
  mutation->new_value = new_value;
  mutation->old_value = old_value;

  // |key| is null for |Clear()| mutation events.
  if (!key.IsNull()) {
    pending_mutations_by_key_.insert(key, Deque<PendingMutation*>())
        .stored_value->value.push_back(mutation.get());
  }
  pending_mutations_by_source_[source_id].push_back(std::move(mutation));
}

std::unique_ptr<CachedStorageArea::PendingMutation>
CachedStorageArea::PopPendingMutation(const base::Token& source_id) {
  auto source_queue_iter = pending_mutations_by_source_.find(source_id);
  if (source_queue_iter == pending_mutations_by_source_.end()) {
    return nullptr;
  }

  OwnedPendingMutationQueue& mutations_for_source = source_queue_iter->second;
  DCHECK(!mutations_for_source.empty());
  std::unique_ptr<PendingMutation> mutation =
      std::move(mutations_for_source.front());
  mutations_for_source.pop_front();
  if (mutations_for_source.empty())
    pending_mutations_by_source_.erase(source_queue_iter);

  // If |key| is non-null, the oldest mutation queued for that key MUST be this
  // mutation, and we remove it as well. If |key| is null, that means |mutation|
  // was a |DeleteAll()| request and there is no corresponding per-key queue
  // entry.
  const String key = mutation->key;
  if (!key.IsNull()) {
    auto key_queue_iter = pending_mutations_by_key_.find(key);
    CHECK(key_queue_iter != pending_mutations_by_key_.end());
    DCHECK_EQ(key_queue_iter->value.front(), mutation.get());
    key_queue_iter->value.pop_front();
    if (key_queue_iter->value.empty())
      pending_mutations_by_key_.erase(key_queue_iter);
  }

  return mutation;
}

void CachedStorageArea::MaybeApplyNonLocalMutationForKey(
    const String& key,
    const String& new_value) {
  DCHECK(map_);
  auto key_queue_iter = pending_mutations_by_key_.find(key);
  if (key_queue_iter == pending_mutations_by_key_.end()) {
    // No pending local mutations, so we can apply this non-local mutation
    // directly to our cache and then we're done.
    if (new_value.IsNull()) {
      map_->RemoveItem(key, nullptr);
    } else {
      // We turn off quota checking here to accommodate the over budget
      // allowance that's provided in the browser process.
      map_->SetItemIgnoringQuota(key, new_value);
    }

    return;
  }

  // We don't want to apply this mutation yet, possibly ever. We need to wait
  // until one or more pending local mutations are acknowledged either
  // successfully or unsuccessfully. For now we stash this non-local mutation in
  // the |old_value| at the front of the key's queue so we don't lose it. If the
  // local mutation eventually fails, we may restore the key to this non-local
  // mutation value.
  key_queue_iter->value.front()->old_value = new_value;
}

// Controls whether we apply an artificial delay to priming the DOMStorage data.
// There are 2 parameters that influence how long the delay is, `factor` and
// `offset`. If the actual time taken is `time_to_prime` then the delay will be
// `time_to_prime * factor + offset`.
BASE_FEATURE(kDomStorageAblation, base::FEATURE_DISABLED_BY_DEFAULT);
BASE_FEATURE_PARAM(double,
                   kDomStorageAblationDelayFactor,
                   &kDomStorageAblation,
                   "factor",
                   0);
const base::FeatureParam<base::TimeDelta> kDomStorageAblationDelayOffset{
    &kDomStorageAblation, "offset", base::Milliseconds(0)};

void CachedStorageArea::EnsureLoaded() {
  if (map_)
    return;
  if (!remote_area_)
    BindStorageArea();

  // There might be something weird happening during the sync call that destroys
  // this object. Keep a reference to either fix or rule out that this is the
  // problem. See https://crbug.com/915577.
  scoped_refptr<CachedStorageArea> keep_alive(this);
  base::TimeTicks before = base::TimeTicks::Now();
  Vector<mojom::blink::KeyValuePtr> data;

  // We had no cached |map_|, which means |receiver_| was bound to the original
  // StorageAreaObserver pipe created upon CachedStorageArea construction. We
  // replace it with a new receiver whose event sequence is synchronized against
  // the result of |GetAll()| for consistency.
  receiver_.reset();
  remote_area_->GetAll(receiver_.BindNewPipeAndPassRemote(), &data);

  // Determine data formats.
  const FormatOption key_format = GetKeyFormat();
  const FormatOption value_format = GetValueFormat();

  map_ = std::make_unique<StorageAreaMap>(
      mojom::blink::StorageArea::kPerStorageAreaQuota);
  for (const auto& item : data) {
    map_->SetItemIgnoringQuota(Uint8VectorToString(item->key, key_format),
                               Uint8VectorToString(item->value, value_format));
  }

  base::TimeDelta time_to_prime = base::TimeTicks::Now() - before;
  base::UmaHistogramTimes("LocalStorage.MojoTimeToPrime", time_to_prime);

  if (base::FeatureList::IsEnabled(kDomStorageAblation)) {
    base::TimeDelta delay =
        time_to_prime * kDomStorageAblationDelayFactor.Get() +
        kDomStorageAblationDelayOffset.Get();
    base::UmaHistogramMediumTimes("LocalStorage.MojoTimeToPrimeAblationDelay",
                                  delay);
    if (delay.is_positive()) {
      base::PlatformThread::Sleep(delay);
    }
  }

  size_t local_storage_size_kb = map_->quota_used() / 1024;
  // Track localStorage size, from 0-6MB. Note that the maximum size should be
  // 10MB, but we add some slop since we want to make sure the max size is
  // always above what we see in practice, since histograms can't change.
  base::UmaHistogramCustomCounts(
      "LocalStorage.MojoSizeInKB",
      base::saturated_cast<base::Histogram::Sample32>(local_storage_size_kb), 1,
      6 * 1024, 50);
  if (local_storage_size_kb < 100) {
    base::UmaHistogramTimes("LocalStorage.MojoTimeToPrimeForUnder100KB",
                            time_to_prime);
  } else if (local_storage_size_kb < 1000) {
    base::UmaHistogramTimes("LocalStorage.MojoTimeToPrimeFor100KBTo1MB",
                            time_to_prime);
  } else {
    base::UmaHistogramTimes("LocalStorage.MojoTimeToPrimeFor1MBTo5MB",
                            time_to_prime);
  }
}

CachedStorageArea::FormatOption CachedStorageArea::GetKeyFormat() const {
  return IsSessionStorage() ? FormatOption::kSessionStorageForceUTF8
                            : FormatOption::kLocalStorageDetectFormat;
}

CachedStorageArea::FormatOption CachedStorageArea::GetValueFormat() const {
  return IsSessionStorage() ? FormatOption::kSessionStorageForceUTF16
                            : FormatOption::kLocalStorageDetectFormat;
}

bool CachedStorageArea::IsSessionStorage() const {
  return type_ == AreaType::kSessionStorage;
}

void CachedStorageArea::EnqueueStorageEvent(const String& key,
                                            const String& old_value,
                                            const String& new_value,
                                            const KURL& url,
                                            const base::Token& source_id) {
  // Ignore key-change events which aren't actually changing the value.
  if (!key.IsNull() && new_value == old_value)
    return;

  HeapVector<Member<Source>, 1> areas_to_remove_;
  for (const auto& area : *areas_) {
    if (area.value != source_id) {
      bool keep = area.key->EnqueueStorageEvent(key, old_value, new_value, url);
      if (!keep)
        areas_to_remove_.push_back(area.key);
    }
  }
  areas_->RemoveAll(areas_to_remove_);
  if (storage_namespace_) {
    storage_namespace_->DidDispatchStorageEvent(storage_key_, key, old_value,
                                                new_value);
  }
}

// static
String CachedStorageArea::Uint8VectorToString(const Vector<uint8_t>& input,
                                              FormatOption format_option) {
  if (input.empty())
    return g_empty_string;
  String result;
  bool corrupt = false;
  switch (format_option) {
    case FormatOption::kSessionStorageForceUTF16: {
      if (input.size() % sizeof(UChar) != 0) {
        corrupt = true;
        break;
      }
      StringBuffer<UChar> buffer(input.size() / sizeof(UChar));
      base::as_writable_bytes(buffer.Span()).copy_from(input);
      result = String::Adopt(buffer);
      break;
    }
    case FormatOption::kSessionStorageForceUTF8: {
      // TODO(mek): When this lived in content it used to do a "lenient"
      // conversion, while this is a strict conversion. Figure out if that
      // difference actually matters in practice.
      result = String::FromUtf8(input);
      if (result.IsNull()) {
        corrupt = true;
        break;
      }
      break;
    }
    case FormatOption::kLocalStorageDetectFormat: {
      auto [format_byte, payload] = base::span(input).split_at<1u>();
      StorageFormat format = static_cast<StorageFormat>(format_byte[0]);
      switch (format) {
        case StorageFormat::UTF16: {
          if (payload.size() % sizeof(UChar) != 0) {
            corrupt = true;
            break;
          }
          StringBuffer<UChar> buffer(
              base::checked_cast<wtf_size_t>(payload.size() / sizeof(UChar)));
          base::as_writable_bytes(buffer.Span()).copy_from(payload);
          result = String::Adopt(buffer);
          break;
        }
        case StorageFormat::Latin1:
          result = String(payload);
          break;
        default:
          corrupt = true;
      }
      break;
    }
  }
  if (corrupt) {
    // TODO(mek): Better error recovery when corrupt (or otherwise invalid) data
    // is detected.
    LOG(ERROR) << "Corrupt data in domstorage";
    return g_empty_string;
  }
  return result;
}

// static
Vector<uint8_t> CachedStorageArea::StringToUint8Vector(
    const String& input,
    FormatOption format_option) {
  switch (format_option) {
    case FormatOption::kSessionStorageForceUTF16: {
      Vector<uint8_t> result(input.length() * sizeof(UChar));
      input.CopyTo(
          UNSAFE_TODO(base::span(reinterpret_cast<UChar*>(result.data()),
                                 input.length())),
          0);
      return result;
    }
    case FormatOption::kSessionStorageForceUTF8: {
      unsigned length = input.length();
      if (input.Is8Bit() && input.ContainsOnlyAsciiOrEmpty()) {
        Vector<uint8_t> result(length);
        base::span(result).copy_from(input.Span8());
        return result;
      }
      // Handle 8 bit case where it's not only ascii.
      if (input.Is8Bit()) {
        // This code is copied from String::Utf8(), except the vector
        // doesn't have a stack-allocated capacity.
        // We do this because there isn't a way to transform the std::string we
        // get from String::Utf8() to a Vector without an extra copy.
        if (length > std::numeric_limits<unsigned>::max() / 3)
          return Vector<uint8_t>();
        Vector<uint8_t> buffer_vector(length * 3);

        unicode::ConversionResult result = unicode::ConvertLatin1ToUtf8(
            input.Span8(), base::span(buffer_vector));
        // (length * 3) should be sufficient for any conversion
        DCHECK_NE(result.status, unicode::kTargetExhausted);
        buffer_vector.Shrink(static_cast<wtf_size_t>(result.converted.size()));
        return buffer_vector;
      }

      // TODO(dmurph): Figure out how to avoid a copy here.
      // TODO(dmurph): Handle invalid UTF16 better. https://crbug.com/873280.
      StringUtf8Adaptor utf8(input, Utf8ConversionMode::kStrictReplacingErrors);
      Vector<uint8_t> result(base::checked_cast<wtf_size_t>(utf8.size()));
      base::span(result).copy_from(base::as_byte_span(utf8));
      return result;
    }
    case FormatOption::kLocalStorageDetectFormat: {
      if (input.ContainsOnlyLatin1OrEmpty()) {
        Vector<uint8_t> result(input.length() + 1);
        auto [format, payload] = base::span(result).split_at<1u>();
        format[0] = static_cast<uint8_t>(StorageFormat::Latin1);
        if (input.Is8Bit()) {
          payload.copy_from(input.Span8());
        } else {
          CopyLCharsFromUCharSource(payload, input.Span16());
        }
        return result;
      }
      DCHECK(!input.Is8Bit());
      Vector<uint8_t> result(
          base::checked_cast<wtf_size_t>(input.CharactersSizeInBytes() + 1));
      auto [format, payload] = base::span(result).split_at<1u>();
      format[0] = static_cast<uint8_t>(StorageFormat::UTF16);
      payload.copy_from(input.RawByteSpan());
      return result;
    }
  }
  NOTREACHED();
}

void CachedStorageArea::EvictCachedData() {
  map_.reset();
}

}  // namespace blink