ext4_utils/allocate.c

/*
 * Copyright (C) 2010 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *	  http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "allocate.h"

#include <stdio.h>
#include <stdlib.h>

#include <sparse/sparse.h>

#include "ext4_utils/ext4_utils.h"

struct xattr_list_element {
	struct ext4_inode *inode;
	struct ext4_xattr_header *header;
	struct xattr_list_element *next;
};

struct block_allocation *create_allocation()
{
	struct block_allocation *alloc = malloc(sizeof(struct block_allocation));
	alloc->list.first = NULL;
	alloc->list.last = NULL;
	alloc->oob_list.first = NULL;
	alloc->oob_list.last = NULL;
	alloc->list.iter = NULL;
	alloc->list.partial_iter = 0;
	alloc->oob_list.iter = NULL;
	alloc->oob_list.partial_iter = 0;
	alloc->filename = NULL;
	alloc->next = NULL;
	return alloc;
}

static struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode)
{
	struct xattr_list_element *element;
	for (element = aux_info.xattrs; element != NULL; element = element->next) {
		if (element->inode == inode)
			return element->header;
	}
	return NULL;
}

static void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header)
{
	struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element));
	element->inode = inode;
	element->header = header;
	element->next = aux_info.xattrs;
	aux_info.xattrs = element;
}

static void region_list_remove(struct region_list *list, struct region *reg)
{
	if (reg->prev)
		reg->prev->next = reg->next;

	if (reg->next)
		reg->next->prev = reg->prev;

	if (list->first == reg)
		list->first = reg->next;

	if (list->last == reg)
		list->last = reg->prev;

	reg->next = NULL;
	reg->prev = NULL;
}

void region_list_append(struct region_list *list, struct region *reg)
{
	if (list->first == NULL) {
		list->first = reg;
		list->last = reg;
		list->iter = reg;
		list->partial_iter = 0;
		reg->prev = NULL;
	} else {
		list->last->next = reg;
		reg->prev = list->last;
		list->last = reg;
	}
	reg->next = NULL;
}

void region_list_merge(struct region_list *list1, struct region_list *list2)
{
	if (list1->first == NULL) {
		list1->first = list2->first;
		list1->last = list2->last;
		list1->iter = list2->first;
		list1->partial_iter = 0;
		list1->first->prev = NULL;
	} else {
		list1->last->next = list2->first;
		list2->first->prev = list1->last;
		list1->last = list2->last;
	}
}
#if 0
static void dump_starting_from(struct region *reg)
{
	for (; reg; reg = reg->next) {
		printf("%p: Blocks %d-%d (%d)\n", reg,
			   reg->block, reg->block + reg->len - 1, reg->len)
	}
}

static void dump_region_lists(struct block_allocation *alloc) {

	printf("Main list:\n");
	dump_starting_from(alloc->list.first);

	printf("OOB list:\n");
	dump_starting_from(alloc->oob_list.first);
}
#endif

void print_blocks(FILE* f, struct block_allocation *alloc, char separator)
{
	struct region *reg;
	fputc(' ', f);
	for (reg = alloc->list.first; reg; reg = reg->next) {
		if (reg->len == 1) {
			fprintf(f, "%d", reg->block);
		} else {
			fprintf(f, "%d-%d", reg->block, reg->block + reg->len - 1);
		}
		fputc(separator, f);
	}
	fputc('\n', f);
}

void append_region(struct block_allocation *alloc,
		u32 block, u32 len, int bg_num)
{
	struct region *reg;
	reg = malloc(sizeof(struct region));
	reg->block = block;
	reg->len = len;
	reg->bg = bg_num;
	reg->next = NULL;

	region_list_append(&alloc->list, reg);
}

static void allocate_bg_inode_table(struct block_group_info *bg)
{
	if (bg->inode_table != NULL)
		return;

	u32 block = bg->first_block + 2;

	if (bg->has_superblock)
		block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1;

	bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size);
	if (bg->inode_table == NULL)
		critical_error_errno("calloc");

	sparse_file_add_data(ext4_sparse_file, bg->inode_table,
			aux_info.inode_table_blocks	* info.block_size, block);

	bg->flags &= ~EXT4_BG_INODE_UNINIT;
}

static int bitmap_set_bit(u8 *bitmap, u32 bit)
{
	if (bitmap[bit / 8] & 1 << (bit % 8))
		return 1;

	bitmap[bit / 8] |= 1 << (bit % 8);
	return 0;
}

static int bitmap_set_8_bits(u8 *bitmap, u32 bit)
{
	int ret = bitmap[bit / 8];
	bitmap[bit / 8] = 0xFF;
	return ret;
}

/* Marks a the first num_blocks blocks in a block group as used, and accounts
 for them in the block group free block info. */
