keos_project5/ffs/mod.rs
1//! # Fast File System (FFS).
2//!
3//! In KeOS, the kernel utilizes multiple layers to implement file operations.
4//! Higher layers provide convenient abstractions such as buffered I/O, while
5//! the lowest layer is responsible for managing
6//! the on-disk layout through the File System.
7//!
8//! ```text
9//! ┌─────────────────────────────┐
10//! │ keos::fs::RegularFile │
11//! │ - Top-level API for File │
12//! └─────────────┬───────────────┘
13//! │
14//! ┌─────────────▼───────────────────┐
15//! │ keos::fs::traits::RegularFile │
16//! │ - Block-based buffer │
17//! │ - Block-level R/W interface │
18//! └─────────────┬───────────────────┘
19//! │
20//! ┌─────────────▼─────────────────────────┐
21//! │ pagecache::overlaying::RegularFile │
22//! │ - Cache-managed file access │
23//! └─────────────┬─────────────────────────┘
24//! │
25//! ┌─────────────▼─────────────────────────┐
26//! │ Filesystem-specific RegularFile │
27//! │ - Primitive block ops on filesystem │
28//! └─────────────┬─────────────────────────┘
29//! │
30//! ┌─────────────▼─────────────────────────┐
31//! │ Inode │
32//! │ - Conduct the disk-level operation │
33//! └───────────────────────────────────────┘
34//! ```
35//!
36//! This project focuses on implementing the File System, the lowest level in
37//! the hierarchy. Here, you will build the abstractions that directly manage
38//! on-disk inodes and blocks, forming the foundation of all higher-level file
39//! operations.
40//!
41//! A **file system** is a fundamental component of any operating system,
42//! responsible for managing how data is stored, organized, and accessed on
43//! persistent storage devices such as hard drives or solid-state drives. It
44//! provides a hierarchical abstraction of files and directories, enabling users
45//! and programs to interact with stored data through well-defined interfaces
46//! while abstracting away low-level hardware details. The file system ensures
47//! data integrity, persistence, and consistency, even in the face of system
48//! crashes or concurrent access.
49//!
50//! While simple file systems may achieve functional correctness, they often
51//! suffer from performance limitations, such as poor spatial locality,
52//! excessive fragmentation, and inefficient handling of metadata. These issues
53//! become increasingly problematic as file systems scale in size and
54//! complexity.
55//!
56//! The **Fast File System (FFS)** was developed to address these
57//! shortcomings. It incorporates layout and allocation strategies aimed at
58//! improving throughput, minimizing seek time, and optimizing disk utilization.
59//! Key features include.
60//!
61//! In this project, you will implement the simplified version of Fast File
62//! System: **No error handling** and **I/O optimizations**.
63//!
64//! ## Overview of the KeOS Fast File System
65//! The following diagram depicts the disk layout of the FFS:
66//! ```text
67//! +────────────────────+
68//! │ Superblock │
69//! +────────────────────+
70//! │ Inode Bitmap │
71//! +────────────────────+
72//! │ Block Bitmap │
73//! Journal ──-+────────────────────+
74//! │ │ JournalSB │
75//! │ +────────────────────+
76//! │ │ TxBegin │
77//! │ │ Journal Block[0] │
78//! │ │ Journal Block[1] │
79//! │ │ ... │
80//! │ │ TxEnd │
81//! └─────── +────────────────────+
82//! │ Inodes │
83//! +────────────────────+
84//! │ Data Blocks │
85//! │ ... │
86//! +────────────────────+
87//! ```
88//! The following list describes each parts of the FFS disk layout:
89//! - **Superblock** – Global filesystem metadata: block size, counts, offsets,
90//! and identifiers.
91//! - **Inode Bitmap** – Tracks which inodes are allocated or free.
92//! - **Block Bitmap** – Tracks which data blocks are allocated or free.
93//! - **Journal** – Transactional log ensuring crash consistency.
94//! - **Inodes** – The inode table storing metadata and block pointers for files
95//! and directories.
96//! - **Data Blocks** – The actual contents of files and directories.
97//!
98//! Now, start with the implementation of [`inode`].
99use crate::lru::LRUCache;
100use access_control::{BlockPointsTo, MetaData, TrackedInode};
101use alloc::{
102 boxed::Box,
103 collections::btree_map::{BTreeMap, Entry},
104 sync::Arc,
105};
106use core::ops::Range;
107use disk_layout::{InodeArray, InodeBitmap, JournalSb};
108use fs_objects::Directory;
109use inode::Inode;
110use journal::{Journal, RunningTransaction};
111use keos::{
112 KernelError,
113 fs::{Disk, FileBlockNumber, InodeNumber},
114 sync::{RwLock, SpinLock},
115};
116use types::LogicalBlockAddress;
117
118pub mod access_control;
119pub mod disk_layout;
120pub mod fs_objects;
121pub mod inode;
122pub mod journal;
123pub mod types;
124
125/// A handle for performing journal I/O operations.
126///
127/// The journal is used to provide crash consistency by recording intended
128/// changes before they are committed to the main file system. This structure
129/// provides an interface for reading from and writing to the journal region
130/// of the disk.
131pub struct JournalIO<'a> {
132 /// A reference to the file system.
133 pub ffs: &'a FastFileSystemInner,
134}
135
136impl JournalIO<'_> {
137 /// Writes a metadata block into the journal.
138 ///
139 /// This function records a 4 KiB block of metadata at the specified
140 /// logical block address (LBA) in the journal. The block is stored
141 /// as part of the write-ahead log, ensuring that metadata updates
142 /// can be safely replayed in case of a crash.
143 pub fn write_metadata_block(
144 &self,
145 lba: LogicalBlockAddress,
146 block: &[u8; 4096],
147 ) -> Result<(), KernelError> {
148 for i in 0..8 {
149 self.ffs.disk.write(
150 lba.into_sector() + i,
151 block[512 * i..512 * (i + 1)].as_array().unwrap(),
152 )?;
153 }
154 Ok(())
155 }
156
157 /// Reads a journal block from the disk.
158 ///
159 /// This function retrieves a 4 KiB block from the journal at the given
160 /// logical block address (LBA) and copies it into the provided buffer.
161 /// It is primarily used during recovery to replay logged operations
162 /// and restore the file system to a consistent state.
163 pub fn read_journal(
164 &self,
165 lba: LogicalBlockAddress,
166 b: &mut [u8; 4096],
167 ) -> Result<(), KernelError> {
168 for i in 0..8 {
169 self.ffs.disk.read(
170 lba.into_sector() + i,
171 b[512 * i..512 * (i + 1)].as_mut_array().unwrap(),
172 )?;
173 }
174
175 Ok(())
176 }
177}
178
179/// Represents the internal structure of a Fast File System (FFS).
180///
181/// This structure encapsulates the core components of the FFS implementation,
182/// including metadata loaded from disk, in-memory caches, and journal state.
183/// It provides the foundational layer for all low-level filesystem operations,
184/// such as reading/writing blocks and accessing inode metadata.
185///
186/// This type is used internally by [`FastFileSystem`] and is not intended
187/// to be accessed directly by external code.
188pub struct FastFileSystemInner {
189 /// The underlying disk device used by the filesystem.
190 pub(crate) disk: Disk,
191
192 /// Total number of blocks available in the filesystem.
193 pub block_count: usize,
194
195 /// Total number of inodes supported by the filesystem.
196 pub inode_count: usize,
197
198 /// Indicate this file system support journaling.
199 pub has_journal: usize,
200
201 /// The expected view of the disk after all journaled changes are
202 /// checkpointed.
203 ///
204 /// This in-memory map reflects the filesystem state after applying
205 /// journaled updates, but may differ from the actual disk contents if a
206 /// crash occurred before checkpointing.
207 pub blocks: SpinLock<LRUCache<LogicalBlockAddress, Arc<SpinLock<[u8; 4096]>>, 512>>,
208
209 /// On-disk superblock structure, wrapped in metadata-aware
210 /// block access.
211 pub sb: BlockPointsTo<disk_layout::SuperBlock>,
212
213 /// In-memory table mapping inode numbers to their live representations.
214 pub inodes: SpinLock<BTreeMap<InodeNumber, Arc<RwLock<Inode>>>>,
215
216 /// The current state of the journal (if present), wrapped in a
217 /// lock to allow mutable access during journal operations.
218 pub journal: Option<SpinLock<Journal>>,
219
220 /// Whether trace the transactions for debugging purpose.
221 pub debug_journal: bool,
222}
223
224impl FastFileSystemInner {
225 /// Constructs a new file system instance from an on-disk superblock.
226 ///
227 /// This function initializes a [`FastFileSystemInner`] by reading the
228 /// provided superblock and setting up access to the underlying disk.
229 pub fn from_raw_sb(
230 sb: BlockPointsTo<disk_layout::SuperBlock>,
231 disk: Disk,
232 debug_journal: bool,
233 disable_journal: bool,
234 ) -> Result<Self, KernelError> {
235 let guard = sb.read();
236 if &guard.magic == b"KeOSFFS\0" {
237 let block_count = guard.block_count as usize;
238 let inode_count = guard.inode_count as usize;
239 let has_journal = guard.has_journal as usize;
240 drop(guard);
241
242 let mut this = FastFileSystemInner {
243 disk,
244 block_count,
245 inode_count,
246 has_journal,
247 blocks: SpinLock::new(LRUCache::new()),
248 sb,
249 inodes: SpinLock::new(BTreeMap::new()),
250 journal: None,
251 debug_journal,
252 };
253
254 if this.has_journal > 0 && !disable_journal {
255 this.journal = Some(SpinLock::new(Journal {
256 sb: JournalSb::from_disk(&this.disk, this.journal().start)?,
257 }));
258 let mut guard = this.journal.as_ref().unwrap().lock();
259 let result = guard.recovery(&this, &JournalIO { ffs: &this });
260 guard.unlock();
261 result?;
262 this.sb.reload(&this.disk)?;
263 }
264
265 println!("[FFS] Mounted with superblock: ");
266 println!(
267 " - Inodes: {:?} / {:?}",
268 this.sb.read().inode_count_inused,
269 this.inode_count
270 );
271 println!(
272 " - Blocks: {:?} / {:?}",
273 this.sb.read().block_count_inused,
274 this.block_count
275 );
276 println!(" - InodeBitmap: {:?}", this.inode_bitmap());
277 println!(" - BlockBitmap: {:?}", this.block_bitmap());
278 println!(" - Journal: {:?}", this.journal());
279 println!(" - InodeArray: {:?}", this.inode());
280 println!(" - DataBlock: {:?} ~", this.data_block_start());
281 Ok(this)
282 } else {
283 Err(KernelError::FilesystemCorrupted("Invalid Superblock Magic"))
284 }
285 }
286
287 /// Returns the range of block address of the inode bitmap.
288 ///
289 /// The inode bitmap is located immediately after the inode table.
290 #[inline]
291 pub fn inode_bitmap(&self) -> Range<LogicalBlockAddress> {
292 let begin = LogicalBlockAddress::new(2).unwrap();
293 begin..begin + self.inode_count.div_ceil(8).div_ceil(0x1000)
294 }
295
296 /// Returns the range of block address of the block bitmap.
297 ///
298 /// The block bitmap follows the inode bitmap.
299 #[inline]
300 pub fn block_bitmap(&self) -> Range<LogicalBlockAddress> {
301 let begin = self.inode_bitmap().end;
302 begin..begin + self.block_count.div_ceil(8).div_ceil(0x1000)
303 }
304
305 /// Returns the range of block address of the journal.
306 ///
307 /// The data block region follows the bitmaps.
308 #[inline]
309 pub fn journal(&self) -> Range<LogicalBlockAddress> {
310 let begin = self.block_bitmap().end;
311 if self.has_journal != 0 {
312 begin
313 ..begin + 1 /* Journal SB */ + 1 /* TxBegin */ + 4095 /* Maximum number of data blocks */ + 1 /* TxEnd */
314 } else {
315 begin..begin
316 }
317 }
318
319 /// Returns the range of the block address of the Inode[] startpoint.
320 ///
321 /// The data block region follows the bitmaps.
322 #[inline]
323 pub fn inode(&self) -> Range<LogicalBlockAddress> {
324 let begin = self.journal().end;
325 begin
326 ..begin
327 + (core::mem::size_of::<disk_layout::Inode>() * self.inode_count).div_ceil(0x1000)
328 }
329
330 /// Returns the starting block address of the data blocks.
331 ///
332 /// The data block region follows the bitmaps and journal.
333 #[inline]
334 pub fn data_block_start(&self) -> LogicalBlockAddress {
335 self.inode().end
336 }
337
338 /// Opens a new running transaction.
339 ///
340 /// This function begins a transaction on the file system, allowing
341 /// multiple operations to be grouped together atomically. Transactions
342 /// ensure crash consistency by recording updates in the journal before
343 /// they are committed to the main file system.
344 pub fn open_transaction(&self, name: &str) -> RunningTransaction<'_> {
345 RunningTransaction::begin(name, self, JournalIO { ffs: self }, self.debug_journal)
346 }
347
348 /// Reads a data block from disk.
349 ///
350 /// This function retrieves the 4 KiB block located at the specified
351 /// logical block address (LBA) from the underlying disk. It is used for
352 /// reading file data on disk.
353 pub fn read_data_block(
354 &self,
355 lba: LogicalBlockAddress,
356 ) -> Result<Box<[u8; 4096]>, KernelError> {
357 assert!(
358 self.data_block_start() <= lba,
359 "[FFS-ERROR] You must cannot directly read the metadata. Use `MetaData::load` or `JournalIO`."
360 );
361 let mut b = Box::new([0u8; 0x1000]);
362 for i in 0..8 {
363 self.disk.read(
364 lba.into_sector() + i,
365 b[512 * i..512 * (i + 1)].as_mut_array().unwrap(),
366 )?;
367 }
368
369 Ok(b)
370 }
371
372 /// Writes a 4 KiB data block to disk.
373 ///
374 /// This function stores the given buffer at the specified logical block
375 /// address (LBA) on the underlying disk. It is typically used for writing
376 /// file contents.
377 pub fn write_data_block(
378 &self,
379 lba: LogicalBlockAddress,
380 b: &[u8; 4096],
381 ) -> Result<(), KernelError> {
382 assert!(
383 self.data_block_start() <= lba,
384 "[FFS-ERROR] You must cannot directly write to the metadata ({lba:?}). Use `MetaData::load` or `JournalIO`.",
385 );
386 for i in 0..8 {
387 self.disk.write(
388 lba.into_sector() + i,
389 b[512 * i..512 * (i + 1)].as_array().unwrap(),
390 )?;
391 }
392
393 Ok(())
394 }
395
396 /// Converts this inode number into the corresponding location in the inode
397 /// bitmap.
398 ///
399 /// # Arguments
400 /// - `fs`: Reference to the file system's internal metadata layout.
401 ///
402 /// # Returns
403 /// - `Some((lba, offset)`: if the inode number is valid, which includes:
404 /// - `lba`: the logical block address of the inode bitmap block that
405 /// contains this inode.
406 /// - `offset`: the bit offset within that bitmap block corresponding to
407 /// this inode.
408 /// - `None`: if the inode number is out of bounds.
409 pub fn get_inode_bitmap_lba_index(
410 &self,
411 ino: InodeNumber,
412 ) -> Option<(LogicalBlockAddress, usize)> {
413 if (ino.into_u32() as usize) < self.inode_count {
414 let index = (ino.into_u32() - 1) as usize;
415
416 Some((self.inode_bitmap().start + index / 0x1000, index % 0x8000))
417 } else {
418 None
419 }
420 }
421
422 /// Converts this inode number into the corresponding location in the inode
423 /// array.
424 ///
425 /// # Returns
426 /// - `Some((lba, offset))`: if the inode number is valid, which includes:
427 /// - `lba`: the logical block address where the containing [`InodeArray`]
428 /// is located.
429 /// - `offset`:the index within that array where this specific inode
430 /// resides.
431 /// - `None`: if the inode number is out of bounds.
432 ///
433 /// [`InodeArray`]: crate::ffs::disk_layout::InodeArray
434 pub fn get_inode_array_lba_index(
435 &self,
436 ino: InodeNumber,
437 ) -> Option<(LogicalBlockAddress, usize)> {
438 if (ino.into_u32() as usize) < self.inode_count {
439 let index = (ino.into_u32() - 1) as usize;
440 let inode_per_block = 0x1000 / core::mem::size_of::<disk_layout::Inode>();
441
442 Some((
443 self.inode().start + index / inode_per_block,
444 index % inode_per_block,
445 ))
446 } else {
447 None
448 }
449 }
450
451 /// Reads a metadata block from disk.
452 ///
453 /// This function retrieves a block at the given logical block address
454 /// and wraps it in a [`SpinLock`] for safe concurrent access. Metadata
455 /// blocks include structures such as inodes, directories, and allocation
456 /// maps that are frequently shared between threads.
457 ///
458 /// THIS IS INTERNAL API. DO NOT USE THIS FUNCTION.
459 #[doc(hidden)]
460 pub fn read_meta(
461 &self,
462 lba: LogicalBlockAddress,
463 ) -> Result<Arc<SpinLock<[u8; 4096]>>, KernelError> {
464 let mut guard = self.blocks.lock();
465 let result = guard
466 .get_or_insert_with(lba, || {
467 let b = Arc::new(SpinLock::new([0; 4096]));
468 {
469 let mut guard = b.lock();
470 for i in 0..8 {
471 self.disk.read(
472 lba.into_sector() + i,
473 guard[512 * i..512 * (i + 1)].as_mut_array().unwrap(),
474 )?;
475 }
476 guard.unlock();
477 }
478 Ok(b)
479 })
480 .map(|b| b.clone());
481 guard.unlock();
482 result
483 }
484
485 /// Allocates a new inode in the file system.
486 ///
487 /// This function creates a new inode on disk and returns both its
488 /// inode number and a [`TrackedInode`] handle for in-memory access.
489 /// The allocation is recorded in the given transaction for crash
490 /// consistency.
491 pub fn allocate_inode(
492 self: &Arc<Self>,
493 is_dir: bool,
494 tx: &RunningTransaction,
495 ) -> Result<(InodeNumber, TrackedInode), KernelError> {
496 for (i, lba) in self.inode_bitmap().enumerate() {
497 let bitmap = InodeBitmap::load(self, lba)?;
498 let mut guard = bitmap.write(tx);
499 for pos in 0..4096 * 8 {
500 if guard.try_allocate(pos) {
501 guard.submit();
502 let ino = InodeNumber::new((pos + i * 4096 * 8 + 1) as u32).unwrap();
503 let mut guard = self.inodes.lock();
504 let result = match guard.entry(ino) {
505 Entry::Occupied(_) => Err(KernelError::FilesystemCorrupted(
506 "Allocate to existing inode.",
507 )),
508 Entry::Vacant(en) => {
509 // Lookup inode bitmap.
510 let (lba, index) = self.get_inode_array_lba_index(ino).unwrap();
511 let inode_arr = InodeArray::load(self, lba)?;
512 let inode = Inode::new(ino, is_dir);
513 let mut guard = inode_arr.write(tx);
514 guard[index] = inode.into_disk_format();
515 guard.submit();
516 let mut sb = self.sb.write(tx);
517 sb.inode_count_inused += 1;
518 sb.submit();
519 let inode = Arc::new(RwLock::new(inode));
520 en.insert(inode.clone());
521 Ok((ino, TrackedInode::new(inode, Arc::downgrade(self))))
522 }
523 };
524 guard.unlock();
525 return result;
526 }
527 }
528 guard.forget();
529 }
530 Err(KernelError::NoSpace)
531 }
532
533 /// Allocates a new data block on disk.
534 ///
535 /// This function reserves a free block for use in the file system,
536 /// recording the allocation in the active transaction. The block is
537 /// marked as used in the allocation bitmap and returned to the caller.
538 pub fn allocate_block(
539 &self,
540 tx: &RunningTransaction,
541 ) -> Result<LogicalBlockAddress, KernelError> {
542 for (i, lba) in self.block_bitmap().enumerate() {
543 let bitmap = disk_layout::BlockBitmap::load(self, lba)?;
544 let mut bitmap = bitmap.write(tx);
545 for pos in 0..4096 * 8 {
546 if bitmap.try_allocate(pos) {
547 bitmap.submit();
548 let mut sb = self.sb.write(tx);
549 sb.block_count_inused += 1;
550 sb.submit();
551 return Ok(LogicalBlockAddress::new((pos + i * 4096 * 8) as u64).unwrap());
552 }
553 }
554 bitmap.forget();
555 }
556 Err(KernelError::NoSpace)
557 }
558
559 /// Retrieves an inode from disk or cache.
560 ///
561 /// This function returns a [`TrackedInode`] corresponding to the given
562 /// inode number. If the inode is cached in memory, it is returned
563 /// directly; otherwise, it is read from disk and added to the cache.
564 ///
565 /// This method manages a "unique view" of a single inode.
566 pub fn get_inode(self: &Arc<Self>, ino: InodeNumber) -> Result<TrackedInode, KernelError> {
567 let mut guard = self.inodes.lock();
568 let result = match guard.entry(ino) {
569 Entry::Occupied(en) => Ok(TrackedInode::new(en.get().clone(), Arc::downgrade(self))),
570 Entry::Vacant(en) => {
571 // Lookup inode bitmap.
572 let (lba, offset) = self.get_inode_bitmap_lba_index(ino).unwrap();
573 let bitmap_block = InodeBitmap::load(self, lba)?;
574 if !bitmap_block.read().is_allocated(offset) {
575 return Err(KernelError::NoSuchEntry);
576 }
577
578 let (lba, index) = self.get_inode_array_lba_index(ino).unwrap();
579 let inodes = InodeArray::load(self, lba)?;
580 let inode = Inode::from_disk_layout(&inodes.read()[index])?;
581 if inode.ino != ino {
582 return Err(KernelError::FilesystemCorrupted("Inode number mismatch"));
583 }
584
585 let inode = Arc::new(RwLock::new(inode));
586 en.insert(inode.clone());
587 Ok(TrackedInode::new(inode, Arc::downgrade(self)))
588 }
589 };
590 guard.unlock();
591 result
592 }
593
594 /// Removes an inode from the in-memory inode table.
595 ///
596 /// This function evicts the given inode from the inode cache maintained
597 /// by the file system. It does not remove the inode’s contents on disk,
598 /// only its in-memory representation.
599 pub fn remove_inode(&self, ino: InodeNumber) -> Option<Arc<RwLock<Inode>>> {
600 let mut guard = self.inodes.lock();
601 if let Entry::Occupied(en) = guard.entry(ino)
602 && Arc::strong_count(en.get()) == 2
603 {
604 let result = en.remove();
605 guard.unlock();
606 // This means the caller only has the sole reference to the inode.
607 return Some(result);
608 }
609 guard.unlock();
610 None
611 }
612}
613
614/// A reference-counted wrapper around [`FastFileSystemInner`].
615///
616/// This structure provides access to a Fast File System instance
617/// while ensuring safe concurrent access through an [`Arc`].
618#[derive(Clone)]
619pub struct FastFileSystem(pub Arc<FastFileSystemInner>);
620
621impl FastFileSystem {
622 /// The inode number of the root directory (`/`).
623 pub const ROOT_INODE_NUMBER: InodeNumber = InodeNumber::new(1).unwrap();
624
625 /// Loads a Fast File System from a given disk.
626 ///
627 /// This function attempts to read the superblock from the disk.
628 /// If the disk contains a valid FFS superblock, it returns an
629 /// initialized [`FastFileSystem`] instance; otherwise, it returns `None`.
630 ///
631 /// # Parameters
632 /// - `disk`: The disk device containing the filesystem.
633 ///
634 /// # Returns
635 /// - `Some(Self)`: If the filesystem is successfully loaded.
636 /// - `None`: If the disk does not contain a valid Fast File System.
637 pub fn from_disk(
638 disk: Disk,
639 debug_journal: bool,
640 disable_journal: bool,
641 ) -> Result<Self, KernelError> {
642 let sb = disk_layout::SuperBlock::from_disk(&disk)?;
643 Ok(Self(Arc::new(FastFileSystemInner::from_raw_sb(
644 sb,
645 disk,
646 debug_journal,
647 disable_journal,
648 )?)))
649 }
650
651 /// Retrieves an in-memory representation of the inode identified by `ino`.
652 ///
653 /// This function looks up the inode in the Fast File System and returns a
654 /// [`TrackedInode`].
655 pub fn get_inode(&self, ino: InodeNumber) -> Result<TrackedInode, KernelError> {
656 self.0.get_inode(ino)
657 }
658}
659
660impl keos::fs::traits::FileSystem for FastFileSystem {
661 fn root(&self) -> Option<keos::fs::Directory> {
662 Some(keos::fs::Directory(Arc::new(Directory::new(
663 self.get_inode(Self::ROOT_INODE_NUMBER).unwrap(),
664 Arc::downgrade(&self.0),
665 )?)))
666 }
667}