rec_entry_operations_bsfs.c File Reference

Recovery entry B-tree operations for BSFS (implementation). More...

Functions
uint32_t	get_next_rec_id (FILE *disk, btree_handle_t *rec_tree)
	Finds the next available recovery ID number by scanning 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_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_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 (implementation).

This module implements the management of the Recovery B-tree, which stores snapshots of deleted files (rec_entry_t) to enable later restoration. It provides initialization of the recovery tree, CRUD-like operations (add/remove/search), and a purge routine based on a timestamp threshold.

Notes:

• Data block reclamation for purged entries must be performed by a separate garbage-collection component, which can iterate the removed entries and free their blocks safely.
• The B-tree handle provided here is type-agnostic; key encoding and comparison are adapted for the rec_entry key layout.

Function Documentation

get_next_rec_id()

uint32_t get_next_rec_id	(	FILE *	disk,
		btree_handle_t *	rec_tree )

Finds the next available recovery ID number by scanning the recovery B-tree.

This function scans the recovery tree to find the highest recovery ID in use and returns the next available one. This ensures uniqueness of recovery ID without reusing deleted ones.

Parameters

disk	Pointer to the disk file.
rec_tree	Pointer to the B-tree handle for recovery tree.

Returns

The next available (unused) recovery ID.

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.