#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdatomic.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <errno.h>
#include "config.h"
#include "os.h"
#include "tar.h"
#include "fs.h"
#include "hash.h"
#include "inode.h"

Functions
static const char *	remove_subpath (const char path, const char path_end, const char *subpath)
	Inode is represented by struct tarfs_inode; Every inode contains a pointer to a corresponding tarfile entry and a hashed filename (32bit FNV1a hash).
static const char *	path_from_pax_header (const char buf, size_t size, const char templ)
	Used to parse PAX-Header data section which is key=value format:
static int	inode_compare (const struct tarfs_inode a, const struct tarfs_inode b)
	Comparator function for our array sortin routine; Compare two inodes.
static void	inode_exchange (struct tarfs_inode a, struct tarfs_inode b)
	Exchange two node indicies.
static void	inode_siftdown (struct tarfs_inode **v, size_t root, size_t end)
	Sift subarray down.
void	inode_sort (struct tarfs_inode **iarr, size_t count)
	Sort inode indicies.
static struct tarfs_inode *	merge (struct tarfs_inode a, struct tarfs_inode b)
	Alphaberical order sorting routines Inodes once created are "position-immutable": that means, inode, once populated stays where she is and only index pointers are manipulated to get a sorted array.
static struct tarfs_inode *	merge_sort (struct tarfs_inode *head)
	Classic merge-sort It is recursive but recursion depth log N, i.e.
struct tarfs_inode *	inode_alphasort (struct tarfs_inode *array, size_t count)
	Sort inodes alphabetically: we do not move inodes.
struct tarfs_inode **	inode_alloc (size_t count)
	Returns an array of pointers to tarfs_inode structures.
void	inode_free (struct tarfs_inode **index, size_t count, uintptr_t tar_start, size_t tar_length)
	Free inodes.
static bool	inode_pathcmp (const struct tarfs_inode inode, const char src)
	Check if given inode is exactly given path.
int	inode_lookup (struct tarfs_inode const const index, size_t num_inodes, const char *path)
	Find an inode that corresponds to given path name.
tart_t	inode_getinfo (struct tarfs_inode const const index, int idx, size_t size, time_t mtime)
	inode_getinfo() : get inode's Type, Size and Mtime These are not precached and must be calculated every time.
tart_t	inode_type (struct tarfs_inode const *ino)
tart_t	inode_rawtype (struct tarfs_inode const *ino)
	Return raw inode type: TART_HARDLINK, TART_SYMLINK, TART_DIR, TART_FILE or TART_BAD.
bool	inode_islink (struct tarfs_inode const *ino)
time_t	inode_mtime (struct tarfs_fs fs, int idx, size_t size)
int	inode_resolve (struct tarfs_inode **index, size_t count)
size_t	inode_populate (struct tarfs_inode inodes, size_t nino, const uint8_t tar_start, size_t tar_length, const char link_rebase, const char root_folder, struct tarfs_stats *st)
	Populate inodes.
void	inode_unmount (struct tarfs_fs fs, const void tar_start, size_t tar_size)
	Unmount a TAR image.
int	inode_mount (struct tarfs_fs fs, const unsigned char buf, size_t size, const char rebase_link, const char base_dir)
	Build an inode index for a TAR image.
void	inode_dumphash_sorted (struct tarfs_inode const const index, size_t count)
	Displays inodes sorted by hash.
void	inode_dumppath_sorted (struct tarfs_inode const *root)
	Displays inodes sorted by path.

Variables
static char const *	s_bad_path = "<bad path>"

Function Documentation

◆ inode_alloc()

struct tarfs_inode ** inode_alloc ( size_t count )

Returns an array of pointers to tarfs_inode structures.

Allocate an inode index.

Inodes are allocated and initialized to all zeros, array of pointers is allocated in populated with pointers to individual inodes Memory layout, single chunk: 0x3fc00000 .. [[index][inodes]] ..3fcxxxxx ---> memory grows this way

Returns an array of pointers to tarfs_inode structures.

Allocates an array of inode pointers capable of holding count entries.

Parameters

count Number of inode pointers to allocate.

Returns: Newly allocated inode index, or NULL on failure.

Definition at line 303 of file inode.c.

References log, and tarfs_calloc().

