path: root/libudffs/extent.c

/*
 * extent.c
 *
 * Copyright (c) 2001-2002  Ben Fennema <bfennema@falcon.csc.calpoly.edu>
 * Copyright (c) 2014-2017  Pali Rohár <pali.rohar@gmail.com>
 * All rights reserved.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 */

/**
 * @file
 * libudffs extend handling functions
 */

#include "config.h"

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <time.h>
#include <sys/time.h>
#include <errno.h>

#include "libudffs.h"

/**
 * This code was very sparsely commented and essentially undocumented as written.
 * Comments and doxygen documentation were generated by code inspection more than
 * a decade after the fact. If you find errors please feel free to correct them.
 *
 * For a more detailed discussion about descriptors the comments at the top
 * of file.c in this directory.
 *
 * Volume space is the set of all blocks on a particular physical disc volume.
 * Blocks in volume space are described using an 32-bit short_ad.
 * A volume-set is multiple related physical volumes, usually with a robotic
 * media changer. Blocks anywhere in a volume set are described by an 48-bit
 * long_ad which contains a volume identifier as well as a location
 * in the volume space of the identifed volume. Block numbers in volume space
 * start at zero and are relative to the first block of the media.
 *
 * Partition space is the set of all blocks contained in a logical partition.
 * Block numbers in partition space start at zero and are relative to the first
 * block of the partition, *NOT* the first block of of the media
 *
 * An 'extent' is a contiguous set of data and a descriptor is a structure
 * containing descriptive information, but these names are used in two very
 * different ways when creating a UDF filesystem on a disc volume/volume-set.
 *
 * An ECMA-167 extent is a region in the volume space of a single physical
 * disc volume described by type extent_ad having a 32-bit starting block
 * and a 32-bit length <2^30 *BYTES* which is normally a multiple of blocksize.
 * The two high order bits define the allocated/written status of the extent.
 * These extents are used in on-disc descriptors at the physical volume level
 * for structures such as the primary volume descriptor and anchor points that
 * operate above the filesystem level.
 *
 * The on-disc descriptors are little-endian and require the use of various
 * le*_to_cpu() and cpu_to_le*() functions when reading and writing them.
 * Descriptors like the primary volume descriptor which are shared with other
 * standards such as ECMA-119/ISO-9660 begin with a one byte type identifier.
 * Other descriptors which are specific to ECMA-167 and UDF begin with a 16-byte
 * tag which starts with a two byte tag identifer and contains additional
 * information such as a CRC field which is pertinent to udf_extents.
 *
 * A udf_extent is an in-memory structure used to organize UDF filesystem level
 * structures such as directories and files and is described using a struct
 * udf_extent having a 32-bit starting block and a 32-bit length *IN BLOCKS*
 * as well as a space type such as unallocated or partition space and various
 * linked lists in cpu byte order. A udf_disc starts with a single extent of
 * unallocated space which becomes a list as that extent is split and the new
 * smaller extents are used for various things. A udf_extent has a udf_descriptor
 * list which is kept sorted by the location within the extent of the described
 * blocks. A udf_descriptor can have a number of different tag identifiers such
 * as file-entry/extended-file-entry descriptor or allocation descriptor.
 * A udf_descriptor has a udf_data list. A udf_data item carries a payload of
 * arbitrary data dependent on the descriptor type. The udf_descriptor can be
 * thought of as the in-memory version of the descriptor tag since it contains
 * the tag ident. The on-disc format structure corresponding to that tag is
 * stored in the first udf_data item on the udf_data list of that descriptor.
 * The 16-byte on-disc format tag will be at the beginning of that structure.
 *
 * Once the UDF volume structure has been constructed in memory, writing it to
 * disc is just a matter of iterating through the extents and their descriptors
 * and data in order and writing them sequentially onto the media while also
 * converting to the on-disc little-endian format as needed.
 */

/**
 * @brief find the next udf_extent of a given space_type on a udf_extent list
 * @param start_ext the starting udf_extent for the search
 * @param type the space_type of the udf_extent to search for
 * @return the in-memory address of udf_extent or NULL
 */
