blob: be721ee2d20be75785d0e0dfe78b9da466dfd145 [file] [log] [blame] [edit]
/*
* Copyright (C) 2015 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 <assert.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
#include "block_allocator.h"
#include "debug.h"
#include "transaction.h"
/*
* BLOCK_ALLOCATOR_QUEUE_LEN:
* Queue length large enough for a worst case tree update, e.g. update of a tree
* where each entry needs to be copied then split.
*/
#define BLOCK_ALLOCATOR_QUEUE_LEN \
(BLOCK_SET_MAX_DEPTH * 2 * BLOCK_SET_MAX_DEPTH * 2)
/**
* struct block_allocator_queue_entry - pending block allocation set update
* @block: block number to free or allocate.
* @tmp: is_tmp value passed to block_allocate_etc or block_free_etc.
* @free: @block is free.
* @removed: queue entry was removed.
*/
struct block_allocator_queue_entry {
data_block_t block;
bool tmp;
bool free;
bool removed;
};
/**
* struct block_allocator_queue - queue of pending block allocation set updates
* @entry: Ring buffer.
* @head Index in @entry of first (oldest) entry in queue.
* @tail: Index in @entry where next entry should be inserted.
* @updating: %true while updating sets, false otherwise.
*/
struct block_allocator_queue {
struct block_allocator_queue_entry entry[BLOCK_ALLOCATOR_QUEUE_LEN];
unsigned int head;
unsigned int tail;
bool updating;
};
/**
* block_allocator_queue_empty - Check if block allocator queue is empty
* @q: Queue object.
*
* Return: %true if @q is empty, %false otherwise.
*/
static bool block_allocator_queue_empty(struct block_allocator_queue* q) {
assert(q->head < countof(q->entry));
assert(q->tail < countof(q->entry));
return q->head == q->tail;
}
/**
* block_allocator_queue_count - Get number of entries in block allocator queue
* @q: Queue object.
*
* Return: number of etnries in @q.
*/
static unsigned int block_allocator_queue_count(
struct block_allocator_queue* q) {
return (q->tail + countof(q->entry) - q->head) % countof(q->entry);
}
/**
* block_allocator_queue_find - Search block allocator queue
* @q: Queue object.
* @block: Block number to search for.
*
* Return: If block is in @q index in @q->entry of matching entry, -1 if @block
* is not in @q.
*/
static int block_allocator_queue_find(struct block_allocator_queue* q,
data_block_t block) {
unsigned int i;
assert(q->head < countof(q->entry));
assert(q->tail < countof(q->entry));
for (i = q->head; i != q->tail; i = (i + 1) % countof(q->entry)) {
if (q->entry[i].removed) {
continue;
}
if (block == q->entry[i].block) {
return i;
}
}
return -1;
}
/**
* block_allocator_queue_add_removed - Add a removed entry to block allocator
* queue
* @q: Queue object.
*
* Add a removed entry to @q to make it non-empty.
*/
static void block_allocator_queue_add_removed(struct block_allocator_queue* q) {
assert(block_allocator_queue_empty(q));
unsigned int new_tail = (q->tail + 1) % countof(q->entry);
q->entry[q->tail].removed = true;
q->tail = new_tail;
pr_write("index %d\n", q->tail);
}
/**
* block_allocator_queue_add - Add a entry to block allocator queue
* @q: Queue object.
* @block: block number to free or allocate.
* @is_tmp: is_tmp value passed to block_allocate_etc or block_free_etc.
* @is_free: @block is free.
*/
static void block_allocator_queue_add(struct block_allocator_queue* q,
data_block_t block,
bool is_tmp,
bool is_free) {
int ret;
unsigned int index;
unsigned int new_tail;
ret = block_allocator_queue_find(q, block);
if (ret >= 0) {
index = ret;
assert(index < countof(q->entry));
assert(q->entry[index].tmp == is_tmp);
assert(q->entry[index].free != is_free);
q->entry[index].removed = true;
if (index != q->head || !q->updating) {
return;
}
pr_warn("block %" PRIu64
", tmp %d, free %d, removed head during update\n",
block, is_tmp, is_free);
}
new_tail = (q->tail + 1) % countof(q->entry);
assert(q->head < countof(q->entry));
assert(q->tail < countof(q->entry));
assert(new_tail < countof(q->entry));
assert(new_tail != q->head);
q->entry[q->tail].block = block;
assert(q->entry[q->tail].block == block);
q->entry[q->tail].tmp = is_tmp;
q->entry[q->tail].free = is_free;
q->entry[q->tail].removed = false;
q->tail = new_tail;
pr_write("block %" PRIu64 ", tmp %d, free %d, index %d (rel %d)\n", block,
is_tmp, is_free, q->tail, block_allocator_queue_count(q));
}
/**
* block_allocator_queue_peek_head - Get head block allocator queue entry
* @q: Queue object.
*
* Return: entry at head of @q.
*/
static struct block_allocator_queue_entry block_allocator_queue_peek_head(
struct block_allocator_queue* q) {
assert(!block_allocator_queue_empty(q));
return q->entry[q->head];
}
/**
* block_allocator_queue_remove_head - Remove head block allocator queue entry
* @q: Queue object.
* @entry: Entry that should be at head of @q (used for validation only).
*/
static void block_allocator_queue_remove_head(
struct block_allocator_queue* q,
struct block_allocator_queue_entry entry) {
assert(block_allocator_queue_peek_head(q).block == entry.block);
pr_write("index %d, count %d\n", q->head, block_allocator_queue_count(q));
q->head = (q->head + 1) % countof(q->entry);
}
/**
* block_allocator_queue_find_free_block - Search allocator queue for free block
* @q: Queue object.
* @block: Block number to search for.
*
* Return: First block >= @block that is not in @q as an allocated block.
*/
static data_block_t block_allocator_queue_find_free_block(
struct block_allocator_queue* q,
data_block_t block) {
int index;
while (true) {
index = block_allocator_queue_find(q, block);
if (index < 0) {
return block;
}
if (q->entry[index].free) {
return block;
}
block++;
}
}
static struct block_allocator_queue block_allocator_queue;
/**
* find_free_block - Search for a free block
* @tr: Transaction object.
* @min_block_in: Block number to start search at.
*
* Return: Block number that is in all committed free sets and not already
* allocated by any transaction. To be considered free, a block must be in the
* current file-system free set AND any checkpointed free sets, if available.
*/
static data_block_t find_free_block(struct transaction* tr,
data_block_t min_block_in) {
data_block_t block;
data_block_t min_block = min_block_in;
struct block_set* set;
if (!fs_is_writable(tr->fs)) {
printf("Read-only filesystem tried to allocate a free block\n");
if (!tr->failed) {
transaction_fail(tr);
}
return 0;
}
assert(list_in_list(&tr->node)); /* transaction must be active */
pr_read("min_block %" PRIu64 "\n", min_block);
block = min_block;
do {
block = block_set_find_next_block(tr, &tr->fs->free, block, true);
if (tr->failed) {
return 0;
}
/*
* if block_set_find_next_block() returns 0, there was no available free
* block after min_block
*/
if (!block) {
break;
}
assert(block >= min_block);
/*
* set min_block to a candidate for an available free block. If no
* checkpoint or pending allocation contains this block, block will
* still equal min_block and we will exit the loop
*/
min_block = block;
pr_read("check free block %" PRIu64 "\n", block);
/* check if the block is also free in the checkpoint */
block = block_set_find_next_block(tr, &tr->fs->checkpoint_free, block,
true);
if (tr->failed) {
return 0;
}
if (!block) {
break;
}
assert(block >= min_block);
assert(!list_is_empty(&tr->fs->allocated));
list_for_every_entry(&tr->fs->allocated, set, struct block_set, node) {
block = block_set_find_next_block(tr, set, block, false);
if (tr->failed) {
return 0;
}
assert(block >= min_block);
};
block = block_allocator_queue_find_free_block(&block_allocator_queue,
block);
assert(block >= min_block);
} while (block != min_block);
if (!block) {
if (LOCAL_TRACE >= TRACE_LEVEL_READ) {
if (min_block_in) {
block = find_free_block(tr, 0);
}
printf("%s: no space, min_block %" PRIu64
", free block ignoring_min_block %" PRIu64 "\n",
__func__, min_block_in, block);
printf("%s: free\n", __func__);
block_set_print(tr, &tr->fs->free);
printf("%s: checkpoint free\n", __func__);
block_set_print(tr, &tr->fs->checkpoint_free);
list_for_every_entry(&tr->fs->allocated, set, struct block_set,
node) {
#if TLOG_LVL >= TLOG_LVL_DEBUG
printf("%s: allocated %p\n", __func__, set);
#endif
block_set_print(tr, set);
}
if (tr->new_free_set) {
printf("%s: new free\n", __func__);
block_set_print(tr, tr->new_free_set);
}
}
return 0;
}
pr_read("found free block %" PRIu64 "\n", block);
return block;
}
/**
* block_allocate_etc - Allocate a block
* @tr: Transaction object.
* @is_tmp: %true if allocated block should be automatically freed when
* transaction completes, %false if allocated block should be added
* to free set when transaction completes.
*
* Find a free block and add queue a set update.
*
* Return: Allocated block number.
*/
data_block_t block_allocate_etc(struct transaction* tr, bool is_tmp) {
data_block_t block;
data_block_t min_block;
bool update_sets;
if (tr->failed) {
pr_warn("transaction failed, abort\n");
return 0;
}
assert(transaction_is_active(tr));
/* TODO: group allocations by set */
update_sets = block_allocator_queue_empty(&block_allocator_queue);
if (update_sets) {
tr->last_tmp_free_block = tr->fs->dev->block_count / 4 * 3;
tr->last_free_block = 0;
}
min_block = is_tmp ? tr->last_tmp_free_block : tr->last_free_block;
block = find_free_block(tr, min_block);
if (!block) {
block = find_free_block(tr, 0);
if (!block) {
if (!tr->failed) {
pr_err("no space\n");
transaction_fail(tr);
}
return 0;
}
}
block_allocator_queue_add(&block_allocator_queue, block, is_tmp, false);
full_assert(find_free_block(tr, block) != block);
if (update_sets) {
block_allocator_process_queue(tr);
}
full_assert(tr->failed || find_free_block(tr, block) != block);
if (tr->failed) {
return 0;
}
return block;
}
/**
* block_allocator_add_allocated - Update block sets with new allocated block
* @tr: Transaction object.
* @block: Block that was allocated.
* @is_tmp: %true if allocated block should be automatically freed when
* transaction completes, %false if allocated block should be added
* to free set when transaction completes.
*
* Add @block to the allocated set selected by @is_tmp. If called while
* completing the transaction update the new free set directly if needed.
*/
static void block_allocator_add_allocated(struct transaction* tr,
data_block_t block,
bool is_tmp) {
if (is_tmp) {
pr_write("add %" PRIu64 " to tmp_allocated\n", block);
block_set_add_block(tr, &tr->tmp_allocated, block);
tr->last_tmp_free_block = block + 1;
} else {
pr_write("add %" PRIu64 " to allocated\n", block);
block_set_add_block(tr, &tr->allocated, block);
if (block < tr->min_free_block) {
pr_write("remove %" PRIu64 " from new_free_set\n", block);
assert(tr->new_free_set);
block_set_remove_block(tr, tr->new_free_set, block);
tr->last_free_block = block + 1;
}
}
}
/**
* block_free_etc - Free a block
* @tr: Transaction object.
* @block: Block that should be freed.
* @is_tmp: Must match is_tmp value passed to block_allocate_etc (always
* %false if @block was not allocated by this transaction).
*/
void block_free_etc(struct transaction* tr, data_block_t block, bool is_tmp) {
bool update_sets = block_allocator_queue_empty(&block_allocator_queue);
assert(block_is_clean(tr->fs->dev, block));
block_allocator_queue_add(&block_allocator_queue, block, is_tmp, true);
if (update_sets) {
block_allocator_process_queue(tr);
}
}
/**
* block_allocator_add_free - Update block sets with new free block
* @tr: Transaction object.
* @block: Block that should be freed.
* @is_tmp: Must match is_tmp value passed to block_allocate_etc (always
* %false if @block was not allocated by this transaction).
*
* If @block was allocated in this transaction, remove it from the allocated set
* (selected by @is_tmp). Otherwise add it to the set of blocks to remove when
* transaction completes. If called while completing the transaction update the
* new free set directly if needed.
*/
static void block_allocator_add_free(struct transaction* tr,
data_block_t block,
bool is_tmp) {
assert(block_is_clean(tr->fs->dev, block));
if (is_tmp) {
assert(!block_set_block_in_set(tr, &tr->allocated, block));
assert(!block_set_block_in_set(tr, &tr->freed, block));
pr_write("remove %" PRIu64 " from tmp_allocated\n", block);
block_set_remove_block(tr, &tr->tmp_allocated, block);
return;
}
assert(!block_set_block_in_set(tr, &tr->tmp_allocated, block));
if (block_set_block_in_set(tr, &tr->allocated, block)) {
pr_write("remove %" PRIu64 " from allocated\n", block);
block_set_remove_block(tr, &tr->allocated, block);
if (block < tr->min_free_block) {
pr_write("add %" PRIu64 " to new_free_root\n", block);
assert(tr->new_free_set);
block_set_add_block(tr, tr->new_free_set, block);
}
} else {
if (block < tr->min_free_block) {
pr_write("add %" PRIu64 " to new_free_root\n", block);
assert(tr->new_free_set);
block_set_add_block(tr, tr->new_free_set, block);
} else {
pr_write("add %" PRIu64 " to freed\n", block);
block_set_add_block(tr, &tr->freed, block);
}
}
}
/**
* block_allocator_suspend_set_updates - Prevent set updates
* @tr: Transaction object.
*/
void block_allocator_suspend_set_updates(struct transaction* tr) {
block_allocator_queue_add_removed(&block_allocator_queue);
}
/**
* block_allocator_allocation_queued - Check for queued block allocation
* @tr: Transaction object.
* @block: Block to serach for.
* @is_tmp: is_tmp value passed to block_allocate_etc.
*
* Return: %true if a block matching @block, @is_tmp and !free is in the
* block allocator queue, %false otherwise.
*/
bool block_allocator_allocation_queued(struct transaction* tr,
data_block_t block,
bool is_tmp) {
int index;
index = block_allocator_queue_find(&block_allocator_queue, block);
return index >= 0 && block_allocator_queue.entry[index].tmp == is_tmp &&
!block_allocator_queue.entry[index].free;
}
/**
* block_allocator_process_queue - Process all block allocator queue entries
* @tr: Transaction object.
*/
void block_allocator_process_queue(struct transaction* tr) {
struct block_allocator_queue_entry entry;
int loop_limit =
BLOCK_SET_MAX_DEPTH * BLOCK_SET_MAX_DEPTH * BLOCK_SET_MAX_DEPTH +
tr->fs->dev->block_count;
assert(!block_allocator_queue.updating);
block_allocator_queue.updating = true;
while (!block_allocator_queue_empty(&block_allocator_queue)) {
assert(loop_limit-- > 0);
entry = block_allocator_queue_peek_head(&block_allocator_queue);
pr_write("block %" PRIu64 ", tmp %d, free %d, removed %d\n",
(data_block_t)entry.block, entry.tmp, entry.free,
entry.removed);
if (entry.removed) {
} else if (entry.free) {
block_allocator_add_free(tr, entry.block, entry.tmp);
} else {
block_allocator_add_allocated(tr, entry.block, entry.tmp);
}
block_allocator_queue_remove_head(&block_allocator_queue, entry);
}
block_allocator_queue.updating = false;
}