Referenced by inode_mount().

◆ inode_alphasort()

struct tarfs_inode * inode_alphasort	(	struct tarfs_inode *	array,
		size_t	count )

Sort inodes alphabetically: we do not move inodes.

we do not move inode's indices. Instead we use inode's in_next field to link all inodes in alphabetical order. This way we can have our inodes sorted by a hash AND sorted by its path

Definition at line 279 of file inode.c.

References merge_sort().

Referenced by inode_mount().

◆ inode_compare()

int inode_compare	(	const struct tarfs_inode *	a,
		const struct tarfs_inode *	b )

static

Comparator function for our array sortin routine; Compare two inodes.

Definition at line 147 of file inode.c.

Referenced by inode_siftdown().

◆ inode_dumphash_sorted()

void inode_dumphash_sorted	(	struct tarfs_inode const const	index,
		size_t	count )

Displays inodes sorted by hash.

Dump the inode hash table in sorted order.

Displays inodes sorted by hash.

Debug helper used to inspect the inode index.

Parameters

index	Inode index.
count	Number of entries.

Definition at line 1032 of file inode.c.

References inode_getinfo().

◆ inode_dumppath_sorted()

void inode_dumppath_sorted ( struct tarfs_inode const * root )

Displays inodes sorted by path.

Dump the directory tree sorted by pathname.

Displays inodes sorted by path.

Debug helper that recursively prints the filesystem hierarchy.

Parameters

root	Root inode.

Definition at line 1057 of file inode.c.

◆ inode_exchange()

void inode_exchange	(	struct tarfs_inode **	a,
		struct tarfs_inode **	b )

inlinestatic

Exchange two node indicies.

Definition at line 158 of file inode.c.

Referenced by inode_siftdown(), and inode_sort().

◆ inode_free()

void inode_free	(	struct tarfs_inode **	index,
		size_t	count,
		uintptr_t	tar_start,
		size_t	tar_length )

Free inodes.

Destroy an inode index.

All memory associated with inodes is freed: inodes and index array. Some inodes may have allocated names. There is no way to distiguish allocated name from a TAR name, except for checking pointer address to NOT BE in the mmaped TAR file

Free inodes.

Frees an inode index previously created by inode_alloc() together with all associated inode objects.

Parameters

index	Inode index.
count	Number of entries in the index.
tar_start	Start address of the mounted TAR image.
tar_length	TAR image size in bytes.

Definition at line 342 of file inode.c.

References tarfs_os_free().

Referenced by inode_unmount().

◆ inode_getinfo()

tart_t inode_getinfo	(	struct tarfs_inode const const	index,
		int	idx,
		size_t *	size,
		time_t *	mtime )

inode_getinfo() : get inode's Type, Size and Mtime These are not precached and must be calculated every time.

Get information about an inode.

Having this information in the tarfs_inode will increase the size of inode list dramatically

Parameters

fs	a pointer to mounted FS
idx	inode of intereset (inode index)
size	if not NULL, provides the location to store the entry size
mtime	if not NULL, provides the location to store the entry mtime

Returns: Entry type (e.g. TART_FILE or TART_DIR etc). If return value is TART_BAD, then this is an indication of an invalid/unusable inode

inode_getinfo() : get inode's Type, Size and Mtime These are not precached and must be calculated every time.

Retrieves metadata for the inode referenced by an inode index entry. Either size or mtime may be NULL if the corresponding value is not required.

Parameters

index	Inode index.
idx	Inode number within the index.
size	Optional output for file size.
mtime	Optional output for modification time.

Returns: TAR entry type.

Definition at line 466 of file inode.c.

References mtime, tarhdr_t::mtime, size, tarhdr_t::size, tar_octal(), tart_t, and tarhdr_t::type.

Referenced by inode_dumphash_sorted(), inode_resolve(), tarf_fstat(), and tarf_open().

◆ inode_islink()

bool inode_islink ( struct tarfs_inode const * ino )

Definition at line 521 of file inode.c.

References tarhdr_t::type.

◆ inode_lookup()

int inode_lookup	(	struct tarfs_inode const const	index,
		size_t	num_inodes,
		const char *	path )

Find an inode that corresponds to given path name.

Find an inode by pathname.