static int reserve_blocks(struct block_group_info *bg, u32 bg_num, u32 start, u32 num)
{
	unsigned int i = 0;

	u32 block = start;
	for (i = 0; i < num && block % 8 != 0; i++, block++) {
		if (bitmap_set_bit(bg->block_bitmap, block)) {
			error("attempted to reserve already reserved block %d in block group %d", block, bg_num);
			return -1;
		}
	}

	for (; i + 8 <= (num & ~7); i += 8, block += 8) {
		if (bitmap_set_8_bits(bg->block_bitmap, block)) {
			error("attempted to reserve already reserved block %d in block group %d", block, bg_num);
			return -1;
		}
	}

	for (; i < num; i++, block++) {
		if (bitmap_set_bit(bg->block_bitmap, block)) {
			error("attempted to reserve already reserved block %d in block group %d", block, bg_num);
			return -1;
		}
	}

	bg->free_blocks -= num;

	return 0;
}

static void free_blocks(struct block_group_info *bg, u32 block, u32 num_blocks)
{
	unsigned int i;
	for (i = 0; i < num_blocks; i++, block--)
		bg->block_bitmap[block / 8] &= ~(1 << (block % 8));
	bg->free_blocks += num_blocks;
	for (i = bg->chunk_count; i > 0 ;) {
		--i;
		if (bg->chunks[i].len >= num_blocks && bg->chunks[i].block <= block) {
			if (bg->chunks[i].block == block) {
				bg->chunks[i].block += num_blocks;
				bg->chunks[i].len -= num_blocks;
			} else if (bg->chunks[i].block + bg->chunks[i].len - 1 == block + num_blocks) {
				bg->chunks[i].len -= num_blocks;
			}
			break;
		}
	}
}

/* Reduces an existing allocation by len blocks by return the last blocks
   to the free pool in their block group. Assumes that the blocks being
   returned were the last ones allocated out of the block group */
void reduce_allocation(struct block_allocation *alloc, u32 len)
{
	while (len) {
		struct region *last_reg = alloc->list.last;
		struct block_group_info *bg = &aux_info.bgs[last_reg->bg];

		if (last_reg->len > len) {
			free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, len);
			last_reg->len -= len;
			len = 0;
		} else {
			struct region *reg = alloc->list.last->prev;
			free_blocks(bg, last_reg->block + last_reg->len - bg->first_block - 1, last_reg->len);
			len -= last_reg->len;
			if (reg) {
				reg->next = NULL;
			} else {
				alloc->list.first = NULL;
				alloc->list.last = NULL;
				alloc->list.iter = NULL;
				alloc->list.partial_iter = 0;
			}
			free(last_reg);
		}
	}
}

static void init_bg(struct block_group_info *bg, unsigned int i)
{
	int header_blocks = 2 + aux_info.inode_table_blocks;

	bg->has_superblock = ext4_bg_has_super_block(i);

	if (bg->has_superblock)
		header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks;

	bg->bitmaps = calloc(info.block_size, 2);
	bg->block_bitmap = bg->bitmaps;
	bg->inode_bitmap = bg->bitmaps + info.block_size;

	bg->header_blocks = header_blocks;
	bg->first_block = aux_info.first_data_block + i * info.blocks_per_group;

	u32 block = bg->first_block;
	if (bg->has_superblock)
		block += 1 + aux_info.bg_desc_blocks +  info.bg_desc_reserve_blocks;
	sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size,
			block);

	bg->data_blocks_used = 0;
	bg->free_blocks = info.blocks_per_group;
	bg->free_inodes = info.inodes_per_group;
	bg->first_free_inode = 1;
	bg->flags = EXT4_BG_INODE_UNINIT;

	bg->chunk_count = 0;
	bg->max_chunk_count = 1;
	bg->chunks = (struct region*) calloc(bg->max_chunk_count, sizeof(struct region));

	if (reserve_blocks(bg, i, 0, bg->header_blocks) < 0)
		error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i);
	// Add empty starting delimiter chunk
	reserve_bg_chunk(i, bg->header_blocks, 0);

	if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) {
		u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks;
		reserve_blocks(bg, i, info.blocks_per_group - overrun, overrun);
		// Add empty ending delimiter chunk
		reserve_bg_chunk(i, info.blocks_per_group - overrun, 0);
	} else {
		reserve_bg_chunk(i, info.blocks_per_group - 1, 0);
	}

}

