jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2018-2022, Andreas Kling <kling@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/IntrusiveList.h>
8#include <Kernel/Debug.h>
9#include <Kernel/FileSystem/BlockBasedFileSystem.h>
10#include <Kernel/Process.h>
11
12namespace Kernel {
13
14struct CacheEntry {
15 IntrusiveListNode<CacheEntry> list_node;
16 BlockBasedFileSystem::BlockIndex block_index { 0 };
17 u8* data { nullptr };
18 bool has_data { false };
19};
20
21class DiskCache {
22public:
23 static constexpr size_t EntryCount = 10000;
24 explicit DiskCache(BlockBasedFileSystem& fs, NonnullOwnPtr<KBuffer> cached_block_data, NonnullOwnPtr<KBuffer> entries_buffer)
25 : m_fs(fs)
26 , m_cached_block_data(move(cached_block_data))
27 , m_entries(move(entries_buffer))
28 {
29 for (size_t i = 0; i < EntryCount; ++i) {
30 entries()[i].data = m_cached_block_data->data() + i * m_fs->block_size();
31 m_clean_list.append(entries()[i]);
32 }
33 }
34
35 ~DiskCache() = default;
36
37 bool is_dirty() const { return !m_dirty_list.is_empty(); }
38 bool entry_is_dirty(CacheEntry const& entry) const { return m_dirty_list.contains(entry); }
39
40 void mark_all_clean()
41 {
42 while (auto* entry = m_dirty_list.first())
43 m_clean_list.prepend(*entry);
44 }
45
46 void mark_dirty(CacheEntry& entry)
47 {
48 m_dirty_list.prepend(entry);
49 }
50
51 void mark_clean(CacheEntry& entry)
52 {
53 m_clean_list.prepend(entry);
54 }
55
56 CacheEntry* get(BlockBasedFileSystem::BlockIndex block_index) const
57 {
58 auto it = m_hash.find(block_index);
59 if (it == m_hash.end())
60 return nullptr;
61 auto& entry = const_cast<CacheEntry&>(*it->value);
62 VERIFY(entry.block_index == block_index);
63 return &entry;
64 }
65
66 ErrorOr<CacheEntry*> ensure(BlockBasedFileSystem::BlockIndex block_index) const
67 {
68 if (auto* entry = get(block_index))
69 return entry;
70
71 if (m_clean_list.is_empty()) {
72 // Not a single clean entry! Flush writes and try again.
73 // NOTE: We want to make sure we only call FileBackedFileSystem flush here,
74 // not some FileBackedFileSystem subclass flush!
75 m_fs->flush_writes_impl();
76 return ensure(block_index);
77 }
78
79 VERIFY(m_clean_list.last());
80 auto& new_entry = *m_clean_list.last();
81 m_clean_list.prepend(new_entry);
82
83 m_hash.remove(new_entry.block_index);
84 TRY(m_hash.try_set(block_index, &new_entry));
85
86 new_entry.block_index = block_index;
87 new_entry.has_data = false;
88
89 return &new_entry;
90 }
91
92 CacheEntry const* entries() const { return (CacheEntry const*)m_entries->data(); }
93 CacheEntry* entries() { return (CacheEntry*)m_entries->data(); }
94
95 template<typename Callback>
96 void for_each_dirty_entry(Callback callback)
97 {
98 for (auto& entry : m_dirty_list)
99 callback(entry);
100 }
101
102private:
103 mutable NonnullRefPtr<BlockBasedFileSystem> m_fs;
104 mutable IntrusiveList<&CacheEntry::list_node> m_dirty_list;
105 mutable IntrusiveList<&CacheEntry::list_node> m_clean_list;
106 mutable HashMap<BlockBasedFileSystem::BlockIndex, CacheEntry*> m_hash;
107 NonnullOwnPtr<KBuffer> m_cached_block_data;
108 NonnullOwnPtr<KBuffer> m_entries;
109};
110
111BlockBasedFileSystem::BlockBasedFileSystem(OpenFileDescription& file_description)
112 : FileBackedFileSystem(file_description)
113{
114 VERIFY(file_description.file().is_seekable());
115}
116
117BlockBasedFileSystem::~BlockBasedFileSystem() = default;
118
119void BlockBasedFileSystem::remove_disk_cache_before_last_unmount()
120{
121 VERIFY(m_lock.is_locked());
122 m_cache.with_exclusive([&](auto& cache) {
123 cache.clear();
124 });
125}
126
127ErrorOr<void> BlockBasedFileSystem::initialize_while_locked()
128{
129 VERIFY(m_lock.is_locked());
130 VERIFY(!is_initialized_while_locked());
131 VERIFY(block_size() != 0);
132 auto cached_block_data = TRY(KBuffer::try_create_with_size("BlockBasedFS: Cache blocks"sv, DiskCache::EntryCount * block_size()));
133 auto entries_data = TRY(KBuffer::try_create_with_size("BlockBasedFS: Cache entries"sv, DiskCache::EntryCount * sizeof(CacheEntry)));
134 auto disk_cache = TRY(adopt_nonnull_own_or_enomem(new (nothrow) DiskCache(*this, move(cached_block_data), move(entries_data))));
135
136 m_cache.with_exclusive([&](auto& cache) {
137 cache = move(disk_cache);
138 });
139 return {};
140}
141
142ErrorOr<void> BlockBasedFileSystem::write_block(BlockIndex index, UserOrKernelBuffer const& data, size_t count, u64 offset, bool allow_cache)
143{
144 VERIFY(m_logical_block_size);
145 VERIFY(offset + count <= block_size());
146 dbgln_if(BBFS_DEBUG, "BlockBasedFileSystem::write_block {}, size={}", index, count);
147
148 // NOTE: We copy the `data` to write into a local buffer before taking the cache lock.
149 // This makes sure any page faults caused by accessing the data will occur before
150 // we tie down the cache.
151 auto buffered_data = TRY(ByteBuffer::create_uninitialized(count));
152
153 TRY(data.read(buffered_data.bytes()));
154
155 return m_cache.with_exclusive([&](auto& cache) -> ErrorOr<void> {
156 if (!allow_cache) {
157 flush_specific_block_if_needed(index);
158 u64 base_offset = index.value() * block_size() + offset;
159 auto nwritten = TRY(file_description().write(base_offset, data, count));
160 VERIFY(nwritten == count);
161 return {};
162 }
163
164 auto entry = TRY(cache->ensure(index));
165 if (count < block_size()) {
166 // Fill the cache first.
167 TRY(read_block(index, nullptr, block_size()));
168 }
169 memcpy(entry->data + offset, buffered_data.data(), count);
170
171 cache->mark_dirty(*entry);
172 entry->has_data = true;
173 return {};
174 });
175}
176
177ErrorOr<void> BlockBasedFileSystem::raw_read(BlockIndex index, UserOrKernelBuffer& buffer)
178{
179 auto base_offset = index.value() * m_logical_block_size;
180 auto nread = TRY(file_description().read(buffer, base_offset, m_logical_block_size));
181 VERIFY(nread == m_logical_block_size);
182 return {};
183}
184
185ErrorOr<void> BlockBasedFileSystem::raw_write(BlockIndex index, UserOrKernelBuffer const& buffer)
186{
187 auto base_offset = index.value() * m_logical_block_size;
188 auto nwritten = TRY(file_description().write(base_offset, buffer, m_logical_block_size));
189 VERIFY(nwritten == m_logical_block_size);
190 return {};
191}
192
193ErrorOr<void> BlockBasedFileSystem::raw_read_blocks(BlockIndex index, size_t count, UserOrKernelBuffer& buffer)
194{
195 auto current = buffer;
196 for (auto block = index.value(); block < (index.value() + count); block++) {
197 TRY(raw_read(BlockIndex { block }, current));
198 current = current.offset(logical_block_size());
199 }
200 return {};
201}
202
203ErrorOr<void> BlockBasedFileSystem::raw_write_blocks(BlockIndex index, size_t count, UserOrKernelBuffer const& buffer)
204{
205 auto current = buffer;
206 for (auto block = index.value(); block < (index.value() + count); block++) {
207 TRY(raw_write(block, current));
208 current = current.offset(logical_block_size());
209 }
210 return {};
211}
212
213ErrorOr<void> BlockBasedFileSystem::write_blocks(BlockIndex index, unsigned count, UserOrKernelBuffer const& data, bool allow_cache)
214{
215 VERIFY(m_logical_block_size);
216 dbgln_if(BBFS_DEBUG, "BlockBasedFileSystem::write_blocks {}, count={}", index, count);
217 for (unsigned i = 0; i < count; ++i) {
218 TRY(write_block(BlockIndex { index.value() + i }, data.offset(i * block_size()), block_size(), 0, allow_cache));
219 }
220 return {};
221}
222
223ErrorOr<void> BlockBasedFileSystem::read_block(BlockIndex index, UserOrKernelBuffer* buffer, size_t count, u64 offset, bool allow_cache) const
224{
225 VERIFY(m_logical_block_size);
226 VERIFY(offset + count <= block_size());
227 dbgln_if(BBFS_DEBUG, "BlockBasedFileSystem::read_block {}", index);
228
229 return m_cache.with_exclusive([&](auto& cache) -> ErrorOr<void> {
230 if (!allow_cache) {
231 const_cast<BlockBasedFileSystem*>(this)->flush_specific_block_if_needed(index);
232 u64 base_offset = index.value() * block_size() + offset;
233 auto nread = TRY(file_description().read(*buffer, base_offset, count));
234 VERIFY(nread == count);
235 return {};
236 }
237
238 auto* entry = TRY(cache->ensure(index));
239 if (!entry->has_data) {
240 auto base_offset = index.value() * block_size();
241 auto entry_data_buffer = UserOrKernelBuffer::for_kernel_buffer(entry->data);
242 auto nread = TRY(file_description().read(entry_data_buffer, base_offset, block_size()));
243 VERIFY(nread == block_size());
244 entry->has_data = true;
245 }
246 if (buffer)
247 TRY(buffer->write(entry->data + offset, count));
248 return {};
249 });
250}
251
252ErrorOr<void> BlockBasedFileSystem::read_blocks(BlockIndex index, unsigned count, UserOrKernelBuffer& buffer, bool allow_cache) const
253{
254 VERIFY(m_logical_block_size);
255 if (!count)
256 return EINVAL;
257 if (count == 1)
258 return read_block(index, &buffer, block_size(), 0, allow_cache);
259 auto out = buffer;
260 for (unsigned i = 0; i < count; ++i) {
261 TRY(read_block(BlockIndex { index.value() + i }, &out, block_size(), 0, allow_cache));
262 out = out.offset(block_size());
263 }
264
265 return {};
266}
267
268void BlockBasedFileSystem::flush_specific_block_if_needed(BlockIndex index)
269{
270 m_cache.with_exclusive([&](auto& cache) {
271 if (!cache->is_dirty())
272 return;
273 auto* entry = cache->get(index);
274 if (!entry)
275 return;
276 if (!cache->entry_is_dirty(*entry))
277 return;
278 size_t base_offset = entry->block_index.value() * block_size();
279 auto entry_data_buffer = UserOrKernelBuffer::for_kernel_buffer(entry->data);
280 (void)file_description().write(base_offset, entry_data_buffer, block_size());
281 });
282}
283
284void BlockBasedFileSystem::flush_writes_impl()
285{
286 size_t count = 0;
287 m_cache.with_exclusive([&](auto& cache) {
288 if (!cache->is_dirty())
289 return;
290 cache->for_each_dirty_entry([&](CacheEntry& entry) {
291 auto base_offset = entry.block_index.value() * block_size();
292 auto entry_data_buffer = UserOrKernelBuffer::for_kernel_buffer(entry.data);
293 [[maybe_unused]] auto rc = file_description().write(base_offset, entry_data_buffer, block_size());
294 ++count;
295 });
296 cache->mark_all_clean();
297 dbgln("{}: Flushed {} blocks to disk", class_name(), count);
298 });
299}
300
301void BlockBasedFileSystem::flush_writes()
302{
303 flush_writes_impl();
304}
305
306}