Performs a binary search in the array of pointers to struct tarfs_inode (index array). The array is sorted by ->in_hash

Inode pointer can be retrieved as node_ptr = index[i] where i is node index as returned by inode_lookup()

Returns inode index (>=0) or -errno

Find an inode that corresponds to given path name.

Performs a pathname lookup in the inode index.

Parameters

index	Inode index.
num_inodes	Number of entries in the index.
path	Absolute path to search for.

Returns: Inode index on success, or -1 if not found.

< Init vector for 32bit hash

Definition at line 399 of file inode.c.

References hash32(), HASH32_IV, inode_pathcmp(), and log.

Referenced by inode_resolve(), and tarf_open().

◆ inode_mount()

int inode_mount	(	struct tarfs_fs *	fs,
		const unsigned char *	buf,
		size_t	size,
		const char *	rebase_link,
		const char *	path_rebase )

Build an inode index for a TAR image.

Scans the TAR archive, creates the inode index and initializes the filesystem state.

Parameters

fs	Filesystem instance.
buf	Start address of the TAR image.
size	TAR image size in bytes.
rebase_link	Optional path prefix substracted from symbolic links.
path_rebase	Optional path prefix substracted from every TAR entry. Normally this one is autodetected (the very first directory in the archive becomes the 'path_rebase' parameter) and then substracted from every path in the archive, so archive gets "/" entry

Return values

0	Success.
-1	Mount failed.

< Hash32 value of a single-character C-string "/". NOTE: must be recomputed if hash32 algo is changed!

Definition at line 932 of file inode.c.

References tarfs_fs::fs_dsize, tarfs_fs::fs_ino, tarfs_fs::fs_mtime, tarfs_fs::fs_nino, tarfs_fs::fs_root, tarfs_fs::fs_size, tarfs_fs::fs_stats, tarfs_fs::fs_vaddr, HASH32_SLASH, inode_alloc(), inode_alphasort(), inode_populate(), inode_resolve(), inode_sort(), log, mtime, tarhdr_t::mtime, size, tar_getnino(), and tar_octal().

Referenced by tarfs_mount_memory().

◆ inode_mtime()

time_t inode_mtime	(	struct tarfs_fs *	fs,
		int	idx,
		size_t *	size )

Definition at line 535 of file inode.c.

References tarfs_fs::fs_ino, size, tarhdr_t::size, tar_octal(), and tarhdr_t::type.

◆ inode_pathcmp()

bool inode_pathcmp	(	const struct tarfs_inode *	inode,
		const char *	src )

static

Check if given inode is exactly given path.

This function is used as final check as collision avoidance step after hash-based binary search. Unless we are using perfect hash (which should be possible to generate on mount()) we have to verify our search results.

Definition at line 364 of file inode.c.

Referenced by inode_lookup().

◆ inode_populate()

size_t inode_populate	(	struct tarfs_inode *	inodes,
		size_t	nino,
		const uint8_t *	tar_start,
		size_t	tar_length,
		const char *	link_rebase,
		const char *	root_folder,
		struct tarfs_stats *	st )

Populate inodes.

Inodes must be allocated, and the allocation size must match real amount of inodes, which can be obtained through tar_getnino

Returns: Total size of all files containing data

< Init vector for 32bit hash

Definition at line 655 of file inode.c.

References tarfs_stats::badblocks, tarfs_stats::dirs, tarfs_stats::files, hash32(), HASH32_IV, tarfs_stats::links, log, path_from_pax_header(), tarfs_stats::ram, remove_subpath(), s_bad_path, size, tar_baddata(), tar_badhdr(), tar_octal(), tar_strdup1(), tar_strlen(), tarfs_integrity(), and tarfs_strdup().

Referenced by inode_mount().

◆ inode_rawtype()

tart_t inode_rawtype ( struct tarfs_inode const * ino )

Return raw inode type: TART_HARDLINK, TART_SYMLINK, TART_DIR, TART_FILE or TART_BAD.

Definition at line 506 of file inode.c.

References tart_t, and tarhdr_t::type.

◆ inode_resolve()

int inode_resolve	(	struct tarfs_inode **	index,
		size_t	count )

Definition at line 561 of file inode.c.

References inode_getinfo(), inode_lookup(), link_name, log, tarfs_os_free(), tart_t, and type.