void block_allocator_init()
{
	unsigned int i;

	aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups);
	if (aux_info.bgs == NULL)
		critical_error_errno("calloc");

	for (i = 0; i < aux_info.groups; i++)
		init_bg(&aux_info.bgs[i], i);
}

void block_allocator_free()
{
	unsigned int i;

	for (i = 0; i < aux_info.groups; i++) {
		free(aux_info.bgs[i].bitmaps);
		free(aux_info.bgs[i].inode_table);
	}
	free(aux_info.bgs);
}

/* Allocate a single block and return its block number */
u32 allocate_block()
{
	u32 block;
	struct block_allocation *blk_alloc = allocate_blocks(1);
	if (!blk_alloc) {
		return EXT4_ALLOCATE_FAILED;
	}
	block = blk_alloc->list.first->block;
	free_alloc(blk_alloc);
	return block;
}

static struct region *ext4_allocate_best_fit_partial(u32 len)
{
	unsigned int i;
	int j;
	unsigned int found_bg = 0, found_prev_chunk = 0, found_block = 0;
	u32 found_allocate_len = 0;
	bool minimize = false;
	struct block_group_info *bgs = aux_info.bgs;
	struct region *reg;

	for (i = 0; i < aux_info.groups; i++) {
		for (j = 1; j < bgs[i].chunk_count; j++) {
			u32 hole_start, hole_size;
			hole_start = bgs[i].chunks[j-1].block + bgs[i].chunks[j-1].len;
			hole_size =  bgs[i].chunks[j].block - hole_start;
			if (hole_size == len) {
				// Perfect fit i.e. right between 2 chunks no need to keep searching
				found_bg = i;
				found_prev_chunk = j - 1;
				found_block = hole_start;
				found_allocate_len = hole_size;
				goto done;
			} else if (hole_size > len && (found_allocate_len == 0 || (found_allocate_len > hole_size))) {
				found_bg = i;
				found_prev_chunk = j - 1;
				found_block = hole_start;
				found_allocate_len = hole_size;
				minimize = true;
			} else if (!minimize) {
				if (found_allocate_len < hole_size) {
					found_bg = i;
					found_prev_chunk = j - 1;
					found_block = hole_start;
					found_allocate_len = hole_size;
				}
			}
		}
	}

	if (found_allocate_len == 0) {
		error("failed to allocate %u blocks, out of space?", len);
		return NULL;
	}
	if (found_allocate_len > len) found_allocate_len = len;
done:
	// reclaim allocated space in chunk
	bgs[found_bg].chunks[found_prev_chunk].len += found_allocate_len;
	if (reserve_blocks(&bgs[found_bg],
				found_bg,
				found_block,
				found_allocate_len) < 0) {
		error("failed to reserve %u blocks in block group %u\n", found_allocate_len, found_bg);
		return NULL;
	}
	bgs[found_bg].data_blocks_used += found_allocate_len;
	reg = malloc(sizeof(struct region));
	reg->block = found_block + bgs[found_bg].first_block;
	reg->len = found_allocate_len;
	reg->next = NULL;
	reg->prev = NULL;
	reg->bg = found_bg;
	return reg;
}

static struct region *ext4_allocate_best_fit(u32 len)
{
	struct region *first_reg = NULL;
	struct region *prev_reg = NULL;
	struct region *reg;

	while (len > 0) {
		reg = ext4_allocate_best_fit_partial(len);
		if (reg == NULL)
			return NULL;

		if (first_reg == NULL)
			first_reg = reg;

		if (prev_reg) {
			prev_reg->next = reg;
			reg->prev = prev_reg;
		}

		prev_reg = reg;
		len -= reg->len;
	}

	return first_reg;
}

/* Allocate len blocks.  The blocks may be spread across multiple block groups,
   and are returned in a linked list of the blocks in each block group.  The
   allocation algorithm is:
	  1.  If the remaining allocation is larger than any available contiguous region,
		  allocate the largest contiguous region and loop
	  2.  Otherwise, allocate the smallest contiguous region that it fits in
*/
struct block_allocation *allocate_blocks(u32 len)
{
	struct region *reg = ext4_allocate_best_fit(len);

	if (reg == NULL)
		return NULL;

	struct block_allocation *alloc = create_allocation();
	alloc->list.first = reg;
	while (reg->next != NULL)
		reg = reg->next;
	alloc->list.last = reg;
	alloc->list.iter = alloc->list.first;
	alloc->list.partial_iter = 0;
	return alloc;
}

/* Returns the number of discontiguous regions used by an allocation */
int block_allocation_num_regions(struct block_allocation *alloc)
{
	unsigned int i;
	struct region *reg = alloc->list.first;

	for (i = 0; reg != NULL; reg = reg->next)
		i++;

	return i;
}