struct udf_extent *next_extent(struct udf_extent *start_ext, enum udf_space_type type)
{
	while (start_ext != NULL && !(start_ext->space_type & type))
		start_ext = start_ext->next;

	return start_ext;
}

/**
 * @brief find the next udf_extent of a given space_type on a udf_extent list
 *        that satisfies the necessary size and alignment
 * @param disc the udf_disc containing the blocks
 * @param start_ext the starting udf_extent for the search
 * @param type the space_type of the udf_extent to search for
 * @param blocks the minimum size of the udf_extent in blocks
 * @param offset the required alignment for the start block
 * @return the start block of the aligned udf_extent or zero
 */
uint32_t next_extent_size(struct udf_disc *disc, struct udf_extent *start_ext, enum udf_space_type type, uint32_t blocks, uint32_t offset)
{
	return find_next_extent_size(disc, start_ext->start, type, blocks, offset);
}

/**
 * @brief find the next udf_extent of a given space_type on a udf_extent list
 *        that satisfies the necessary size and alignment
 * @param disc the udf_disc containing the blocks
 * @param start the block to search for
 * @param type the space_type of the udf_extent to search for
 * @param blocks the minimum size of the udf_extent in blocks
 * @param offset the required alignment for the start block
 * @return the start block of the aligned udf_extent or zero
 */
uint32_t find_next_extent_size(struct udf_disc *disc, uint32_t start, enum udf_space_type type, uint32_t blocks, uint32_t offset)
{
	uint32_t inc;
	struct udf_extent *start_ext;

	start_ext = next_extent(find_extent(disc, start), type);
cont:
	while (start_ext != NULL && start_ext->blocks < blocks)
		start_ext = next_extent(start_ext->next, type);

	if (start_ext != NULL && (start_ext->start % offset || start_ext->start < start))
	{
		if (start_ext->start < start)
			inc = start - start_ext->start;
		else
			inc = offset - (start_ext->start % offset);
		if (start_ext->blocks - inc < blocks)
		{
			start_ext = next_extent(start_ext->next, type);
			goto cont;
		}
	}
	else
		inc = 0;

	return start_ext ? start_ext->start + inc : 0;
}

/**
 * @brief find the previous udf_extent of a given space_type on a udf_extent list
 * @param start_ext the starting udf_extent for the search
 * @param type the space_type of the udf_extent to search for
 * @return the in-memory address of the udf_extent or NULL
 */
struct udf_extent *prev_extent(struct udf_extent *start_ext, enum udf_space_type type)
{
	while (start_ext != NULL && !(start_ext->space_type & type))
		start_ext = start_ext->prev;

	return start_ext;
}

/**
 * @brief find the previous udf_extent of a given space_type on a udf_extent
 *        list that satisfies the necessary size and alignment
 * @param start_ext the starting udf_extent for the search
 * @param type the space_type of the udf_extent to search for
 * @param blocks the minimum size of the udf_extent in blocks
 * @param offset the required alignment for the start block
 * @return the start block of the aligned udf_extent or zero
 */
uint32_t prev_extent_size(struct udf_extent *start_ext, enum udf_space_type type, uint32_t blocks, uint32_t offset)
{
	uint32_t inc;

	start_ext = prev_extent(start_ext, type);
cont:
	while (start_ext != NULL && start_ext->blocks < blocks)
		start_ext = prev_extent(start_ext->prev, type);

	if (start_ext != NULL && (start_ext->start % offset))
	{
		inc = offset - (start_ext->start % offset);
		if (start_ext->blocks - inc < blocks)
		{
			start_ext = prev_extent(start_ext->prev, type);
			goto cont;
		}
	}
	else
		inc = 0;

	return start_ext ? start_ext->start + inc + ((start_ext->blocks - inc - blocks)/offset)*offset : 0;
}

/**
 * @brief find the udf_extent on a udf_disc's udf_extent list which contains
 *        a particular block
 * @param disc the udf_disc containing the udf_extent list head
 * @param start the block to search for
 * @return the in-memory address of the udf_extent or NULL
 */
struct udf_extent *find_extent(struct udf_disc *disc, uint32_t start)
{
	struct udf_extent *start_ext = disc->head;

