rankings.cc | Explore in Territory

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

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

#include "net/disk_cache/blockfile/rankings.h"

#include <stdint.h>

#include <limits>
#include <memory>

#include "base/memory/raw_ptr.h"
#include "base/process/process.h"
#include "base/time/time.h"
#include "build/build_config.h"
#include "net/base/net_export.h"
#include "net/disk_cache/blockfile/backend_impl.h"
#include "net/disk_cache/blockfile/disk_format.h"
#include "net/disk_cache/blockfile/entry_impl.h"
#include "net/disk_cache/blockfile/errors.h"
#include "net/disk_cache/blockfile/stress_support.h"

#if BUILDFLAG(IS_WIN)
#include <windows.h>
#endif

Time;
TimeTicks;

namespace disk_cache {
// This is used by crash_cache.exe to generate unit test files.
NET_EXPORT_PRIVATE RankCrashes g_rankings_crash = …;
}

namespace {

enum Operation { … };

// This class provides a simple lock for the LRU list of rankings. Whenever an
// entry is to be inserted or removed from the list, a transaction object should
// be created to keep track of the operation. If the process crashes before
// finishing the operation, the transaction record (stored as part of the user
// data on the file header) can be used to finish the operation.
class Transaction { … };

Transaction::Transaction(volatile disk_cache::LruData* data,
                         disk_cache::Addr addr, Operation op, int list)
    : … { … }

Transaction::~Transaction() { … }

// Code locations that can generate crashes.
enum CrashLocation { … };

// Simulates a crash (by exiting the process without graceful shutdown) on debug
// builds, according to the value of g_rankings_crash. This used by
// crash_cache.exe to generate unit-test files.
void GenerateCrash(CrashLocation location) { … }

// Update the timestamp fields of |node|.
void UpdateTimes(disk_cache::CacheRankingsBlock* node, bool modified) { … }

}  // namespace

namespace disk_cache {

Rankings::ScopedRankingsBlock::ScopedRankingsBlock() : … { … }

Rankings::ScopedRankingsBlock::ScopedRankingsBlock(Rankings* rankings)
    : … { … }

Rankings::ScopedRankingsBlock::ScopedRankingsBlock(Rankings* rankings,
                                                   CacheRankingsBlock* node)
    : … { … }

Rankings::Iterator::Iterator() = default;

void Rankings::Iterator::Reset() { … }

Rankings::Rankings() = default;

Rankings::~Rankings() = default;

bool Rankings::Init(BackendImpl* backend, bool count_lists) { … }

void Rankings::Reset() { … }

void Rankings::Insert(CacheRankingsBlock* node, bool modified, List list) { … }

// If a, b and r are elements on the list, and we want to remove r, the possible
// states for the objects if a crash happens are (where y(x, z) means for object
// y, prev is x and next is z):
// A. One element:
//    1. r(r, r), head(r), tail(r)                    initial state
//    2. r(r, r), head(0), tail(r)                    WriteHead()
//    3. r(r, r), head(0), tail(0)                    WriteTail()
//    4. r(0, 0), head(0), tail(0)                    next.Store()
//
// B. Remove a random element:
//    1. a(x, r), r(a, b), b(r, y), head(x), tail(y)  initial state
//    2. a(x, r), r(a, b), b(a, y), head(x), tail(y)  next.Store()
//    3. a(x, b), r(a, b), b(a, y), head(x), tail(y)  prev.Store()
//    4. a(x, b), r(0, 0), b(a, y), head(x), tail(y)  node.Store()
//
// C. Remove head:
//    1. r(r, b), b(r, y), head(r), tail(y)           initial state
//    2. r(r, b), b(r, y), head(b), tail(y)           WriteHead()
//    3. r(r, b), b(b, y), head(b), tail(y)           next.Store()
//    4. r(0, 0), b(b, y), head(b), tail(y)           prev.Store()
//
// D. Remove tail:
//    1. a(x, r), r(a, r), head(x), tail(r)           initial state
//    2. a(x, r), r(a, r), head(x), tail(a)           WriteTail()
//    3. a(x, a), r(a, r), head(x), tail(a)           prev.Store()
//    4. a(x, a), r(0, 0), head(x), tail(a)           next.Store()
void Rankings::Remove(CacheRankingsBlock* node, List list, bool strict) { … }

// A crash in between Remove and Insert will lead to a dirty entry not on the
// list. We want to avoid that case as much as we can (as while waiting for IO),
// but the net effect is just an assert on debug when attempting to remove the
// entry. Otherwise we'll need reentrant transactions, which is an overkill.
void Rankings::UpdateRank(CacheRankingsBlock* node, bool modified, List list) { … }

CacheRankingsBlock* Rankings::GetNext(CacheRankingsBlock* node, List list) { … }

CacheRankingsBlock* Rankings::GetPrev(CacheRankingsBlock* node, List list) { … }

void Rankings::FreeRankingsBlock(CacheRankingsBlock* node) { … }

void Rankings::TrackRankingsBlock(CacheRankingsBlock* node,
                                  bool start_tracking) { … }

int Rankings::SelfCheck() { … }

bool Rankings::SanityCheck(CacheRankingsBlock* node, bool from_list) const { … }

bool Rankings::DataSanityCheck(CacheRankingsBlock* node, bool from_list) const { … }

void Rankings::SetContents(CacheRankingsBlock* node, CacheAddr address) { … }

void Rankings::ReadHeads() { … }

void Rankings::ReadTails() { … }

void Rankings::WriteHead(List list) { … }

void Rankings::WriteTail(List list) { … }

bool Rankings::GetRanking(CacheRankingsBlock* rankings) { … }

void Rankings::ConvertToLongLived(CacheRankingsBlock* rankings) { … }

void Rankings::CompleteTransaction() { … }

void Rankings::FinishInsert(CacheRankingsBlock* node) { … }

void Rankings::RevertRemove(CacheRankingsBlock* node) { … }

bool Rankings::CheckLinks(CacheRankingsBlock* node, CacheRankingsBlock* prev,
                          CacheRankingsBlock* next, List* list) { … }

bool Rankings::CheckSingleLink(CacheRankingsBlock* prev,
                               CacheRankingsBlock* next) { … }

int Rankings::CheckList(List list) { … }

// Note that the returned error codes assume a forward walk (from head to tail)
// so they have to be adjusted accordingly by the caller. We use two stop values
// to be able to detect a corrupt node at the end that is not linked going back.
int Rankings::CheckListSection(List list, Addr end1, Addr end2, bool forward,
                               Addr* last, Addr* second_last, int* num_items) { … }

bool Rankings::IsHead(CacheAddr addr, List* list) const { … }

bool Rankings::IsTail(CacheAddr addr, List* list) const { … }

// We expect to have just a few iterators at any given time, maybe two or three,
// But we could have more than one pointing at the same mode. We walk the list
// of cache iterators and update all that are pointing to the given node.
void Rankings::UpdateIterators(CacheRankingsBlock* node) { … }

void Rankings::UpdateIteratorsForRemoved(CacheAddr address,
                                         CacheRankingsBlock* next) { … }

void Rankings::IncrementCounter(List list) { … }

void Rankings::DecrementCounter(List list) { … }

}  // namespace disk_cache
chromium/net/disk_cache/blockfile/rankings.cc