int block_allocation_len(struct block_allocation *alloc)
{
	unsigned int i;
	struct region *reg = alloc->list.first;

	for (i = 0; reg != NULL; reg = reg->next)
		i += reg->len;

	return i;
}

/* Returns the block number of the block'th block in an allocation */
u32 get_block(struct block_allocation *alloc, u32 block)
{
	struct region *reg = alloc->list.iter;
	block += alloc->list.partial_iter;

	for (; reg; reg = reg->next) {
		if (block < reg->len)
			return reg->block + block;
		block -= reg->len;
	}
	return EXT4_ALLOCATE_FAILED;
}

u32 get_oob_block(struct block_allocation *alloc, u32 block)
{
	struct region *reg = alloc->oob_list.iter;
	block += alloc->oob_list.partial_iter;

	for (; reg; reg = reg->next) {
		if (block < reg->len)
			return reg->block + block;
		block -= reg->len;
	}
	return EXT4_ALLOCATE_FAILED;
}

/* Gets the starting block and length in blocks of the first region
   of an allocation */
void get_region(struct block_allocation *alloc, u32 *block, u32 *len)
{
	*block = alloc->list.iter->block;
	*len = alloc->list.iter->len - alloc->list.partial_iter;
}

/* Move to the next region in an allocation */
void get_next_region(struct block_allocation *alloc)
{
	alloc->list.iter = alloc->list.iter->next;
	alloc->list.partial_iter = 0;
}

/* Returns the number of free blocks in a block group */
u32 get_free_blocks(u32 bg)
{
	return aux_info.bgs[bg].free_blocks;
}

int last_region(struct block_allocation *alloc)
{
	return (alloc->list.iter == NULL);
}

void rewind_alloc(struct block_allocation *alloc)
{
	alloc->list.iter = alloc->list.first;
	alloc->list.partial_iter = 0;
}

static struct region *do_split_allocation(struct block_allocation *alloc, u32 len)
{
	struct region *reg = alloc->list.iter;
	struct region *new;
	struct region *tmp;

	while (reg && len >= reg->len) {
		len -= reg->len;
		reg = reg->next;
	}

	if (reg == NULL && len > 0)
		return NULL;

	if (len > 0) {
		new = malloc(sizeof(struct region));

		new->bg = reg->bg;
		new->block = reg->block + len;
		new->len = reg->len - len;
		new->next = reg->next;
		new->prev = reg;

		reg->next = new;
		reg->len = len;

		tmp = alloc->list.iter;
		alloc->list.iter = new;
		return tmp;
	} else {
		return reg;
	}
}

/* Splits an allocation into two allocations.  The returned allocation will
   point to the first half, and the original allocation ptr will point to the
   second half. */
static struct region *split_allocation(struct block_allocation *alloc, u32 len)
{
	/* First make sure there is a split at the current ptr */
	do_split_allocation(alloc, alloc->list.partial_iter);

	/* Then split off len blocks */
	struct region *middle = do_split_allocation(alloc, len);
	alloc->list.partial_iter = 0;
	return middle;
}

/* Reserve the next blocks for oob data (indirect or extent blocks) */
int reserve_oob_blocks(struct block_allocation *alloc, int blocks)
{
	struct region *oob = split_allocation(alloc, blocks);
	struct region *next;

	if (oob == NULL)
		return -1;

	while (oob && oob != alloc->list.iter) {
		next = oob->next;
		region_list_remove(&alloc->list, oob);
		region_list_append(&alloc->oob_list, oob);
		oob = next;
	}

	return 0;
}

static int advance_list_ptr(struct region_list *list, int blocks)
{
	struct region *reg = list->iter;

	while (reg != NULL && blocks > 0) {
		if (reg->len > list->partial_iter + blocks) {
			list->partial_iter += blocks;
			return 0;
		}

		blocks -= (reg->len - list->partial_iter);
		list->partial_iter = 0;
		reg = reg->next;
	}

	if (blocks > 0)
		return -1;

	return 0;
}

/* Move the allocation pointer forward */
int advance_blocks(struct block_allocation *alloc, int blocks)
{
	return advance_list_ptr(&alloc->list, blocks);
}

int advance_oob_blocks(struct block_allocation *alloc, int blocks)
{
	return advance_list_ptr(&alloc->oob_list, blocks);
}

int append_oob_allocation(struct block_allocation *alloc, u32 len)
{
	struct region *reg = ext4_allocate_best_fit(len);

	if (reg == NULL) {
		error("failed to allocate %d blocks", len);
		return -1;
	}

	for (; reg; reg = reg->next)
		region_list_append(&alloc->oob_list, reg);

	return 0;
}

