rec_entry_operations_bsfs.h File Reference

Recovery entry B-tree operations for BSFS. More...

Functions
int	rec_tree_init (FILE *disk, superblock_t *sb, btree_handle_t *out)
	Initialize (or load) the Recovery B-tree handle.
int	rec_tree_add (FILE *disk, superblock_t *sb, btree_handle_t *rec_tree, rec_entry_t *entry)
	Insert a recovery entry into the Recovery B-tree.
int	rec_tree_remove (FILE *disk, superblock_t *sb, btree_handle_t *rec_tree, uint32_t recovery_id)
	Remove a recovery entry from the Recovery B-tree by ID.
int	rec_tree_search (FILE *disk, btree_handle_t *rec_tree, uint32_t recovery_id, rec_entry_t *out_entry)
	Look up a recovery entry in the Recovery B-tree by ID.
int	rec_tree_find_by_name (FILE *disk, btree_handle_t *rec_tree, const char *name, rec_entry_t *out, size_t max, size_t *out_count)
	Find recovery entries by original filename.
int	purge_file (FILE *disk, superblock_t *sb, btree_handle_t *data_tree, btree_handle_t *rec_tree, const rec_entry_t *rec)
	Permanently purge a deleted file from the filesystem.

Detailed Description

Recovery entry B-tree operations for BSFS.

This header defines the public API to manage the Recovery B-tree used by BSFS to track deleted files for later restoration. Each record stores a snapshot of the file's inode metadata and block mapping at deletion time.

Provided operations:

• Initialization of the recovery tree in the filesystem image.
• Add / remove / search recovery entries by key.
• Purge (garbage collect) old entries by timestamp threshold.

Function Documentation

purge_file()

int purge_file	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	data_tree,
		btree_handle_t *	rec_tree,
		const rec_entry_t *	rec )

Permanently purge a deleted file from the filesystem.

Reclaims all data blocks referenced by the snapshot rec (both direct spans and spans in the per-file data B-tree), removes the span records, and finally removes the metadata entry from the Recovery B-tree.

Failure semantics:

• If deallocation of data or removal of span mappings fails, the recovery entry is NOT removed and the function returns -1, allowing a retry.

Parameters

disk	Open filesystem image.
sb	Loaded superblock.
data_tree	B-tree handle for file data spans (bspan_t mappings).
rec_tree	B-tree handle for recovery entries (rec_entry_t).
rec	The recovery entry describing the file to purge.

Returns

0 on success; -1 on error.

rec_tree_add()

int rec_tree_add	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	rec_tree,
		rec_entry_t *	entry )

Insert a recovery entry into the Recovery B-tree.

This function inserts a rec_entry_t into the recovery tree. The B-tree must be configured so that:

• handle->entry_size == sizeof(rec_entry_t);
• handle->get_key points to the recovery_id field inside rec_entry_t; and
• handle->cmp compares recovery_id in ascending order (or matches your chosen ordering).

If entry->recovery_id is 0, a new unique ID is assigned via get_next_rec_id(). On duplicate key, the underlying B-tree insert is expected to fail and this function returns 0.

Parameters

disk	Open filesystem image.
sb	Loaded superblock (used for node allocations).
rec_tree	Recovery B-tree handle (already initialized).
entry	In/out recovery entry to insert. If recovery_id == 0, it will be set to a fresh ID before insertion.

Returns

1 on success; 0 on failure (I/O error or duplicate key).

rec_tree_find_by_name()

int rec_tree_find_by_name	(	FILE *	disk,
		btree_handle_t *	rec_tree,
		const char *	name,
		rec_entry_t *	out,
		size_t	max,
		size_t *	out_count )

Find recovery entries by original filename.

Performs an in-order traversal over the Recovery B-tree (keyed by rec_entry_t::recovery_id) and collects entries whose rec_entry_t::original_name matches exactly the provided name.

Up to max matches are copied into the out buffer (if non-NULL). The total number of matches found in the tree (which can be greater than max) is returned via out_count.

Parameters

disk	Open filesystem image.
rec_tree	Initialized Recovery B-tree handle.
name	Exact filename to match against rec_entry_t::original_name.
out	Output buffer for matches (may be NULL to only count).
max	Capacity of out in number of entries.
out_count	Output: total number of matches found.

Returns

1 on success (including zero matches), 0 on invalid args or I/O failure while traversing.

rec_tree_init()

int rec_tree_init	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	out )

Initialize (or load) the Recovery B-tree handle.

If the recovery tree does not exist yet, this function creates a new B-tree (root block allocation and on-disk initialization) and persists its root into the superblock. If it already exists, this function creates an in-memory handle pointing at the existing root.

Parameters

disk	Open filesystem image.
sb	Loaded superblock (may be updated if the root is created).
out	Output: initialized B-tree handle for the recovery tree.

Returns

1 on success, 0 on failure.

rec_tree_remove()

int rec_tree_remove	(	FILE *	disk,
		superblock_t *	sb,
		btree_handle_t *	rec_tree,
		uint32_t	recovery_id )

Remove a recovery entry from the Recovery B-tree by ID.

This function deletes a single rec_entry_t identified by its recovery_id from the Recovery tree. The B-tree for recovery entries must be configured so that the key is the 32-bit recovery_id field of rec_entry_t (i.e., handle->get_key returns &entry->recovery_id).

Semantics:

• If an entry with the given recovery_id exists, it is removed from the tree and the function returns 1.
• If no such entry exists, the function returns 0.

Notes:

• This function only removes the metadata entry from the Recovery B-tree. Reclaiming data blocks referenced by the entry (if any) must be handled by a higher-level GC routine before or after removal, depending on your chosen policy.

Parameters

disk	Open filesystem image.
sb	Loaded superblock.
rec_tree	Recovery B-tree handle (already initialized).
recovery_id	Unique identifier of the recovery entry to remove.

Returns

1 if the entry was found and removed; 0 otherwise.

rec_tree_search()

int rec_tree_search	(	FILE *	disk,
		btree_handle_t *	rec_tree,
		uint32_t	recovery_id,
		rec_entry_t *	out_entry )

Look up a recovery entry in the Recovery B-tree by ID.

This function searches the Recovery B-tree for a rec_entry_t whose key is the 32-bit recovery_id. The B-tree must be configured so that the key for each node record is the recovery_id field of rec_entry_t (i.e., the handle's key accessor returns &entry->recovery_id).

Semantics:

• If an entry with the given recovery_id exists, it is copied into out_entry and the function returns 1.
• If not found, the function returns 0 and leaves out_entry unmodified.

Parameters

disk	Open filesystem image.
rec_tree	Recovery B-tree handle (already initialized).
recovery_id	Key (unique ID) of the recovery entry to find.
out_entry	Output buffer to receive the found entry (must be non-NULL).

Returns

1 if found; 0 if not found or on invalid arguments.