blob: ed77c152675f3c55f2413a24ff65faac3c044a7c [file] [log] [blame]
// Copyright (C) 2019 The Android Open Source Project
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#pragma once
#include <android-base/logging.h>
#include <stdint.h>
#include <optional>
#include <vector>
namespace android {
namespace snapshot {
class DmSnapCowSizeCalculator {
public:
DmSnapCowSizeCalculator(unsigned int sector_bytes, unsigned int chunk_sectors)
: sector_bytes_(sector_bytes),
chunk_sectors_(chunk_sectors),
exceptions_per_chunk(chunk_sectors_ * sector_bytes_ / exception_size_bytes) {}
void WriteByte(uint64_t address) { WriteSector(address / sector_bytes_); }
void WriteSector(uint64_t sector) { WriteChunk(sector / chunk_sectors_); }
void WriteChunk(uint64_t chunk_id) {
if (!valid_) {
return;
}
if (modified_chunks_.size() <= chunk_id) {
if (modified_chunks_.max_size() <= chunk_id) {
LOG(ERROR) << "Invalid COW size, chunk_id is too large.";
valid_ = false;
return;
}
modified_chunks_.resize(chunk_id + 1, false);
if (modified_chunks_.size() <= chunk_id) {
LOG(ERROR) << "Invalid COW size, chunk_id is too large.";
valid_ = false;
return;
}
}
modified_chunks_[chunk_id] = true;
}
std::optional<uint64_t> cow_size_bytes() const {
auto sectors = cow_size_sectors();
if (!sectors) {
return std::nullopt;
}
return sectors.value() * sector_bytes_;
}
std::optional<uint64_t> cow_size_sectors() const {
auto chunks = cow_size_chunks();
if (!chunks) {
return std::nullopt;
}
return chunks.value() * chunk_sectors_;
}
/*
* The COW device has a precise internal structure as follows:
*
* - header (1 chunk)
* - #0 map and chunks
* - map (1 chunk)
* - chunks addressable by previous map (exceptions_per_chunk)
* - #1 map and chunks
* - map (1 chunk)
* - chunks addressable by previous map (exceptions_per_chunk)
* ...
* - #n: map and chunks
* - map (1 chunk)
* - chunks addressable by previous map (exceptions_per_chunk)
* - 1 extra chunk
*/
std::optional<uint64_t> cow_size_chunks() const {
if (!valid_) {
LOG(ERROR) << "Invalid COW size.";
return std::nullopt;
}
uint64_t modified_chunks_count = 0;
uint64_t cow_chunks = 0;
for (const auto& c : modified_chunks_) {
if (c) {
++modified_chunks_count;
}
}
/* disk header + padding = 1 chunk */
cow_chunks += 1;
/* snapshot modified chunks */
cow_chunks += modified_chunks_count;
/* snapshot chunks index metadata */
cow_chunks += 1 + modified_chunks_count / exceptions_per_chunk;
return cow_chunks;
}
private:
/*
* Size of each sector in bytes.
*/
const uint64_t sector_bytes_;
/*
* Size of each chunk in sectors.
*/
const uint64_t chunk_sectors_;
/*
* The COW device stores tables to map the modified chunks. Each table has
* the size of exactly 1 chunk.
* Each entry of the table is called exception and the number of exceptions
* that each table can contain determines the number of data chunks that
* separate two consecutive tables. This value is then fundamental to
* compute the space overhead introduced by the tables in COW devices.
*/
const uint64_t exceptions_per_chunk;
/*
* Each row of the table (called exception in the kernel) contains two
* 64 bit indices to identify the corresponding chunk, and this 128 bit
* pair is constant in size.
*/
static constexpr unsigned int exception_size_bytes = 64 * 2 / 8;
/*
* Validity check for the container.
* It may happen that the caller attempts the write of an invalid chunk
* identifier, and this misbehavior is accounted and stored in this value.
*/
bool valid_ = true;
/*
* |modified_chunks_| is a container that keeps trace of the modified
* chunks.
* Multiple options were considered when choosing the most appropriate data
* structure for this container. Here follows a summary of why vector<bool>
* has been chosen, taking as a reference a snapshot partition of 4 GiB and
* chunk size of 4 KiB.
* - std::set<uint64_t> is very space-efficient for a small number of
* operations, but if the whole snapshot is changed, it would need to
* store
* 4 GiB / 4 KiB * (64 bit / 8) = 8 MiB
* just for the data, plus the additional data overhead for the red-black
* tree used for data sorting (if each rb-tree element stores 3 address
* and the word-aligne color, the total size grows to 32 MiB).
* - std::bitset<N> is not a good fit because requires a priori knowledge,
* at compile time, of the bitset size.
* - std::vector<bool> is a special case of vector, which uses a data
* compression that allows reducing the space utilization of each element
* to 1 bit. In detail, this data structure is composed of a resizable
* array of words, each of them representing a bitmap. On a 64 bit
* device, modifying the whole 4 GiB snapshot grows this container up to
* 4 * GiB / 4 KiB / 64 = 64 KiB
* that, even if is the same space requirement to change a single byte at
* the highest address of the snapshot, is a very affordable space
* requirement.
*/
std::vector<bool> modified_chunks_;
};
} // namespace snapshot
} // namespace android