/* Returns an ext4_inode structure for an inode number */
struct ext4_inode *get_inode(u32 inode)
{
	inode -= 1;
	int bg = inode / info.inodes_per_group;
	inode %= info.inodes_per_group;

	allocate_bg_inode_table(&aux_info.bgs[bg]);
	return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode *
		info.inode_size);
}

struct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode)
{
	struct ext4_xattr_header *block = xattr_list_find(inode);
	if (block != NULL)
		return block;

	u32 block_num = allocate_block();
	block = calloc(info.block_size, 1);
	if (block == NULL) {
		error("get_xattr: failed to allocate %d", info.block_size);
		return NULL;
	}

	block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC);
	block->h_refcount = cpu_to_le32(1);
	block->h_blocks = cpu_to_le32(1);
	inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512));
	inode->i_file_acl_lo = cpu_to_le32(block_num);

	int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num);
	if (result != 0) {
		error("get_xattr: sparse_file_add_data failure %d", result);
		free(block);
		return NULL;
	}
	xattr_list_insert(inode, block);
	return block;
}

/* Mark the first len inodes in a block group as used */
u32 reserve_inodes(int bg, u32 num)
{
	unsigned int i;
	u32 inode;

	if (get_free_inodes(bg) < num)
		return EXT4_ALLOCATE_FAILED;

	for (i = 0; i < num; i++) {
		inode = aux_info.bgs[bg].first_free_inode + i - 1;
		aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8);
	}

	inode = aux_info.bgs[bg].first_free_inode;

	aux_info.bgs[bg].first_free_inode += num;
	aux_info.bgs[bg].free_inodes -= num;

	return inode;
}

/* Returns the first free inode number
   TODO: Inodes should be allocated in the block group of the data? */
u32 allocate_inode()
{
	unsigned int bg;
	u32 inode;

	for (bg = 0; bg < aux_info.groups; bg++) {
		inode = reserve_inodes(bg, 1);
		if (inode != EXT4_ALLOCATE_FAILED)
			return bg * info.inodes_per_group + inode;
	}

	return EXT4_ALLOCATE_FAILED;
}

/* Returns the number of free inodes in a block group */
u32 get_free_inodes(u32 bg)
{
	return aux_info.bgs[bg].free_inodes;
}

/* Increments the directory count of the block group that contains inode */
void add_directory(u32 inode)
{
	int bg = (inode - 1) / info.inodes_per_group;
	aux_info.bgs[bg].used_dirs += 1;
}

/* Returns the number of inodes in a block group that are directories */
u16 get_directories(int bg)
{
	return aux_info.bgs[bg].used_dirs;
}

/* Returns the flags for a block group */
u16 get_bg_flags(int bg)
{
	return aux_info.bgs[bg].flags;
}

/* Frees the memory used by a linked list of allocation regions */
void free_alloc(struct block_allocation *alloc)
{
	struct region *reg;

	reg = alloc->list.first;
	while (reg) {
		struct region *next = reg->next;
		free(reg);
		reg = next;
	}

	reg = alloc->oob_list.first;
	while (reg) {
		struct region *next = reg->next;
		free(reg);
		reg = next;
	}

	free(alloc);
}

void reserve_bg_chunk(int bg, u32 start_block, u32 size) {
	struct block_group_info *bgs = aux_info.bgs;
	int chunk_count;
	if (bgs[bg].chunk_count == bgs[bg].max_chunk_count) {
		bgs[bg].max_chunk_count *= 2;
		bgs[bg].chunks = realloc(bgs[bg].chunks, bgs[bg].max_chunk_count * sizeof(struct region));
		if (!bgs[bg].chunks)
			critical_error("realloc failed");
	}
	chunk_count = bgs[bg].chunk_count;
	bgs[bg].chunks[chunk_count].block = start_block;
	bgs[bg].chunks[chunk_count].len = size;
	bgs[bg].chunks[chunk_count].bg = bg;
	bgs[bg].chunk_count++;
}

int reserve_blocks_for_allocation(struct block_allocation *alloc) {
	struct region *reg;
	struct block_group_info *bgs = aux_info.bgs;

	if (!alloc) return 0;
	reg = alloc->list.first;
	while (reg != NULL) {
		if (reserve_blocks(&bgs[reg->bg], reg->bg, reg->block - bgs[reg->bg].first_block, reg->len) < 0) {
			return -1;
		}
		reg = reg->next;
	}
	return 0;
}