path: root/base/address_space.h

// Copyright 2018 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.
#pragma once

#include <assert.h>
#include <errno.h>
#include <inttypes.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#ifdef ADDRESS_SPACE_NAMESPACE
namespace ADDRESS_SPACE_NAMESPACE {
#endif

// This is ported from goldfish_address_space, allowing it to be used for
// general sub-allocations of any buffer range.
// It is also a pure header library, so there are no compiler tricks needed
// to use this in a particular implementation. please don't include this
// in a file that is included everywhere else, though.

/* Represents a continuous range of addresses and a flag if this block is
 * available
 */
struct address_block {
    uint64_t offset;
    union {
        uint64_t size_available; /* VMSTATE_x does not support bit fields */
        struct {
            uint64_t size : 63;
            uint64_t available : 1;
        };
    };
};

/* A dynamic array of address blocks, with the following invariant:
 * blocks[i].size > 0
 * blocks[i+1].offset = blocks[i].offset + blocks[i].size
 */
struct address_space_allocator {
    struct address_block *blocks;
    int size;
    int capacity;
    uint64_t total_bytes;
};

#define ANDROID_EMU_ADDRESS_SPACE_BAD_OFFSET (~(uint64_t)0)
#if defined(__APPLE__) && defined(__arm64__)
#define ANDROID_EMU_ADDRESS_SPACE_DEFAULT_PAGE_SIZE 16384
#else
#define ANDROID_EMU_ADDRESS_SPACE_DEFAULT_PAGE_SIZE 4096
#endif

/* The assert function to abort if something goes wrong. */
static void address_space_assert(bool condition) {
#ifdef ANDROID_EMU_ADDRESS_SPACE_ASSERT_FUNC
    ANDROID_EMU_ADDRESS_SPACE_ASSERT_FUNC(condition);
#else
    assert(condition);
#endif
}

static void* address_space_realloc(void* ptr, size_t size) {
#ifdef ANDROID_EMU_ADDRESS_SPACE_REALLOC_FUNC
    return ANDROID_EMU_ADDRESS_SPACE_REALLOC_FUNC(ptr, size);
#else
    void* res = realloc(ptr, size);
    return res;
#endif
}

static void address_space_free(void* ptr) {
#ifdef ANDROID_EMU_ADDRESS_SPACE_FREE_FUNC
    return ANDROID_EMU_ADDRESS_SPACE_FREE_FUNC(ptr);
#else
    free(ptr);
#endif
}

/* Looks for the smallest (to reduce fragmentation) available block with size to
 * fit the requested amount and returns its index or -1 if none is available.
 */
static int address_space_allocator_find_available_block(
    struct address_block *block,
    int n_blocks,
    uint64_t size_at_least)
{
    int index = -1;
    uint64_t size_at_index = 0;
    int i;

    address_space_assert(n_blocks >= 1);

    for (i = 0; i < n_blocks; ++i, ++block) {
        uint64_t this_size = block->size;
        address_space_assert(this_size > 0);

        if (this_size >= size_at_least && block->available &&
            (index < 0 || this_size < size_at_index)) {
            index = i;
            size_at_index = this_size;
        }
    }

    return index;
}

static int address_space_allocator_find_available_block_at_offset(
    struct address_block *block,
    int n_blocks,
    uint64_t size_at_least,
    uint64_t offset)
{
    int index = -1;
    uint64_t size_at_index = 0;
    int i;

    address_space_assert(n_blocks >= 1);

    for (i = 0; i < n_blocks; ++i, ++block) {
        uint64_t this_size = block->size;
        address_space_assert(this_size > 0);

        if (this_size >= size_at_least && block->available &&
            offset >= block->offset &&
            offset < block->offset + this_size) {
            index = i;
            size_at_index = this_size;
            return index;
        }
    }

    return index;
}

static int
address_space_allocator_grow_capacity(int old_capacity) {
    address_space_assert(old_capacity >= 1);

    return old_capacity + old_capacity;
}

/* Inserts one more address block right after i'th (by borrowing i'th size) and
 * adjusts sizes:
 * pre:
 *   size > blocks[i].size
 *
 * post:
 *   * might reallocate allocator->blocks if there is no capacity to insert one
 *   * blocks[i].size -= size;
 *   * blocks[i+1].size = size;
 */
static struct address_block*
address_space_allocator_split_block(
    struct address_space_allocator *allocator,
    int i,
    uint64_t size)
{
    address_space_assert(allocator->capacity >= 1);
    address_space_assert(allocator->size >= 1);
    address_space_assert(allocator->size <= allocator->capacity);
    address_space_assert(i >= 0);
    address_space_assert(i < allocator->size);
    address_space_assert(size < allocator->blocks[i].size);

    if (allocator->size == allocator->capacity) {
        int new_capacity = address_space_allocator_grow_capacity(allocator->capacity);
        allocator->blocks =
            (struct address_block*)
            address_space_realloc(
                allocator->blocks,
                sizeof(struct address_block) * new_capacity);
        address_space_assert(allocator->blocks);
        allocator->capacity = new_capacity;
    }

    struct address_block *blocks = allocator->blocks;

    /*   size = 5, i = 1
     *   [ 0 | 1 |  2  |  3  | 4 ]  =>  [ 0 | 1 | new |  2  | 3 | 4 ]
     *         i  (i+1) (i+2)                 i  (i+1) (i+2)
     */
    memmove(&blocks[i + 2], &blocks[i + 1],
            sizeof(struct address_block) * (allocator->size - i - 1));

    struct address_block *to_borrow_from = &blocks[i];
    struct address_block *new_block = to_borrow_from + 1;

    uint64_t new_size = to_borrow_from->size - size;

    to_borrow_from->size = new_size;

    new_block->offset = to_borrow_from->offset + new_size;
    new_block->size = size;
    new_block->available = 1;

    ++allocator->size;

    return new_block;
}

/* Inserts one more address block right after i'th (by borrowing i'th size) and
 * adjusts sizes:
 * pre:
 *   size < blocks[i].size
 *   offset >= blocks[i].offset
 *   offset < blocks[i].offset + blocks[i].size
 *
 * post:
 *   * might reallocate allocator->blocks if there is no capacity to insert one
 *   * blocks[i].size = offset - blocks[i].offset;
 *   * blocks[i+1].size = offset;
 *   * blocks[i+1].offset = offset;
 */
static struct address_block*
address_space_allocator_split_block_at_offset(
    struct address_space_allocator *allocator,
    int i,
    uint64_t size,
    uint64_t offset)
{
    uint64_t old_block_size;
    bool need_extra_block;
    int new_block_index_offset;

    address_space_assert(allocator->capacity >= 1);
    address_space_assert(allocator->size >= 1);
    address_space_assert(allocator->size <= allocator->capacity);
    address_space_assert(i >= 0);
    address_space_assert(i < allocator->size);
    address_space_assert(size < allocator->blocks[i].size);

    need_extra_block =
        (allocator->blocks[i].size - size - (offset - allocator->blocks[i].offset)) != 0;
    new_block_index_offset = need_extra_block ? 1 : 0;

    if (allocator->size + new_block_index_offset >= allocator->capacity) {
        int new_capacity = address_space_allocator_grow_capacity(allocator->capacity + new_block_index_offset);
        allocator->blocks =
            (struct address_block*)
            address_space_realloc(
                allocator->blocks,
                sizeof(struct address_block) * new_capacity);
        address_space_assert(allocator->blocks);
        allocator->capacity = new_capacity;
    }

    struct address_block *blocks = allocator->blocks;

    /*   size = 5, i = 1
     *   [ 0 | 1 |  2  |  3  | 4 ]  =>  [ 0 | 1 | new |  new(for slop)  | 2    | 3 | 4]
     *         i  (i+1) (i+2)                 i  (i+1) (i+2)              (i+3) 
     */
    memmove(&blocks[i + 2 + new_block_index_offset], &blocks[i + 1],
            sizeof(struct address_block) * (allocator->size - i - 1));

    struct address_block *to_borrow_from = &blocks[i];
    struct address_block *new_block = to_borrow_from + 1;
    struct address_block *extra_block = to_borrow_from + 2;

    old_block_size = to_borrow_from->size;
    to_borrow_from->size = offset - to_borrow_from->offset;

    new_block->offset = offset;
    new_block->size = size;
    new_block->available = 1;

    ++allocator->size;

    if (need_extra_block) {
        extra_block->offset = offset + size;
        extra_block->size = old_block_size - size - to_borrow_from->size;
        extra_block->available = 1;

        ++allocator->size;
    }

    return new_block;
}

/* Marks i'th block as available. If adjacent ((i-1) and (i+1)) blocks are also
 * available, it merges i'th block with them.
 * pre:
 *   i < allocator->size
 * post:
 *   i'th block is merged with adjacent ones if they are available, blocks that
 *   were merged from are removed. allocator->size is updated if blocks were
 *   removed.
 */
static void address_space_allocator_release_block(
    struct address_space_allocator *allocator,
    int i)
{
    struct address_block *blocks = allocator->blocks;
    int before = i - 1;
    int after = i + 1;
    int size = allocator->size;

    address_space_assert(i >= 0);
    address_space_assert(i < size);

    blocks[i].available = 1;

    if (before >= 0 && blocks[before].available) {
        if (after < size && blocks[after].available) {
            // merge (before, i, after) into before
            blocks[before].size += (blocks[i].size + blocks[after].size);

            size -= 2;
            memmove(&blocks[i], &blocks[i + 2],
                sizeof(struct address_block) * (size - i));
            allocator->size = size;
        } else {
            // merge (before, i) into before
            blocks[before].size += blocks[i].size;

            --size;
            memmove(&blocks[i], &blocks[i + 1],
                sizeof(struct address_block) * (size - i));
            allocator->size = size;
        }
    } else if (after < size && blocks[after].available) {
        // merge (i, after) into i
        blocks[i].size += blocks[after].size;

        --size;
        memmove(&blocks[after], &blocks[after + 1],
            sizeof(struct address_block) * (size - after));
        allocator->size = size;
    }

}

/* Takes a size to allocate an address block and returns an offset where this
 * block is allocated. This block will not be available for other callers unless
 * it is explicitly deallocated (see address_space_allocator_deallocate below).
 */
static uint64_t address_space_allocator_allocate(
    struct address_space_allocator *allocator,
    uint64_t size)
{
    int i = address_space_allocator_find_available_block(allocator->blocks,
                                                         allocator->size,
                                                         size);
    if (i < 0) {
        return ANDROID_EMU_ADDRESS_SPACE_BAD_OFFSET;
    } else {
        address_space_assert(i < allocator->size);

        struct address_block *block = &allocator->blocks[i];
        address_space_assert(block->size >= size);

        if (block->size > size) {
            block = address_space_allocator_split_block(allocator, i, size);
        }

        address_space_assert(block->size == size);
        block->available = 0;

        return block->offset;
    }
}

/* Takes a size to allocate an address block and returns an offset where this
 * block is allocated. This block will not be available for other callers unless
 * it is explicitly deallocated (see address_space_allocator_deallocate below).
 */
static int address_space_allocator_allocate_fixed(
    struct address_space_allocator *allocator,
    uint64_t size,
    uint64_t offset)
{
    int i = address_space_allocator_find_available_block_at_offset(
        allocator->blocks,
        allocator->size,
        size,
        offset);

    if (i < 0) {
        return -1;
    } else {
        address_space_assert(i < allocator->size);

        struct address_block *block = &allocator->blocks[i];
        address_space_assert(block->size >= size);

        if (block->size > size) {
            block = address_space_allocator_split_block_at_offset(allocator, i, size, offset);
        }

        address_space_assert(block->size == size);
        block->available = 0;

        return 0;
    }
}

/* Takes an offset returned from address_space_allocator_allocate ealier
 * (see above) and marks this block as available for further allocation.
 */
static uint32_t address_space_allocator_deallocate(
    struct address_space_allocator *allocator,
    uint64_t offset)
{
    struct address_block *block = allocator->blocks;
    int size = allocator->size;
    int i;

    address_space_assert(size >= 1);

    for (i = 0; i < size; ++i, ++block) {
        if (block->offset == offset) {
            if (block->available) {
                return EINVAL;
            } else {
                address_space_allocator_release_block(allocator, i);
                return 0;
            }
        }
    }

    return EINVAL;
}

/* Creates a seed block. */
static void address_space_allocator_init(
    struct address_space_allocator *allocator,
    uint64_t size,
    int initial_capacity)
{
    address_space_assert(initial_capacity >= 1);

    allocator->blocks =
        (struct address_block*)
        malloc(sizeof(struct address_block) * initial_capacity);
    memset(allocator->blocks, 0, sizeof(struct address_block) * initial_capacity);
    address_space_assert(allocator->blocks);

    struct address_block *block = allocator->blocks;

    block->offset = 0;
    block->size = size;
    block->available = 1;

    allocator->size = 1;
    allocator->capacity = initial_capacity;
    allocator->total_bytes = size;
}

/* Destroy function if we don't care what was previoulsy allocated.
 * have been merged into one block.
 */
static void address_space_allocator_destroy_nocleanup(
    struct address_space_allocator *allocator)
{
    address_space_free(allocator->blocks);
}

/* Resets the state of the allocator to the initial state without
 * performing any dynamic memory management. */
static void address_space_allocator_reset(
    struct address_space_allocator *allocator)
{
    address_space_assert(allocator->size >= 1);

    allocator->size = 1;

    struct address_block* block = allocator->blocks;
    block->offset = 0;
    block->size = allocator->total_bytes;
    block->available = 1;
}

typedef void (*address_block_iter_func_t)(void* context, struct address_block*);
typedef void (*address_space_allocator_iter_func_t)(void* context, struct address_space_allocator*);

static void address_space_allocator_run(
    struct address_space_allocator *allocator,
    void* context,
    address_space_allocator_iter_func_t allocator_func,
    address_block_iter_func_t block_func)
{
    struct address_block *block = 0;
    int size;
    int i;

    allocator_func(context, allocator);

    block = allocator->blocks;
    size = allocator->size;

    address_space_assert(size >= 1);

    for (i = 0; i < size; ++i, ++block) {
        block_func(context, block);
    }
}

#ifdef ADDRESS_SPACE_NAMESPACE
}
#endif