	while (start_ext->next != NULL)
	{
		if (start_ext->start + start_ext->blocks > start)
			break;
		start_ext = start_ext->next;
	}
	return start_ext;
}

/**
 * @brief set the space_type, location and size of a udf_extent on a
 *        udf_disc's udf_extent list, splitting the udf_extent if required
 *        to have the returned udf_extent only contain the requested blocks
 * @param disc the udf_disc containing the blocks
 * @param type the space_type of the udf_extent
 * @param start the start block of the udf_extent
 * @param blocks the size of the udf_extent in blocks
 * @return the in-memory address of the udf_extent
 */
struct udf_extent *set_extent(struct udf_disc *disc, enum udf_space_type type, uint32_t start, uint32_t blocks)
{
	struct udf_extent *new_ext, *start_ext = find_extent(disc, start);

	if (start < start_ext->start)
	{
		fprintf(stderr, "%s: Error: Not enough blocks on device\n", appname);
		exit(1);
	}

	if (start == start_ext->start)
	{
		if (blocks == start_ext->blocks)
		{
			start_ext->space_type = type;

			return start_ext;
		}
		else if (blocks < start_ext->blocks)
		{
			new_ext = malloc(sizeof(struct udf_extent));
			new_ext->space_type = type;
			new_ext->start = start;
			new_ext->blocks = blocks;
			new_ext->head = new_ext->tail = NULL;
			new_ext->prev = start_ext->prev;
			if (new_ext->prev)
				new_ext->prev->next = new_ext;
			new_ext->next = start_ext;
			if (disc->head == start_ext)
				disc->head = new_ext;

			start_ext->start += blocks;
			start_ext->blocks -= blocks;
			start_ext->prev = new_ext;

			return new_ext;
		}
		else /* blocks > start_ext->blocks */
		{
			fprintf(stderr, "%s: Error: Not enough blocks on device\n", appname);
			exit(1);
		}
	}
	else /* start > start_ext->start */
	{
		if (start + blocks == start_ext->start + start_ext->blocks)
		{
			new_ext = malloc(sizeof(struct udf_extent));
			new_ext->space_type = type;
			new_ext->start = start;
			new_ext->blocks = blocks;
			new_ext->head = new_ext->tail = NULL;
			new_ext->prev = start_ext;
			new_ext->next = start_ext->next;
			if (new_ext->next)
				new_ext->next->prev = new_ext;
			if (disc->tail == start_ext)
				disc->tail = new_ext;

			start_ext->blocks -= blocks;
			start_ext->next = new_ext;

			return new_ext;
		}
		else if (start + blocks < start_ext->start + start_ext->blocks)
		{
			new_ext = malloc(sizeof(struct udf_extent));
			new_ext->space_type = type;
			new_ext->start = start;
			new_ext->blocks = blocks;
			new_ext->head = new_ext->tail = NULL;
			new_ext->prev = start_ext;

			new_ext->next = malloc(sizeof(struct udf_extent));
			new_ext->next->prev = new_ext;
			new_ext->next->space_type = start_ext->space_type;
			new_ext->next->start = start + blocks;
			new_ext->next->blocks = start_ext->blocks - blocks - start + start_ext->start;
			new_ext->next->head = new_ext->next->tail = NULL;
			new_ext->next->next = start_ext->next;
			if (new_ext->next->next)
				new_ext->next->next->prev = new_ext->next;
			if (disc->tail == start_ext)
				disc->tail = new_ext->next;

			start_ext->blocks = start - start_ext->start;
			start_ext->next = new_ext;

			return new_ext;
		}
		else /* start + blocks > start_ext->start + start_ext->blocks */
		{
			if (start_ext->blocks < blocks)
			{
				fprintf(stderr, "%s: Error: Not enough blocks on device\n", appname);
				exit(1);
			}
			new_ext = malloc(sizeof(struct udf_extent));
			new_ext->space_type = type;
			new_ext->start = start;
			new_ext->blocks = blocks;
			new_ext->head = new_ext->tail = NULL;
			new_ext->prev = start_ext;
			new_ext->next = start_ext->next;
			if (new_ext->next)
				new_ext->next->prev = new_ext;
			if (disc->tail == start_ext)
				disc->tail = new_ext;

			start_ext->blocks -= blocks;
			start_ext->next = new_ext;

			return new_ext;
		}
	}
}

