f2fs_reader/
nat.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4use crate::superblock::{BLOCKS_PER_SEGMENT, BLOCK_SIZE, SEGMENT_SIZE};
5use anyhow::{ensure, Error};
6use std::collections::HashMap;
7use zerocopy::{FromBytes, Immutable, IntoBytes, KnownLayout, Unaligned};
8
9/// A mapping from logical node ID to block address.
10#[repr(C, packed)]
11#[derive(Copy, Clone, Default, Debug, Immutable, Unaligned, KnownLayout, FromBytes, IntoBytes)]
12pub struct RawNatEntry {
13    pub version: u8,
14    pub ino: u32,
15    pub block_addr: u32,
16}
17
18/// The number of NAT entries that fit in a single (4kb) block.
19pub const NAT_ENTRY_PER_BLOCK: usize = BLOCK_SIZE / std::mem::size_of::<RawNatEntry>(); // 455
20
21/// The "Node Address Table" provides a mapping from logical node ID to physical block address.
22/// It boils down to an A/B segment and a bitmap (from the checkpoint) to select which to use.
23/// The `nat_journal` is an additional small mapping of NAT updates that haven't yet been flushed.
24pub struct Nat {
25    /// Byte offset of NAT from start of device.
26    device_offset: usize,
27    /// There are two possible NAT locations for a given entry.
28    /// These are in segment 2*n and 2*n+1.
29    /// The bitmap tells us which one is valid.
30    nat_bitmap: Vec<u8>,
31    /// Copied from the summary block of the 'HotData' segment.
32    /// This contains recent changes that trump what is on disk.
33    pub nat_journal: HashMap<u32, RawNatEntry>,
34}
35
36impl Nat {
37    pub fn new(
38        nat_blkaddr: u32,
39        nat_bitmap: Vec<u8>,
40        nat_journal: HashMap<u32, RawNatEntry>,
41    ) -> Self {
42        let device_offset = nat_blkaddr as usize * BLOCK_SIZE;
43        Self { device_offset, nat_bitmap, nat_journal }
44    }
45
46    /// Returns the offset of the block containing 'nid'
47    pub fn get_nat_block_for_entry(&self, nid: u32) -> Result<u32, Error> {
48        // 9 bytes per entry so 455 entries per 4kB block.
49        let nat_block_ix = nid as usize / NAT_ENTRY_PER_BLOCK;
50        // Alternating pairs of segments are use to hold NAT entries based on nat_bitmap.
51        let segment_offset = nat_block_ix / BLOCKS_PER_SEGMENT * SEGMENT_SIZE * 2;
52        // If bitmap bit is true, we read from odd segment, otherwise even.
53        ensure!(
54            nat_block_ix / 8 < self.nat_bitmap.len(),
55            "Got request for nid {nid} which is beyond the bitmap size of {}",
56            self.nat_bitmap.len()
57        );
58        let bitmap_offset =
59            if (self.nat_bitmap[nat_block_ix / 8] << (nat_block_ix % 8)) & 0x80 == 0x80 {
60                SEGMENT_SIZE
61            } else {
62                0
63            };
64        let byte_offset = self.device_offset
65            + segment_offset
66            + (nat_block_ix % BLOCKS_PER_SEGMENT) * BLOCK_SIZE
67            + bitmap_offset;
68        Ok((byte_offset / BLOCK_SIZE) as u32)
69    }
70
71    /// Returns the offset within the block containing 'nid'.
72    pub fn get_nat_block_offset_for_entry(&self, nid: u32) -> usize {
73        (nid as usize % NAT_ENTRY_PER_BLOCK) * std::mem::size_of::<RawNatEntry>()
74    }
75}
76
77#[repr(C, packed)]
78#[derive(Copy, Clone, Debug, Immutable, KnownLayout, FromBytes, IntoBytes, Unaligned)]
79pub struct Summary {
80    pub nid: u32,
81    pub version: u8,
82    pub ofs_in_node: u16,
83}
84
85#[repr(C, packed)]
86#[derive(Copy, Clone, Debug, Immutable, KnownLayout, FromBytes, IntoBytes, Unaligned)]
87pub struct SummaryFooter {
88    pub entry_type: u8,
89    pub check_sum: u32,
90}
91
92#[repr(C, packed)]
93#[derive(Copy, Clone, Debug, Immutable, KnownLayout, FromBytes, IntoBytes, Unaligned)]
94pub struct NatJournalEntry {
95    pub ino: u32,
96    pub entry: RawNatEntry,
97}
98
99const SUM_ENTRY_SIZE: usize = std::mem::size_of::<Summary>() * 512;
100const N_NATS_SIZE: usize = 2;
101const NAT_JOURNAL_SIZE: usize =
102    BLOCK_SIZE - SUM_ENTRY_SIZE - N_NATS_SIZE - std::mem::size_of::<SummaryFooter>();
103#[repr(C, packed)]
104#[derive(Copy, Clone, Debug, Immutable, KnownLayout, FromBytes, IntoBytes, Unaligned)]
105pub struct NatJournal {
106    pub entries: [NatJournalEntry; NAT_JOURNAL_SIZE / std::mem::size_of::<NatJournalEntry>()],
107    _reserved: [u8; NAT_JOURNAL_SIZE % std::mem::size_of::<NatJournalEntry>()],
108}
109
110/// SummaryBlock contains additional NAT entries to apply.
111#[repr(C, packed)]
112#[derive(Copy, Clone, Debug, Immutable, KnownLayout, FromBytes, IntoBytes, Unaligned)]
113pub struct SummaryBlock {
114    pub entries: [Summary; 512],
115    pub n_nats: u16,
116    pub nat_journal: NatJournal,
117    pub footer: SummaryFooter,
118}
f2fs_reader/nat.rs

f2fs_reader/
nat.rs