Referenced by inode_mount().

◆ inode_siftdown()

void inode_siftdown	(	struct tarfs_inode **	v,
		size_t	root,
		size_t	end )

static

Sift subarray down.

Definition at line 170 of file inode.c.

References inode_compare(), and inode_exchange().

Referenced by inode_sort().

◆ inode_sort()

void inode_sort	(	struct tarfs_inode **	iarr,
		size_t	count )

Sort inode indicies.

Sorting is done by ->in_hash member

Definition at line 192 of file inode.c.

References inode_exchange(), and inode_siftdown().

Referenced by inode_mount().

◆ inode_type()

tart_t inode_type ( struct tarfs_inode const * ino )

Definition at line 490 of file inode.c.

References tart_t, and tarhdr_t::type.

Referenced by tard_readdir().

◆ inode_unmount()

void inode_unmount	(	struct tarfs_fs *	fs,
		const void *	tar_start,
		size_t	tar_size )

Unmount a TAR image.

Releases all in-memory data structures associated with a mounted TARFS instance.

Parameters

fs	Filesystem instance.
tar_start	Start address of the mounted TAR image.
tar_size	TAR image size in bytes.

Definition at line 921 of file inode.c.

References tarfs_fs::fs_ino, tarfs_fs::fs_nino, inode_free(), and log.

Referenced by commit_unmount().

◆ merge()

struct tarfs_inode * merge	(	struct tarfs_inode *	a,
		struct tarfs_inode *	b )

static

Alphaberical order sorting routines Inodes once created are "position-immutable": that means, inode, once populated stays where she is and only index pointers are manipulated to get a sorted array.

In a similar way inode's in_next field is used to create an alphasorted list (singly-linked list)

Definition at line 221 of file inode.c.

References tar_strcmp().

Referenced by merge_sort().

◆ merge_sort()

struct tarfs_inode * merge_sort ( struct tarfs_inode * head )

static

Classic merge-sort It is recursive but recursion depth log N, i.e.

for 65536 files it will be 16 stack frames. Not too bad. TODO: add a hard limit for the recursion depth? 32 seems reasonable

Definition at line 250 of file inode.c.

References merge(), and merge_sort().

Referenced by inode_alphasort(), and merge_sort().

◆ path_from_pax_header()

const char * path_from_pax_header	(	const char *	buf,
		size_t	size,
		const char *	templ )

static

Used to parse PAX-Header data section which is key=value format:

20 path=/some/data 20 linkpath=/some/data

Here we depend on
or \r at the end of every key=value pair, which is guaranteed by the standart

Definition at line 78 of file inode.c.

References log, and size.

Referenced by inode_populate().

◆ remove_subpath()

const char * remove_subpath	(	const char *	path,
		const char *	path_end,
		const char *	subpath )

static

Inode is represented by struct tarfs_inode; Every inode contains a pointer to a corresponding tarfile entry and a hashed filename (32bit FNV1a hash).

Sorted inodes reside in the fs->fs_ino array and are the primary indexing mechanism. Binary array search is used for paths lookup (i.e. 16 lookups at worst for 65535 files)

hotpath is inode_lookup() For the given UTS remove the leading subpath if it is there:

"subpath/path" --> "/path"

Definition at line 51 of file inode.c.

Referenced by inode_populate().

Variable Documentation

◆ s_bad_path

char const* s_bad_path = "<bad path>"

static

Definition at line 647 of file inode.c.

Referenced by inode_populate().

Functions

Variables

Function Documentation

◆ inode_alloc()

◆ inode_alphasort()

◆ inode_compare()

◆ inode_dumphash_sorted()

◆ inode_dumppath_sorted()

◆ inode_exchange()

◆ inode_free()

◆ inode_getinfo()

◆ inode_islink()

◆ inode_lookup()

◆ inode_mount()

◆ inode_mtime()

◆ inode_pathcmp()

◆ inode_populate()

◆ inode_rawtype()

◆ inode_resolve()

◆ inode_siftdown()

◆ inode_sort()

◆ inode_type()

◆ inode_unmount()

◆ merge()

◆ merge_sort()

◆ path_from_pax_header()

◆ remove_subpath()

Variable Documentation

◆ s_bad_path