/**
 * @brief find the next udf_descriptor of a given tag ident on a udf_descriptor list
 * @param start_desc the starting udf_descriptor for the search
 * @param ident the tag ident of udf_descriptor to search for
 * @return the in-memory address of the udf_descriptor or NULL
 */
struct udf_desc *next_desc(struct udf_desc *start_desc, uint16_t ident)
{
	while (start_desc != NULL && start_desc->ident != ident)
		start_desc = start_desc->next;

	return start_desc;
}

/**
 * @brief search the udf_descriptor list of a udf_extent to find the udf_descriptor
 *        that describes a particular block
 * @param ext the udf_extent containing the udf_descriptor list head
 * @param offset the block to search for
 * @return the in-memory address of the udf_descriptor or NULL
 */
struct udf_desc *find_desc(struct udf_extent *ext, uint32_t offset)
{
	struct udf_desc *start_desc = ext->head;

	while (start_desc->next != NULL)
	{
		if (start_desc->offset == offset)
			return start_desc;
		else if (start_desc->offset > offset)
			return start_desc->prev;
		else
			start_desc = start_desc->next;
	}
	return start_desc;
}

/**
 * @brief allocate a new udf_descriptor having a udf_data item and insert it
 *        into the udf_descriptor list of a udf_extent ordered by block number
 * @oaram ext the udf_extent containing the udf_descriptor list head
 * @param ident the tag ident of the new udf_descriptor
 * @param offset the first block the new descriptor describes
 * @param length the length of the udf_data item payload in bytes
 * @param data the udf_data item, if NULL allocate memory for the udf_data item
 * @return the in-memory address of the new udf_descriptor
 */
struct udf_desc *set_desc(struct udf_extent *ext, uint16_t ident, uint32_t offset, uint32_t length, struct udf_data *data)
{
	struct udf_desc *start_desc, *new_desc = calloc(1, sizeof(struct udf_desc));

	new_desc->ident = ident;
	new_desc->offset = offset;
	new_desc->length = length;
	if (data == NULL)
		new_desc->data = alloc_data(NULL, length);
	else
		new_desc->data = data;

	if (ext->head == NULL)
	{
		ext->head = ext->tail = new_desc;
		new_desc->next = new_desc->prev = NULL;
	}
	else
	{
		start_desc = find_desc(ext, offset);
		if (start_desc == NULL)
		{
			new_desc->next = ext->head;
			new_desc->prev = NULL;
			new_desc->next->prev = new_desc;
			ext->head = new_desc;
		}
		else
		{
			new_desc->next = start_desc->next;
			new_desc->prev = start_desc;
			if (start_desc->next)
				start_desc->next->prev = new_desc;
			else
				ext->tail = new_desc;
			start_desc->next = new_desc;
		}
	}

	return new_desc;
}

/**
 * @brief append a udf_data list to the end of the udf_data list of a
 *        udf_descriptor and update the udf_descriptor summed data length
 * @param desc the udf_descriptor containing the target udf_data list head
 * @param data the source udf_data list head
 * @return void
 */
void append_data(struct udf_desc *desc, struct udf_data *data)
{
	struct udf_data *ndata = desc->data;

	desc->length += data->length;

	while (ndata->next != NULL)
		ndata = ndata->next;

	ndata->next = data;
	data->prev = ndata;
}

/**
 * @brief allocate a new udf_data item and initialize it with either
 *        allocated zeros or the supplied payload
 * @param buffer the supplied payload, if NULL allocate memory for the payload
 * @param length the length of the udf_data item payload in bytes
 * @return the in-memory address of the new udf_data item
 */
struct udf_data *alloc_data(void *buffer, int length)
{
	struct udf_data *data = calloc(1, sizeof(struct udf_data));

	if (buffer)
		data->buffer = buffer;
	else if (length)
		data->buffer = calloc(1, length);
	data->length = length;

	return data;
}