code:
/*
 * Copyright (c) 2010-2016 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#include <kern/init.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>
#include <machine/biosmem.h>
#include <machine/boot.h>
#include <machine/cpu.h>
#include <machine/multiboot.h>
#include <machine/page.h>
#include <machine/pmap.h>
#include <machine/pmem.h>
#include <machine/types.h>
#include <vm/vm_page.h>

#define BIOSMEM_MAX_BOOT_DATA 64

/*
 * Boot data descriptor.
 *
 * The start and end addresses must not be page-aligned, since there
 * could be more than one range inside a single page.
 */
struct biosmem_boot_data {
    phys_addr_t start;
    phys_addr_t end;
    bool temporary;
};

/*
 * Sorted array of boot data descriptors.
 */
static struct biosmem_boot_data biosmem_boot_data_array[BIOSMEM_MAX_BOOT_DATA]
    __bootdata;
static unsigned int biosmem_nr_boot_data __bootdata;

/*
 * Maximum number of entries in the BIOS memory map.
 *
 * Because of adjustments of overlapping ranges, the memory map can grow
 * to twice this size.
 */
#define BIOSMEM_MAX_MAP_SIZE 128

/*
 * Memory range types.
 */
#define BIOSMEM_TYPE_AVAILABLE  1
#define BIOSMEM_TYPE_RESERVED   2
#define BIOSMEM_TYPE_ACPI       3
#define BIOSMEM_TYPE_NVS        4
#define BIOSMEM_TYPE_UNUSABLE   5
#define BIOSMEM_TYPE_DISABLED   6

/*
 * Memory map entry.
 */
struct biosmem_map_entry {
    uint64_t base_addr;
    uint64_t length;
    unsigned int type;
};

/*
 * Memory map built from the information passed by the boot loader.
 *
 * If the boot loader didn't pass a valid memory map, a simple map is built
 * based on the mem_lower and mem_upper multiboot fields.
 */
static struct biosmem_map_entry biosmem_map[BIOSMEM_MAX_MAP_SIZE * 2]
    __bootdata;
static unsigned int biosmem_map_size __bootdata;

/*
 * Temporary copy of the BIOS Data Area.
 */
static char biosmem_bda[BIOSMEM_BDA_SIZE] __bootdata;

/*
 * Contiguous block of physical memory.
 */
struct biosmem_zone {
    phys_addr_t start;
    phys_addr_t end;
};

/*
 * Physical zone boundaries.
 */
static struct biosmem_zone biosmem_zones[PMEM_MAX_ZONES] __bootdata;

/*
 * Boundaries of the simple bootstrap heap.
 *
 * This heap is located above BIOS memory.
 */
static phys_addr_t biosmem_heap_start __bootdata;
static phys_addr_t biosmem_heap_bottom __bootdata;
static phys_addr_t biosmem_heap_top __bootdata;
static phys_addr_t biosmem_heap_end __bootdata;

/*
 * Boot allocation policy.
 *
 * Top-down allocations are normally preferred to avoid unnecessarily
 * filling the DMA zone.
 */
static bool biosmem_heap_topdown __bootdata;

static char biosmem_panic_inval_boot_data[] __bootdata
    = "biosmem: invalid boot data";
static char biosmem_panic_too_many_boot_data[] __bootdata
    = "biosmem: too many boot data ranges";
static char biosmem_panic_too_big_msg[] __bootdata
    = "biosmem: too many memory map entries";
static char biosmem_panic_setup_msg[] __bootdata
    = "biosmem: unable to set up the early memory allocator";
static char biosmem_panic_nozone_msg[] __bootdata
    = "biosmem: unable to find any memory zone";
static char biosmem_panic_inval_msg[] __bootdata
    = "biosmem: attempt to allocate 0 page";
static char biosmem_panic_nomem_msg[] __bootdata
    = "biosmem: unable to allocate memory";

void __boot
biosmem_register_boot_data(phys_addr_t start, phys_addr_t end, bool temporary)
{
    unsigned int i;

    if (start >= end) {
        boot_panic(biosmem_panic_inval_boot_data);
    }

    if (biosmem_nr_boot_data == ARRAY_SIZE(biosmem_boot_data_array)) {
        boot_panic(biosmem_panic_too_many_boot_data);
    }

    for (i = 0; i < biosmem_nr_boot_data; i++) {
        /* Check if the new range overlaps */
        if ((end > biosmem_boot_data_array[i].start)
            && (start < biosmem_boot_data_array[i].end)) {

            /*
             * If it does, check whether it's part of another range.
             * For example, this applies to debugging symbols directly
             * taken from the kernel image.
             */
            if ((start >= biosmem_boot_data_array[i].start)
                && (end <= biosmem_boot_data_array[i].end)) {

                /*
                 * If it's completely included, make sure that a permanent
                 * range remains permanent.
                 *
                 * XXX This means that if one big range is first registered
                 * as temporary, and a smaller range inside of it is
                 * registered as permanent, the bigger range becomes
                 * permanent. It's not easy nor useful in practice to do
                 * better than that.
                 */
                if (biosmem_boot_data_array[i].temporary != temporary) {
                    biosmem_boot_data_array[i].temporary = false;
                }

                return;
            }

            boot_panic(biosmem_panic_inval_boot_data);
        }

        if (end <= biosmem_boot_data_array[i].start) {
            break;
        }
    }

    boot_memmove(&biosmem_boot_data_array[i + 1],
                 &biosmem_boot_data_array[i],
                 (biosmem_nr_boot_data - i) * sizeof(*biosmem_boot_data_array));

    biosmem_boot_data_array[i].start = start;
    biosmem_boot_data_array[i].end = end;
    biosmem_boot_data_array[i].temporary = temporary;
    biosmem_nr_boot_data++;
}

static void __init
biosmem_unregister_boot_data(phys_addr_t start, phys_addr_t end)
{
    unsigned int i;

    if (start >= end) {
        panic("%s", biosmem_panic_inval_boot_data);
    }

    assert(biosmem_nr_boot_data != 0);

    for (i = 0; biosmem_nr_boot_data; i++) {
        if ((start == biosmem_boot_data_array[i].start)
            && (end == biosmem_boot_data_array[i].end)) {
            break;
        }
    }

    if (i == biosmem_nr_boot_data) {
        return;
    }

    log_debug("biosmem: unregister boot data: %llx:%llx",
              (unsigned long long)biosmem_boot_data_array[i].start,
              (unsigned long long)biosmem_boot_data_array[i].end);

    biosmem_nr_boot_data--;

    memmove(&biosmem_boot_data_array[i],
            &biosmem_boot_data_array[i + 1],
            (biosmem_nr_boot_data - i) * sizeof(*biosmem_boot_data_array));
}

static void __boot
biosmem_map_build(const struct multiboot_raw_info *mbi)
{
    struct multiboot_raw_mmap_entry *mb_entry, *mb_end;
    struct biosmem_map_entry *start, *entry, *end;
    unsigned long addr;

    addr = mbi->mmap_addr;
    mb_entry = (struct multiboot_raw_mmap_entry *)addr;
    mb_end = (struct multiboot_raw_mmap_entry *)(addr + mbi->mmap_length);
    start = biosmem_map;
    entry = start;
    end = entry + BIOSMEM_MAX_MAP_SIZE;

    while ((mb_entry < mb_end) && (entry < end)) {
        entry->base_addr = mb_entry->base_addr;
        entry->length = mb_entry->length;
        entry->type = mb_entry->type;

        mb_entry = (void *)mb_entry + sizeof(mb_entry->size) + mb_entry->size;
        entry++;
    }

    biosmem_map_size = entry - start;
}

static void __boot
biosmem_map_build_simple(const struct multiboot_raw_info *mbi)
{
    struct biosmem_map_entry *entry;

    entry = biosmem_map;
    entry->base_addr = 0;
    entry->length = mbi->mem_lower << 10;
    entry->type = BIOSMEM_TYPE_AVAILABLE;

    entry++;
    entry->base_addr = BIOSMEM_END;
    entry->length = mbi->mem_upper << 10;
    entry->type = BIOSMEM_TYPE_AVAILABLE;

    biosmem_map_size = 2;
}

static int __boot
biosmem_map_entry_is_invalid(const struct biosmem_map_entry *entry)
{
    return (entry->base_addr + entry->length) <= entry->base_addr;
}

static void __boot
biosmem_map_filter(void)
{
    struct biosmem_map_entry *entry;
    unsigned int i;

    i = 0;

    while (i < biosmem_map_size) {
        entry = &biosmem_map[i];

        if (biosmem_map_entry_is_invalid(entry)) {
            biosmem_map_size--;
            boot_memmove(entry, entry + 1,
                         (biosmem_map_size - i) * sizeof(*entry));
            continue;
        }

        i++;
    }
}

static void __boot
biosmem_map_sort(void)
{
    struct biosmem_map_entry tmp;
    unsigned int i, j;

    /*
     * Simple insertion sort.
     */
    for (i = 1; i < biosmem_map_size; i++) {
        boot_memcpy(&tmp, &biosmem_map[i], sizeof(tmp));

        for (j = i - 1; j < i; j--) {
            if (biosmem_map[j].base_addr < tmp.base_addr) {
                break;
            }

            boot_memcpy(&biosmem_map[j + 1], &biosmem_map[j],
                        sizeof(biosmem_map[j + 1]));
        }

        boot_memcpy(&biosmem_map[j + 1], &tmp, sizeof(biosmem_map[j + 1]));
    }
}

static void __boot
biosmem_map_adjust(void)
{
    struct biosmem_map_entry tmp, *a, *b, *first, *second;
    uint64_t a_end, b_end, last_end;
    unsigned int i, j, last_type;

    biosmem_map_filter();

    /*
     * Resolve overlapping areas, giving priority to most restrictive
     * (i.e. numerically higher) types.
     */
    for (i = 0; i < biosmem_map_size; i++) {
        a = &biosmem_map[i];
        a_end = a->base_addr + a->length;

        j = i + 1;

        while (j < biosmem_map_size) {
            b = &biosmem_map[j];
            b_end = b->base_addr + b->length;

            if ((a->base_addr >= b_end) || (a_end <= b->base_addr)) {
                j++;
                continue;
            }

            if (a->base_addr < b->base_addr) {
                first = a;
                second = b;
            } else {
                first = b;
                second = a;
            }

            if (a_end > b_end) {
                last_end = a_end;
                last_type = a->type;
            } else {
                last_end = b_end;
                last_type = b->type;
            }

            tmp.base_addr = second->base_addr;
            tmp.length = MIN(a_end, b_end) - tmp.base_addr;
            tmp.type = MAX(a->type, b->type);
            first->length = tmp.base_addr - first->base_addr;
            second->base_addr += tmp.length;
            second->length = last_end - second->base_addr;
            second->type = last_type;

            /*
             * Filter out invalid entries.
             */
            if (biosmem_map_entry_is_invalid(a)
                && biosmem_map_entry_is_invalid(b)) {
                boot_memcpy(a, &tmp, sizeof(*a));
                biosmem_map_size--;
                memmove(b, b + 1, (biosmem_map_size - j) * sizeof(*b));
                continue;
            } else if (biosmem_map_entry_is_invalid(a)) {
                boot_memcpy(a, &tmp, sizeof(*a));
                j++;
                continue;
            } else if (biosmem_map_entry_is_invalid(b)) {
                boot_memcpy(b, &tmp, sizeof(*b));
                j++;
                continue;
            }

            if (tmp.type == a->type) {
                first = a;
            } else if (tmp.type == b->type) {
                first = b;
            } else {

                /*
                 * If the overlapping area can't be merged with one of its
                 * neighbors, it must be added as a new entry.
                 */

                if (biosmem_map_size >= ARRAY_SIZE(biosmem_map)) {
                    boot_panic(biosmem_panic_too_big_msg);
                }

                boot_memcpy(&biosmem_map[biosmem_map_size], &tmp,
                            sizeof(biosmem_map[biosmem_map_size]));
                biosmem_map_size++;
                j++;
                continue;
            }

            if (first->base_addr > tmp.base_addr) {
                first->base_addr = tmp.base_addr;
            }

            first->length += tmp.length;
            j++;
        }
    }

    biosmem_map_sort();
}

/*
 * Find addresses of physical memory within a given range.
 *
 * This function considers the memory map with the [*phys_start, *phys_end]
 * range on entry, and returns the lowest address of physical memory
 * in *phys_start, and the highest address of unusable memory immediately
 * following physical memory in *phys_end.
 *
 * These addresses are normally used to establish the range of a zone.
 */
static int __boot
biosmem_map_find_avail(phys_addr_t *phys_start, phys_addr_t *phys_end)
{
    const struct biosmem_map_entry *entry, *map_end;
    phys_addr_t zone_start, zone_end;
    uint64_t start, end;

    zone_start = (phys_addr_t)-1;
    zone_end = (phys_addr_t)-1;
    map_end = biosmem_map + biosmem_map_size;

    for (entry = biosmem_map; entry < map_end; entry++) {
        if (entry->type != BIOSMEM_TYPE_AVAILABLE) {
            continue;
        }

        start = vm_page_round(entry->base_addr);

        if (start >= *phys_end) {
            break;
        }

        end = vm_page_trunc(entry->base_addr + entry->length);

        if ((start < end) && (start < *phys_end) && (end > *phys_start)) {
            if (zone_start == (phys_addr_t)-1) {
                zone_start = start;
            }

            zone_end = end;
        }
    }

    if ((zone_start == (phys_addr_t)-1) || (zone_end == (phys_addr_t)-1)) {
        return -1;
    }

    if (zone_start > *phys_start) {
        *phys_start = zone_start;
    }

    if (zone_end < *phys_end) {
        *phys_end = zone_end;
    }

    return 0;
}

static void __boot
biosmem_set_zone(unsigned int zone_index, phys_addr_t start, phys_addr_t end)
{
    biosmem_zones[zone_index].start = start;
    biosmem_zones[zone_index].end = end;
}

static phys_addr_t __boot
biosmem_zone_end(unsigned int zone_index)
{
    return biosmem_zones[zone_index].end;
}

static phys_addr_t __boot
biosmem_zone_size(unsigned int zone_index)
{
    return biosmem_zones[zone_index].end - biosmem_zones[zone_index].start;
}

static int __boot
biosmem_find_avail_clip(phys_addr_t *avail_start, phys_addr_t *avail_end,
                        phys_addr_t data_start, phys_addr_t data_end)
{
    phys_addr_t orig_end;

    assert(data_start < data_end);

    orig_end = data_end;
    data_start = vm_page_trunc(data_start);
    data_end = vm_page_round(data_end);

    if (data_end < orig_end) {
        boot_panic(biosmem_panic_inval_boot_data);
    }

    if ((data_end <= *avail_start) || (data_start >= *avail_end)) {
        return 0;
    }

    if (data_start > *avail_start) {
        *avail_end = data_start;
    } else {
        if (data_end >= *avail_end) {
            return -1;
        }

        *avail_start = data_end;
    }

    return 0;
}

/*
 * Find available memory in the given range.
 *
 * The search starts at the given start address, up to the given end address.
 * If a range is found, it is stored through the avail_startp and avail_endp
 * pointers.
 *
 * The range boundaries are page-aligned on return.
 */
static int __boot
biosmem_find_avail(phys_addr_t start, phys_addr_t end,
                   phys_addr_t *avail_start, phys_addr_t *avail_end)
{
    phys_addr_t orig_start;
    unsigned int i;
    int error;

    assert(start <= end);

    orig_start = start;
    start = vm_page_round(start);
    end = vm_page_trunc(end);

    if ((start < orig_start) || (start >= end)) {
        return -1;
    }

    *avail_start = start;
    *avail_end = end;

    for (i = 0; i < biosmem_nr_boot_data; i++) {
        error = biosmem_find_avail_clip(avail_start, avail_end,
                                        biosmem_boot_data_array[i].start,
                                        biosmem_boot_data_array[i].end);

        if (error) {
            return -1;
        }
    }

    return 0;
}

static void __boot
biosmem_setup_allocator(const struct multiboot_raw_info *mbi)
{
    phys_addr_t heap_start, heap_end, max_heap_start, max_heap_end;
    phys_addr_t start, end;
    int error;

    /*
     * Find some memory for the heap. Look for the largest unused area in
     * upper memory, carefully avoiding all boot data.
     */
    end = vm_page_trunc((mbi->mem_upper + 1024) << 10);

#ifndef __LP64__
    if (end > PMEM_DIRECTMAP_LIMIT) {
        end = PMEM_DIRECTMAP_LIMIT;
    }
#endif /* __LP64__ */

    max_heap_start = 0;
    max_heap_end = 0;
    start = BIOSMEM_END;

    for (;;) {
        error = biosmem_find_avail(start, end, &heap_start, &heap_end);

        if (error) {
            break;
        }

        if ((heap_end - heap_start) > (max_heap_end - max_heap_start)) {
            max_heap_start = heap_start;
            max_heap_end = heap_end;
        }

        start = heap_end;
    }

    if (max_heap_start >= max_heap_end) {
        boot_panic(biosmem_panic_setup_msg);
    }

    biosmem_heap_start = max_heap_start;
    biosmem_heap_end = max_heap_end;
    biosmem_heap_bottom = biosmem_heap_start;
    biosmem_heap_top = biosmem_heap_end;
    biosmem_heap_topdown = true;

    /* Prevent biosmem_free_usable() from releasing the heap */
    biosmem_register_boot_data(biosmem_heap_start, biosmem_heap_end, false);
}

void __boot
biosmem_bootstrap(const struct multiboot_raw_info *mbi)
{
    phys_addr_t phys_start, phys_end;
    int error;

    boot_memcpy(biosmem_bda, (const void *)BIOSMEM_BDA_ADDR, BIOSMEM_BDA_SIZE);

    if (mbi->flags & MULTIBOOT_LOADER_MMAP) {
        biosmem_map_build(mbi);
    } else {
        biosmem_map_build_simple(mbi);
    }

    biosmem_map_adjust();

    phys_start = BIOSMEM_BASE;
    phys_end = PMEM_DMA_LIMIT;
    error = biosmem_map_find_avail(&phys_start, &phys_end);

    if (error) {
        boot_panic(biosmem_panic_nozone_msg);
    }

    biosmem_set_zone(PMEM_ZONE_DMA, phys_start, phys_end);

    phys_start = PMEM_DMA_LIMIT;
#ifdef PMEM_DMA32_LIMIT
    phys_end = PMEM_DMA32_LIMIT;
    error = biosmem_map_find_avail(&phys_start, &phys_end);

    if (error) {
        goto out;
    }

    biosmem_set_zone(PMEM_ZONE_DMA32, phys_start, phys_end);

    phys_start = PMEM_DMA32_LIMIT;
#endif /* PMEM_DMA32_LIMIT */
    phys_end = PMEM_DIRECTMAP_LIMIT;
    error = biosmem_map_find_avail(&phys_start, &phys_end);

    if (error) {
        goto out;
    }

    biosmem_set_zone(PMEM_ZONE_DIRECTMAP, phys_start, phys_end);

    phys_start = PMEM_DIRECTMAP_LIMIT;
    phys_end = PMEM_HIGHMEM_LIMIT;
    error = biosmem_map_find_avail(&phys_start, &phys_end);

    if (error) {
        goto out;
    }

    biosmem_set_zone(PMEM_ZONE_HIGHMEM, phys_start, phys_end);

out:
    biosmem_setup_allocator(mbi);
}

void * __boot
biosmem_bootalloc(unsigned int nr_pages)
{
    unsigned long addr, size;

    size = vm_page_ptob(nr_pages);

    if (size == 0) {
        boot_panic(biosmem_panic_inval_msg);
    }

    if (biosmem_heap_topdown) {
        addr = biosmem_heap_top - size;

        if ((addr < biosmem_heap_start) || (addr > biosmem_heap_top)) {
            boot_panic(biosmem_panic_nomem_msg);
        }

        biosmem_heap_top = addr;
    } else {
        unsigned long end;

        addr = biosmem_heap_bottom;
        end = addr + size;

        if ((end > biosmem_heap_end) || (end < biosmem_heap_bottom)) {
            boot_panic(biosmem_panic_nomem_msg);
        }

        biosmem_heap_bottom = end;
    }

    return boot_memset((void *)addr, 0, size);
}

const void *
biosmem_get_bda(void)
{
    return biosmem_bda;
}

phys_addr_t __boot
biosmem_directmap_end(void)
{
    if (biosmem_zone_size(PMEM_ZONE_DIRECTMAP) != 0) {
        return biosmem_zone_end(PMEM_ZONE_DIRECTMAP);
    } else if (biosmem_zone_size(PMEM_ZONE_DMA32) != 0) {
        return biosmem_zone_end(PMEM_ZONE_DMA32);
    } else {
        return biosmem_zone_end(PMEM_ZONE_DMA);
    }
}

static const char * __init
biosmem_type_desc(unsigned int type)
{
    switch (type) {
    case BIOSMEM_TYPE_AVAILABLE:
        return "available";
    case BIOSMEM_TYPE_RESERVED:
        return "reserved";
    case BIOSMEM_TYPE_ACPI:
        return "ACPI";
    case BIOSMEM_TYPE_NVS:
        return "ACPI NVS";
    case BIOSMEM_TYPE_UNUSABLE:
        return "unusable";
    default:
        return "unknown (reserved)";
    }
}

static void __init
biosmem_map_show(void)
{
    const struct biosmem_map_entry *entry, *end;

    log_debug("biosmem: physical memory map:");

    for (entry = biosmem_map, end = entry + biosmem_map_size;
         entry < end;
         entry++)
        log_debug("biosmem: %018llx:%018llx, %s",
                  (unsigned long long)entry->base_addr,
                  (unsigned long long)(entry->base_addr + entry->length),
                  biosmem_type_desc(entry->type));

    log_debug("biosmem: heap: %llx:%llx",
              (unsigned long long)biosmem_heap_start,
              (unsigned long long)biosmem_heap_end);
}

static void __init
biosmem_load_zone(struct biosmem_zone *zone, uint64_t max_phys_end)
{
    phys_addr_t phys_start, phys_end, avail_start, avail_end;
    unsigned int zone_index;

    phys_start = zone->start;
    phys_end = zone->end;
    zone_index = zone - biosmem_zones;

    if (phys_end > max_phys_end) {
        if (max_phys_end <= phys_start) {
            log_warning("biosmem: zone %s physically unreachable, "
                        "not loaded", vm_page_zone_name(zone_index));
            return;
        }

        log_warning("biosmem: warning: zone %s truncated to %#llx",
                    vm_page_zone_name(zone_index),
                    (unsigned long long)max_phys_end);
        phys_end = max_phys_end;
    }

    vm_page_load(zone_index, phys_start, phys_end);

    /*
     * Clip the remaining available heap to fit it into the loaded
     * zone if possible.
     */

    if ((biosmem_heap_top > phys_start) && (biosmem_heap_bottom < phys_end)) {
        if (biosmem_heap_bottom >= phys_start) {
            avail_start = biosmem_heap_bottom;
        } else {
            avail_start = phys_start;
        }

        if (biosmem_heap_top <= phys_end) {
            avail_end = biosmem_heap_top;
        } else {
            avail_end = phys_end;
        }

        vm_page_load_heap(zone_index, avail_start, avail_end);
    }
}

static int __init
biosmem_setup(void)
{
    unsigned int phys_addr_width;
    uint64_t max_phys_end;
    struct biosmem_zone *zone;

    biosmem_map_show();

    phys_addr_width = cpu_phys_addr_width(cpu_current());
    max_phys_end = ((phys_addr_width == 0) || (phys_addr_width == 64))
                   ? (uint64_t)-1
                   : (uint64_t)1 << phys_addr_width;

    for (size_t i = 0; i < ARRAY_SIZE(biosmem_zones); i++) {
        if (biosmem_zone_size(i) == 0) {
            break;
        }

        zone = &biosmem_zones[i];
        biosmem_load_zone(zone, max_phys_end);
    }

    return 0;
}

INIT_OP_DEFINE(biosmem_setup,
               INIT_OP_DEP(cpu_setup, true),
               INIT_OP_DEP(log_setup, true));

static void __init
biosmem_unregister_temporary_boot_data(void)
{
    struct biosmem_boot_data *data;
    unsigned int i;

    for (i = 0; i < biosmem_nr_boot_data; i++) {
        data = &biosmem_boot_data_array[i];

        if (!data->temporary) {
            continue;
        }

        biosmem_unregister_boot_data(data->start, data->end);
        i = (unsigned int)-1;
    }
}

static void __init
biosmem_free_usable_range(phys_addr_t start, phys_addr_t end)
{
    struct vm_page *page;

    log_debug("biosmem: release to vm_page: %llx:%llx (%lluk)",
              (unsigned long long)start, (unsigned long long)end,
              (unsigned long long)((end - start) >> 10));

    while (start < end) {
        page = vm_page_lookup(start);
        assert(page != NULL);
        vm_page_manage(page);
        start += PAGE_SIZE;
    }
}

static void __init
biosmem_free_usable_entry(phys_addr_t start, phys_addr_t end)
{
    phys_addr_t avail_start, avail_end;
    int error;

    for (;;) {
        error = biosmem_find_avail(start, end, &avail_start, &avail_end);

        if (error) {
            break;
        }

        biosmem_free_usable_range(avail_start, avail_end);
        start = avail_end;
    }
}

static int __init
biosmem_free_usable(void)
{
    struct biosmem_map_entry *entry;
    uint64_t start, end;
    unsigned int i;

    biosmem_unregister_temporary_boot_data();

    for (i = 0; i < biosmem_map_size; i++) {
        entry = &biosmem_map[i];

        if (entry->type != BIOSMEM_TYPE_AVAILABLE) {
            continue;
        }

        start = vm_page_round(entry->base_addr);

        if (start >= PMEM_HIGHMEM_LIMIT) {
            break;
        }

        end = vm_page_trunc(entry->base_addr + entry->length);

        if (end > PMEM_HIGHMEM_LIMIT) {
            end = PMEM_HIGHMEM_LIMIT;
        }

        if (start < BIOSMEM_BASE) {
            start = BIOSMEM_BASE;
        }

        if (start >= end) {
            continue;
        }

        biosmem_free_usable_entry(start, end);
    }

    return 0;
}

INIT_OP_DEFINE(biosmem_free_usable,
               INIT_OP_DEP(boot_save_data, true),
               INIT_OP_DEP(log_setup, true),
               INIT_OP_DEP(vm_page_setup, true));


code:
/*
 * Copyright (c) 2010-2016 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */

#ifndef X86_BIOSMEM_H
#define X86_BIOSMEM_H

#include <stdbool.h>

#include <kern/init.h>
#include <machine/multiboot.h>
#include <machine/types.h>

/*
 * BIOS Data Area.
 */
#define BIOSMEM_BDA_ADDR    0x400
#define BIOSMEM_BDA_SIZE    0x100

/*
 * Address where the address of the Extended BIOS Data Area segment can be
 * found.
 */
#define BIOSMEM_EBDA_PTR 0x40e

/*
 * Significant low memory addresses.
 *
 * The first 64 KiB are reserved for various reasons (e.g. to preserve BIOS
 * data and to work around data corruption on some hardware).
 */
#define BIOSMEM_BASE        0x010000
#define BIOSMEM_BASE_END    0x0a0000
#define BIOSMEM_EXT_ROM     0x0e0000
#define BIOSMEM_ROM         0x0f0000
#define BIOSMEM_END         0x100000

/*
 * Report reserved addresses to the biosmem module.
 *
 * Once all boot data have been registered, the user can set up the
 * early page allocator.
 *
 * If the range is marked temporary, it will be unregistered once
 * the boot data have been saved/consumed so that their backing
 * pages are loaded into the VM system.
 *
 * This function is called before paging is enabled.
 */
void biosmem_register_boot_data(phys_addr_t start, phys_addr_t end,
                                bool temporary);

/*
 * Initialize the early page allocator.
 *
 * This function uses the memory map provided by the boot loader along
 * with the registered boot data addresses to set up a heap of free pages
 * of physical memory.
 *
 * This function is called before paging is enabled.
 */
void biosmem_bootstrap(const struct multiboot_raw_info *mbi);

/*
 * Allocate contiguous physical pages during bootstrap.
 *
 * The pages returned are guaranteed to be part of the direct physical
 * mapping when paging is enabled.
 *
 * This function should only be used to allocate initial page table pages.
 * Those pages are later loaded into the VM system (as reserved pages)
 * which means they can be freed like other regular pages. Users should
 * fix up the type of those pages once the VM system is initialized.
 *
 * This function is called before paging is enabled.
 */
void * biosmem_bootalloc(unsigned int nr_pages);

/*
 * Return a pointer to a copy of the BIOS Data Area.
 *
 * The region denoted by the returned address is of size BIOSMEM_BDA_SIZE,
 * and is only valid during initialization.
 */
const void * biosmem_get_bda(void);

/*
 * Return the limit of physical memory that can be directly mapped.
 */
phys_addr_t biosmem_directmap_end(void);

/*
 * This init operation provides :
 *  - heaps of physical memory are loaded by the VM system
 */
INIT_OP_DECLARE(biosmem_setup);

#endif /* X86_BIOSMEM_H */

license: mit


code:
/*
 * Copyright (c) 2010-2017 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 *
 *
 * Early initialization procedure for x86.
 *
 * This module is separated in assembly and C code. The former is where
 * the first instructions are run, and where actions that aren't possible,
 * easy or clean in C are performed.
 *
 * When the boot loader passes control to the kernel, the main processor is
 * in protected mode, paging is disabled, and some boot data are availabe
 * outside the kernel. This module first sets up a basic physical memory
 * allocator so that it can allocate page tables without corrupting the
 * boot data. The .boot section is linked at physical addresses, so that
 * it can run with and without paging enabled. The page tables must properly
 * configure an identity mapping so that this remains true as long as
 * initialization code and data are used. Once the VM system is available,
 * boot data are copied in kernel allocated buffers and their original pages
 * are freed.
 *
 * On amd64, 64-bit code cannot run in legacy or compatibility mode. In order
 * to walk the boot data structures, the kernel must either run 32-bit code
 * (e.g. converting ELF32 to ELF64 objects before linking them) or establish
 * a temporary identity mapping for the first 4 GiB of physical memory. As a
 * way to simplify development, and make it possible to use 64-bit code
 * almost everywhere, the latter solution is implemented (a small part of
 * 32-bit code is required until the identity mapping is in place). Mentions
 * to "enabling paging" do not refer to this initial identity mapping.
 *
 * TODO EFI support.
 */

#include <stdalign.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>

#include <kern/arg.h>
#include <kern/init.h>
#include <kern/kmem.h>
#include <kern/kernel.h>
#include <kern/log.h>
#include <kern/macros.h>
#include <kern/panic.h>
#include <kern/percpu.h>
#include <kern/thread.h>
#include <machine/acpi.h>
#include <machine/atcons.h>
#include <machine/biosmem.h>
#include <machine/boot.h>
#include <machine/cga.h>
#include <machine/cpu.h>
#include <machine/elf.h>
#include <machine/multiboot.h>
#include <machine/page.h>
#include <machine/pmap.h>
#include <machine/pmu_amd.h>
#include <machine/pmu_intel.h>
#include <machine/uart.h>
#include <vm/vm_kmem.h>

alignas(CPU_DATA_ALIGN) char boot_stack[BOOT_STACK_SIZE] __bootdata;
alignas(CPU_DATA_ALIGN) char boot_ap_stack[BOOT_STACK_SIZE] __bootdata;

#ifdef __LP64__
alignas(PAGE_SIZE) pmap_pte_t boot_pml4[PMAP_L3_PTES_PER_PT] __bootdata;
alignas(PAGE_SIZE) pmap_pte_t boot_pdpt[PMAP_L2_PTES_PER_PT] __bootdata;
alignas(PAGE_SIZE) pmap_pte_t boot_pdir[4 * PMAP_L1_PTES_PER_PT] __bootdata;
char boot_panic_long_mode_msg[] __bootdata
    = "boot: processor doesn't support long mode";
#endif /* __LP64__ */

struct cpu_tls_seg boot_tls_seg __bootdata = {
    .ssp_guard_word = SSP_GUARD_WORD,
};

/*
 * This TLS segment descriptor is copied early at boot time into the
 * temporary boot GDT. However, it is incomplete. Assembly code
 * completes it before writing it into the boot GDT before calling
 * any C function, since those may require the TLS segment ready if
 * stack protection is enabled.
 */
struct cpu_seg_desc boot_tls_seg_desc __bootdata = {
    .low = (sizeof(boot_tls_seg) & 0xffff),

    .high = CPU_DESC_DB
            | ((sizeof(boot_tls_seg) >> 16) & 0xf)
            | CPU_DESC_PRESENT
            | CPU_DESC_S
            | CPU_DESC_TYPE_DATA,
};

/*
 * Copies of the multiboot data passed by the boot loader.
 */
static struct multiboot_raw_info boot_raw_mbi __bootdata;
static struct multiboot_info boot_mbi __initdata;

static char boot_tmp_cmdline[ARG_CMDLINE_MAX_SIZE] __bootdata;

static char boot_panic_intro_msg[] __bootdata = "panic: ";
static char boot_panic_loader_msg[] __bootdata
    = "boot: not started by a multiboot compliant boot loader";
static char boot_panic_meminfo_msg[] __bootdata
    = "boot: missing basic memory information";
static char boot_panic_cmdline_msg[] __bootdata
    = "boot: command line too long";

static volatile unsigned int boot_ap_id __bootdata;
static char *boot_ap_stacks[CONFIG_MAX_CPUS - 1] __initdata;

pmap_pte_t * boot_ap_setup(void);
char * boot_get_ap_stack(void);

void * __boot
boot_memcpy(void *dest, const void *src, size_t n)
{
    const char *src_ptr;
    char *dest_ptr;
    size_t i;

    dest_ptr = dest;
    src_ptr = src;

    for (i = 0; i < n; i++) {
        *dest_ptr = *src_ptr;
        dest_ptr++;
        src_ptr++;
    }

    return dest;
}

void * __boot
boot_memmove(void *dest, const void *src, size_t n)
{
    const char *src_ptr;
    char *dest_ptr;
    size_t i;

    if (dest <= src) {
        dest_ptr = dest;
        src_ptr = src;

        for (i = 0; i < n; i++) {
            *dest_ptr = *src_ptr;
            dest_ptr++;
            src_ptr++;
        }
    } else {
        dest_ptr = dest + n - 1;
        src_ptr = src + n - 1;

        for (i = 0; i < n; i++) {
            *dest_ptr = *src_ptr;
            dest_ptr--;
            src_ptr--;
        }
    }

    return dest;
}

void * __boot
boot_memset(void *s, int c, size_t n)
{
    char *buffer;
    size_t i;

    buffer = s;

    for (i = 0; i < n; i++) {
        buffer[i] = c;
    }

    return s;
}

size_t __boot
boot_strlen(const char *s)
{
    const char *start;

    start = s;

    while (*s != '\0') {
        s++;
    }

    return (s - start);
}

void __boot
boot_panic(const char *msg)
{
    uint16_t *ptr, *end;
    const char *s;

    ptr = (uint16_t *)BOOT_CGAMEM;
    end = ptr + BOOT_CGACHARS;

    s = boot_panic_intro_msg;

    while ((ptr < end) && (*s != '\0')) {
        *ptr = (BOOT_CGACOLOR << 8) | *s;
        ptr++;
        s++;
    }

    s = msg;

    while ((ptr < end) && (*s != '\0')) {
        *ptr = (BOOT_CGACOLOR << 8) | *s;
        ptr++;
        s++;
    }

    while (ptr < end) {
        *ptr = (BOOT_CGACOLOR << 8) | ' ';
        ptr++;
    }

    cpu_halt();

    /* Never reached */
}

static void __boot
boot_save_mod_cmdline_sizes(struct multiboot_raw_info *mbi)
{
    struct multiboot_raw_module *mod;
    uint32_t i;

    if (mbi->flags & MULTIBOOT_LOADER_MODULES) {
        uintptr_t addr;

        addr = mbi->mods_addr;

        for (i = 0; i < mbi->mods_count; i++) {
            mod = (struct multiboot_raw_module *)addr + i;
            mod->reserved = boot_strlen((char *)(uintptr_t)mod->string) + 1;
        }
    }
}

static void __boot
boot_register_data(const struct multiboot_raw_info *mbi)
{
    struct multiboot_raw_module *mod;
    struct elf_shdr *shdr;
    uintptr_t tmp;
    unsigned int i;

    biosmem_register_boot_data((uintptr_t)&_boot,
                               BOOT_VTOP((uintptr_t)&_end), false);

    if (mbi->flags & MULTIBOOT_LOADER_MODULES) {
        i = mbi->mods_count * sizeof(struct multiboot_raw_module);
        biosmem_register_boot_data(mbi->mods_addr, mbi->mods_addr + i, true);

        tmp = mbi->mods_addr;

        for (i = 0; i < mbi->mods_count; i++) {
            mod = (struct multiboot_raw_module *)tmp + i;
            biosmem_register_boot_data(mod->mod_start, mod->mod_end, true);

            if (mod->string != 0) {
                biosmem_register_boot_data(mod->string,
                                           mod->string + mod->reserved, true);
            }
        }
    }

    if (mbi->flags & MULTIBOOT_LOADER_SHDR) {
        tmp = mbi->shdr_num * mbi->shdr_size;
        biosmem_register_boot_data(mbi->shdr_addr, mbi->shdr_addr + tmp, true);

        tmp = mbi->shdr_addr;

        for (i = 0; i < mbi->shdr_num; i++) {
            shdr = (struct elf_shdr *)(tmp + (i * mbi->shdr_size));

            if ((shdr->type != ELF_SHT_SYMTAB)
                && (shdr->type != ELF_SHT_STRTAB)) {
                continue;
            }

            biosmem_register_boot_data(shdr->addr, shdr->addr + shdr->size, true);
        }
    }
}

pmap_pte_t * __boot
boot_setup_paging(struct multiboot_raw_info *mbi, unsigned long eax)
{
    if (eax != MULTIBOOT_LOADER_MAGIC) {
        boot_panic(boot_panic_loader_msg);
    }

    if (!(mbi->flags & MULTIBOOT_LOADER_MEMORY)) {
        boot_panic(boot_panic_meminfo_msg);
    }

    /*
     * Save the multiboot data passed by the boot loader, initialize the
     * bootstrap allocator and set up paging.
     */
    boot_memmove(&boot_raw_mbi, mbi, sizeof(boot_raw_mbi));

    /*
     * The kernel command line must be passed as early as possible to the
     * arg module so that other modules can look up options. Instead of
     * mapping it later, make a temporary copy.
     */
    if (!(mbi->flags & MULTIBOOT_LOADER_CMDLINE)) {
        boot_tmp_cmdline[0] = '\0';
    } else {
        uintptr_t addr;
        size_t length;

        addr = mbi->cmdline;
        length = boot_strlen((const char *)addr) + 1;

        if (length > ARRAY_SIZE(boot_tmp_cmdline)) {
            boot_panic(boot_panic_cmdline_msg);
        }

        boot_memcpy(boot_tmp_cmdline, (const char *)addr, length);
    }

    if ((mbi->flags & MULTIBOOT_LOADER_MODULES) && (mbi->mods_count == 0)) {
        boot_raw_mbi.flags &= ~MULTIBOOT_LOADER_MODULES;
    }

    /*
     * The module command lines will be memory mapped later during
     * initialization. Their respective sizes must be saved.
     */
    boot_save_mod_cmdline_sizes(&boot_raw_mbi);
    boot_register_data(&boot_raw_mbi);
    biosmem_bootstrap(&boot_raw_mbi);
    return pmap_setup_paging();
}

#ifdef CONFIG_X86_PAE
#define BOOT_PAE_LABEL " PAE"
#else /* CONFIG_X86_PAE */
#define BOOT_PAE_LABEL
#endif /* CONFIG_X86_PAE */

void __init
boot_log_info(void)
{
    log_info(KERNEL_NAME "/" CONFIG_SUBARCH " " KERNEL_VERSION
             BOOT_PAE_LABEL);
}

static void * __init
boot_save_memory(uint32_t addr, size_t size)
{
    uintptr_t map_addr;
    size_t map_size;
    const void *src;
    void *copy;

    /*
     * Creates temporary virtual mappings because, on 32-bits systems,
     * there is no guarantee that the boot data will be available from
     * the direct physical mapping.
     */
    src = vm_kmem_map_pa(addr, size, &map_addr, &map_size);

    if (src == NULL) {
        panic("boot: unable to map boot data in kernel map");
    }

    copy = kmem_alloc(size);

    if (copy == NULL) {
        panic("boot: unable to allocate memory for boot data copy");
    }

    memcpy(copy, src, size);
    vm_kmem_unmap_pa(map_addr, map_size);
    return copy;
}

static void __init
boot_save_mod(struct multiboot_module *dest_mod,
              const struct multiboot_raw_module *src_mod)
{
    uintptr_t map_addr;
    size_t size, map_size;
    const void *src;
    void *copy;

    size = src_mod->mod_end - src_mod->mod_start;
    src = vm_kmem_map_pa(src_mod->mod_start, size, &map_addr, &map_size);

    if (src == NULL) {
        panic("boot: unable to map module in kernel map");
    }

    copy = kmem_alloc(size);

    if (copy == NULL) {
        panic("boot: unable to allocate memory for module copy");
    }

    memcpy(copy, src, size);
    vm_kmem_unmap_pa(map_addr, map_size);

    dest_mod->mod_start = copy;
    dest_mod->mod_end = copy + size;

    if (src_mod->string == 0) {
        dest_mod->string = NULL;
    } else {
        dest_mod->string = boot_save_memory(src_mod->string, src_mod->reserved);
    }
}

static void __init
boot_save_mods(void)
{
    const struct multiboot_raw_module *src;
    struct multiboot_module *dest;
    uintptr_t map_addr;
    size_t size, map_size;
    uint32_t i;

    if (!(boot_raw_mbi.flags & MULTIBOOT_LOADER_MODULES)) {
        boot_mbi.mods_addr = NULL;
        boot_mbi.mods_count = boot_raw_mbi.mods_count;
        return;
    }

    size = boot_raw_mbi.mods_count * sizeof(struct multiboot_raw_module);
    src = vm_kmem_map_pa(boot_raw_mbi.mods_addr, size, &map_addr, &map_size);

    if (src == NULL) {
        panic("boot: unable to map module table in kernel map");
    }

    size = boot_raw_mbi.mods_count * sizeof(struct multiboot_module);
    dest = kmem_alloc(size);

    if (dest == NULL) {
        panic("boot: unable to allocate memory for the module table");
    }

    for (i = 0; i < boot_raw_mbi.mods_count; i++) {
        boot_save_mod(&dest[i], &src[i]);
    }

    vm_kmem_unmap_pa(map_addr, map_size);

    boot_mbi.mods_addr = dest;
    boot_mbi.mods_count = boot_raw_mbi.mods_count;
}

/*
 * Copy boot data in kernel allocated memory.
 *
 * At this point, the only required boot data are the modules and the command
 * line strings. Optionally, the kernel can use the symbol table, if passed by
 * the boot loader. Once the boot data are managed as kernel buffers, their
 * backing pages can be freed.
 */
static int __init
boot_save_data(void)
{
    boot_mbi.flags = boot_raw_mbi.flags;
    boot_save_mods();
    return 0;
}

INIT_OP_DEFINE(boot_save_data,
               INIT_OP_DEP(kmem_setup, true),
               INIT_OP_DEP(vm_kmem_setup, true));

void __init
boot_main(void)
{
    arg_set_cmdline(boot_tmp_cmdline);
    kernel_main();

    /* Never reached */
}

void __init
boot_alloc_ap_stacks(void)
{
    char *stack;

    for (unsigned int i = 1; i < cpu_count(); i++) {
        stack = kmem_alloc(BOOT_STACK_SIZE);

        if (!stack) {
            panic("boot: unable to allocate stack for cpu%u", i);
        }

        boot_ap_stacks[i - 1] = stack;
    }
}

void __init
boot_set_ap_id(unsigned int ap_id)
{
    boot_ap_id = ap_id;
}

pmap_pte_t * __boot
boot_ap_setup(void)
{
    return pmap_ap_setup_paging(boot_ap_id);
}

char * __init
boot_get_ap_stack(void)
{
    unsigned int index;

    index = boot_ap_id - 1;
    assert(boot_ap_id < ARRAY_SIZE(boot_ap_stacks));
    return boot_ap_stacks[index];
}

void __init
boot_ap_main(void)
{
    cpu_ap_setup(boot_ap_id);
    thread_ap_setup();
    pmap_ap_setup();
    percpu_ap_setup();
    kernel_ap_main();

    /* Never reached */
}

/*
 * Init operation aliases.
 */

static int __init
boot_bootstrap_console(void)
{
    return 0;
}

INIT_OP_DEFINE(boot_bootstrap_console,
               INIT_OP_DEP(atcons_bootstrap, true),
               INIT_OP_DEP(uart_bootstrap, true));

static int __init
boot_setup_console(void)
{
    return 0;
}

INIT_OP_DEFINE(boot_setup_console,
               INIT_OP_DEP(atcons_setup, true),
               INIT_OP_DEP(uart_setup, true));

static int __init
boot_load_vm_page_zones(void)
{
    return 0;
}

INIT_OP_DEFINE(boot_load_vm_page_zones,
               INIT_OP_DEP(biosmem_setup, true));

static int __init
boot_setup_intr(void)
{
    return 0;
}

INIT_OP_DEFINE(boot_setup_intr,
               INIT_OP_DEP(acpi_setup, true));

#ifdef CONFIG_PERFMON
static int __init
boot_setup_pmu(void)
{
    return 0;
}

#ifdef CONFIG_X86_PMU_AMD
#define BOOT_PMU_AMD_INIT_OP_DEPS \
               INIT_OP_DEP(pmu_amd_setup, false),
#else /* CONFIG_X86_PMU_AMD */
#define BOOT_PMU_AMD_INIT_OP_DEPS
#endif /* CONFIG_X86_PMU_AMD */

#ifdef CONFIG_X86_PMU_INTEL
#define BOOT_PMU_INTEL_INIT_OP_DEPS \
               INIT_OP_DEP(pmu_intel_setup, false),
#else /* CONFIG_X86_PMU_INTEL */
#define BOOT_PMU_INTEL_INIT_OP_DEPS
#endif /* CONFIG_X86_PMU_INTEL */

INIT_OP_DEFINE(boot_setup_pmu,
               BOOT_PMU_AMD_INIT_OP_DEPS
               BOOT_PMU_INTEL_INIT_OP_DEPS);
#endif /* CONFIG_PERFMON */

static int __init
boot_setup_shutdown(void)
{
    return 0;
}

INIT_OP_DEFINE(boot_setup_shutdown,
               INIT_OP_DEP(acpi_setup, true),
               INIT_OP_DEP(cpu_setup_shutdown, true));


code:
/*
 * Copyright (c) 2010-2014 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */

#ifndef X86_BOOT_H
#define X86_BOOT_H

#include <stdnoreturn.h>

#include <kern/macros.h>
#include <machine/page.h>
#include <machine/pmap.h>

/*
 * Size of the stack used when booting a processor.
 */
#define BOOT_STACK_SIZE PAGE_SIZE

/*
 * Macros used by the very early panic functions.
 */
#define BOOT_CGAMEM     0xb8000
#define BOOT_CGACHARS   (80 * 25)
#define BOOT_CGACOLOR   0x7

/*
 * The kernel is physically loaded at BOOT_OFFSET by the boot loader. It
 * is divided in two parts: the .boot section which uses physical addresses
 * and the main kernel code and data at PMAP_KERNEL_OFFSET.
 *
 * See the linker script for more information.
 */
#define BOOT_OFFSET DECL_CONST(0x100000, UL)

/*
 * Virtual to physical address translation macro.
 */
#define BOOT_VTOP(addr) ((addr) - PMAP_KERNEL_OFFSET)

/*
 * Address where the MP trampoline code is copied and run at.
 *
 * It must reside at a free location in the first segment and be page
 * aligned.
 */
#define BOOT_MP_TRAMPOLINE_ADDR 0x7000

#ifndef __ASSEMBLER__

#include <kern/init.h>
#include <machine/multiboot.h>
#include <machine/pmap.h>

/*
 * Functions and data used before paging is enabled must be part of the .boot
 * and .bootdata sections respectively, so that they use physical addresses.
 * Once paging is enabled, their access relies on the kernel identity mapping.
 */
#define __boot __section(".boot.text")
#define __bootdata __section(".boot.data") __attribute__((used))

/*
 * Boundaries of the .boot section.
 */
extern char _boot;
extern char _boot_end;

/*
 * Size of the trampoline code used for APs.
 */
extern uint32_t boot_mp_trampoline_size;

/*
 * Address of the MP trampoline code.
 */
void boot_mp_trampoline(void);

/*
 * Helper functions available before paging is enabled.
 *
 * Any memory passed to these must also be accessible without paging.
 */
void * boot_memcpy(void *dest, const void *src, size_t n);
void * boot_memmove(void *dest, const void *src, size_t n);
void * boot_memset(void *s, int c, size_t n);
size_t boot_strlen(const char *s);
noreturn void boot_panic(const char *s);

/*
 * This function is called by the bootstrap code before paging is enabled.
 * It establishes a direct mapping of the kernel at virtual addresses and
 * returns the physical address of the page directory. It is up to the
 * caller to actually enable paging.
 */
pmap_pte_t * boot_setup_paging(struct multiboot_raw_info *mbi,
                               unsigned long eax);

/*
 * Main entry point, called directly after basic paging is initialized.
 */
void boot_main(void);

/*
 * Entry point for APs.
 */
void boot_ap_main(void);

void boot_alloc_ap_stacks(void);

void boot_set_ap_id(unsigned int ap_id);

/*
 * Log kernel version and other architecture-specific information.
 */
void boot_log_info(void);

/*
 * This init operation provides :
 *  - boot data are saved
 */
INIT_OP_DECLARE(boot_save_data);

/*
 * This init operation provides :
 *  - all console devices are bootstrapped
 */
INIT_OP_DECLARE(boot_bootstrap_console);

/*
 * This init operation provides :
 *  - all console devices are fully initialized
 */
INIT_OP_DECLARE(boot_setup_console);

/*
 * This init operation provides :
 *  - physical memory has been loaded to the VM system
 */
INIT_OP_DECLARE(boot_load_vm_page_zones);

/*
 * This init operation provides :
 *  - all interrupt controllers have been registered
 */
INIT_OP_DECLARE(boot_setup_intr);

/*
 * This init operation provides :
 *  - all PMU drivers have probed hardware
 */
INIT_OP_DECLARE(boot_setup_pmu);

/*
 * This init operation provides :
 *  - all shutdown operations have been registered
 */
INIT_OP_DECLARE(boot_setup_shutdown);

#endif /* __ASSEMBLER__ */

#endif /* X86_BOOT_H */


code:
/*
 * Copyright (c) 2010, 2012, 2013 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */

#include <machine/asm.h>
#include <machine/cpu.h>
#include <machine/boot.h>
#include <machine/multiboot.h>
#include <machine/page.h>
#include <machine/pmap.h>

/*
 * Boot GDT segment selectors.
 */
#define BOOT_GDT_SEL_NULL   0
#define BOOT_GDT_SEL_CODE   8
#define BOOT_GDT_SEL_DATA   16
#define BOOT_GDT_SEL_CODE64 24
#define BOOT_GDT_SEL_TLS    24

/*
 * Convert a physical address in the .boot section to its real address in
 * the MP trampoline code.
 */
#define BOOT_MP_ADDR_PTOT(addr) (BOOT_MP_TRAMPOLINE_ADDR + (addr) \
                                 - boot_mp_trampoline)

.section .boot.hdr, "awx"
.code32

 /*
  * Multiboot header.
  */
ASM_DATA(boot_header)
 .long MULTIBOOT_OS_MAGIC
 .long MULTIBOOT_OS_FLAGS
 .long -(MULTIBOOT_OS_FLAGS + MULTIBOOT_OS_MAGIC)
ASM_END(boot_header)

/*
 * Entry point.
 */
ASM_ENTRY(boot_start)
 lgdt boot_gdtr

 /* Keep %eax and %ebx */
 movl $BOOT_GDT_SEL_DATA, %ecx
 movl %ecx, %ds
 movl %ecx, %es
 movl %ecx, %ss
 xorl %ecx, %ecx
 movl %ecx, %fs
 movl %ecx, %gs
 ljmp $BOOT_GDT_SEL_CODE, $1f

1:
 movl $(boot_stack + BOOT_STACK_SIZE), %esp

#ifdef __LP64__
 call boot_check_long_mode
 call boot_setup_tls
 call boot_setup_long_mode

 /*
  * At this point, the processor runs in long mode, but still uses the
  * compatibility mode code segment. Switch to 64-bit mode with a far jump.
  */
 ljmp $BOOT_GDT_SEL_CODE64, $1f

1:
 .code64
 movl %ebx, %edi
 movl %eax, %esi
#else /* __LP64__ */
 call boot_build_tls_seg_desc
 movl $BOOT_GDT_SEL_TLS, %ecx
 movl %ecx, %gs

 pushl %eax
 pushl %ebx
#endif /* __LP64__ */

 call boot_setup_paging

#ifdef __LP64__
 movq %rax, %cr3
 movq $(boot_stack + BOOT_STACK_SIZE), %rsp
#else /* __LP64__ */
 movl %eax, %cr3
 movl %cr0, %eax
 orl $CPU_CR0_PG, %eax
 movl %eax, %cr0
 ljmp $BOOT_GDT_SEL_CODE, $1f

1:
 movl $(boot_stack + BOOT_STACK_SIZE), %esp
#endif /* __LP64__ */

 xorl %ebp, %ebp
 call boot_main

 /* Never reached */
 nop
ASM_END(boot_start)

.code32

ASM_DATA(boot_gdtr)
 .word boot_gdt_end - boot_gdt - 1
 .long boot_gdt
ASM_END(boot_gdtr)

#ifdef __LP64__

/*
 * The %eax and %ebx registers must be preserved.
 */

ASM_ENTRY(boot_check_long_mode)
 pushl %eax
 pushl %ebx
 movl $CPU_CPUID_EXT_BIT, %eax
 cpuid
 cmpl $CPU_CPUID_EXT_BIT, %eax
 jbe boot_no_long_mode
 movl $(CPU_CPUID_EXT_BIT | 1), %eax
 cpuid
 testl $CPU_CPUID_EXT1_EDX_LM, %edx
 jz boot_no_long_mode
 popl %ebx
 popl %eax
 ret
ASM_END(boot_check_long_mode)

ASM_ENTRY(boot_no_long_mode)
 movl $boot_panic_long_mode_msg, %esi
 movl $BOOT_CGAMEM, %edi
 movl $(BOOT_CGAMEM + (BOOT_CGACHARS * 2)), %edx
 movw $(BOOT_CGACOLOR << 8), %ax

1:
 movb (%esi), %al
 testb %al, %al
 jz 1f
 movw %ax, (%edi)
 incl %esi
 add $2, %edi
 cmpl %edx, %edi
 jae 2f
 jmp 1b

1:
 cmpl %edx, %edi
 jae 2f
 movw $((BOOT_CGACOLOR << 8) + ' '), (%edi)
 add $2, %edi
 jmp 1b

2:
 hlt
 jmp 2b
ASM_END(boot_no_long_mode)

ASM_ENTRY(boot_setup_long_mode)
 /* Set PML4[0] */
 movl $boot_pdpt, %edx
 orl $(PMAP_PTE_RW | PMAP_PTE_P), %edx
 movl %edx, boot_pml4

 /* Set PDPT[0] through PDPT[3] */
 movl $boot_pdir, %edx
 orl $(PMAP_PTE_RW | PMAP_PTE_P), %edx
 movl $boot_pdpt, %edi
 movl $4, %ecx

1:
 movl %edx, (%edi)
 addl $PAGE_SIZE, %edx
 addl $8, %edi
 loop 1b

 /* Set PDIR[0] through PDIR[2047] */
 movl $(PMAP_PTE_PS | PMAP_PTE_RW | PMAP_PTE_P), %edx
 movl $boot_pdir, %edi
 movl $2048, %ecx

1:
 movl %edx, (%edi)
 addl $(1 << PMAP_L1_SKIP), %edx
 addl $8, %edi
 loop 1b

 /* Switch to long mode */
 movl %eax, %edi
 movl %cr4, %eax
 orl $CPU_CR4_PAE, %eax
 movl %eax, %cr4
 movl $boot_pml4, %eax
 movl %eax, %cr3
 movl $CPU_MSR_EFER, %ecx
 rdmsr
 orl $CPU_EFER_LME, %eax
 wrmsr
 movl %cr0, %eax
 orl $CPU_CR0_PG, %eax
 movl %eax, %cr0
 ljmp $BOOT_GDT_SEL_CODE, $1f

1:
 movl %edi, %eax
 ret
ASM_END(boot_setup_long_mode)

ASM_ENTRY(boot_setup_tls)
 pushl %eax
 movl $boot_tls_seg, %eax
 movl $0, %edx
 movl $CPU_MSR_GSBASE, %ecx
 wrmsr
 popl %eax
 ret
ASM_END(boot_setup_tls)

#else /* __LP64__ */

/*
 * Complete the temporary boot TLS segment descriptor and copy it into
 * the boot GDT.
 *
 * The %eax and %ebx registers must be preserved.
 */
ASM_ENTRY(boot_build_tls_seg_desc)
 pushl %eax

 /* Load boot_tls_seg_desc address */
 movl $boot_tls_seg_desc, %ecx

 /* Add the base 15:0 bits to boot_tls_seg_desc.low */
 movl $boot_tls_seg, %eax
 shll $16, %eax
 orl %eax, (%ecx)

 /* Add the base 23:16 bits to boot_tls_seg_desc.high */
 movl $boot_tls_seg, %eax
 shrl $16, %eax
 andl $0xff, %eax
 orl %eax, 4(%ecx)

 /* Add the base 31:24 bits to boot_tls_seg_desc.high */
 movl $boot_tls_seg, %eax
 andl $0xff000000, %eax
 orl %eax, 4(%ecx)

 /* Load boot_gdt[BOOT_GDT_SEL_TLS] address */
 movl $boot_gdt + BOOT_GDT_SEL_TLS, %edx

 /* Set boot_gdt[BOOT_GDT_SEL_TLS].low */
 movl (%ecx), %eax
 movl %eax, (%edx)

 /* Set boot_gdt[BOOT_GDT_SEL_TLS].high */
 movl 4(%ecx), %eax
 movl %eax, 4(%edx)

 popl %eax
 ret
ASM_END(boot_build_tls_seg_desc)

#endif /* __LP64__ */

/*
 * This is where an AP runs after leaving the trampoline code.
 */
ASM_ENTRY(boot_ap_start32)
 /*
  * Set up the GDT again, because the current one is from the trampoline code
  * which isn't part of the identity mapping and won't be available once paging
  * is enabled.
  */
 lgdt boot_gdtr
 movl $BOOT_GDT_SEL_DATA, %eax
 movl %eax, %ds
 movl %eax, %es
 movl %eax, %ss
 xorl %eax, %eax
 movl %eax, %fs
 movl $BOOT_GDT_SEL_TLS, %eax
 movl %eax, %gs
 ljmp $BOOT_GDT_SEL_CODE, $1f

1:
 movl $(boot_ap_stack + BOOT_STACK_SIZE), %esp

#ifdef __LP64__
 call boot_setup_tls
 call boot_setup_long_mode
 ljmp $BOOT_GDT_SEL_CODE64, $1f

1:
 .code64
#endif /* __LP64__ */

 call boot_ap_setup

#ifdef __LP64__
 movq %rax, %cr3
#else /* __LP64__ */
 movl %eax, %cr3
 movl %cr0, %eax
 orl $CPU_CR0_PG, %eax
 movl %eax, %cr0
 ljmp $BOOT_GDT_SEL_CODE, $1f

1:
#endif /* __LP64__ */

 call boot_get_ap_stack

#ifdef __LP64__
 movq %rax, %rsp
 addq $BOOT_STACK_SIZE, %rsp
#else /* __LP64__ */
 movl %eax, %esp
 addl $BOOT_STACK_SIZE, %esp
#endif /* __LP64__ */

 xorl %ebp, %ebp
 call boot_ap_main

 /* Never reached */
 nop
ASM_END(boot_ap_start32)

.code32

/*
 * This part, including the GDT, is the MP trampoline code run by APs
 * on startup. It is copied at a fixed location in the first segment and
 * must enable protected mode to jump back into the kernel.
 */
ASM_ENTRY(boot_mp_trampoline)
 .code16
 cli
 xorw %ax, %ax
 movw %ax, %ds
 movw %ax, %es
 movw %ax, %fs
 movw %ax, %gs
 movw %ax, %ss
 lgdt BOOT_MP_ADDR_PTOT(boot_ap_gdtr)
 movl %cr0, %eax
 orl $CPU_CR0_PE, %eax
 movl %eax, %cr0
 ljmp $BOOT_GDT_SEL_CODE, $BOOT_MP_ADDR_PTOT(1f)

.align 4
1:
 .code32
 movl $BOOT_GDT_SEL_DATA, %eax
 movl %eax, %ds
 movl %eax, %es
 movl %eax, %ss
 xorl %eax, %eax
 movl %eax, %fs
 movl %eax, %gs
 ljmp $BOOT_GDT_SEL_CODE, $boot_ap_start32
ASM_END(boot_mp_trampoline)

ASM_DATA(boot_ap_gdtr)
 .word boot_gdt_end - boot_gdt - 1
 .long BOOT_MP_ADDR_PTOT(boot_gdt)
ASM_END(boot_ap_gdtr)

ASM_DATA(boot_gdt)
 .quad 0x0000000000000000   /* Null descriptor */
 .quad 0x00cf9a000000ffff   /* Code segment descriptor */
 .quad 0x00cf92000000ffff   /* Data segment descriptor */
#ifdef __LP64__
 .quad 0x00209a0000000000   /* 64-bit code segment selector */
#else /* __LP64__ */
 .quad 0x0                  /* TLS segment descriptor, filled at boot time */
#endif /* __LP64__ */
ASM_END(boot_gdt)
boot_gdt_end:

ASM_DATA(boot_mp_trampoline_size)
 .long . - boot_mp_trampoline
ASM_END(boot_mp_trampoline_size)


code:
/*
 * Copyright (c) 2010-2017 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 */

#include <assert.h>
#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>

#include <kern/console.h>
#include <kern/init.h>
#include <kern/cbuf.h>
#include <kern/macros.h>
#include <machine/io.h>
#include <machine/cga.h>
#include <vm/vm_page.h>

/*
 * Screen dimensions.
 */
#define CGA_COLUMNS 80
#define CGA_LINES   25

/*
 * Text mode mapped memory and size.
 */
#define CGA_MEMORY              0xb8000
#define CGA_MEMORY_LINE_SIZE    (CGA_COLUMNS * 2)
#define CGA_MEMORY_SIZE         (CGA_MEMORY_LINE_SIZE * CGA_LINES)

/*
 * I/O ports.
 */
#define CGA_PORT_MISC_OUT_READ          0x3cc
#define CGA_PORT_MISC_OUT_WRITE         0x3c2
#define CGA_PORT_CRTC_ADDR              0x3d4
#define CGA_PORT_CRTC_DATA              0x3d5

/*
 * Miscellaneous output register bits.
 */
#define CGA_MISC_OUT_IOAS               0x1

/*
 * CRTC registers.
 */
#define CGA_CRTC_CURSOR_START_REG       0xa
#define CGA_CRTC_CURSOR_LOC_HIGH_REG    0xe
#define CGA_CRTC_CURSOR_LOC_LOW_REG     0xf

/*
 * Cursor start register bits.
 */
#define CGA_CSR_DISABLED    0x10

/*
 * Foreground screen color.
 */
#define CGA_FOREGROUND_COLOR 0x7

/*
 * Number of spaces to display for a tabulation.
 */
#define CGA_TABULATION_SPACES 8

static void *cga_memory __read_mostly;

#define CGA_BACK_BUFFER_SIZE (64 * 1024)

#if CGA_BACK_BUFFER_SIZE < CGA_MEMORY_SIZE
#error "back buffer size must be at least as large as video memory"
#endif

#define CGA_SCROLL_PAGE ((CGA_LINES / 2) * CGA_MEMORY_LINE_SIZE)

/*
 * Back buffer.
 */
struct cga_bbuf {
    struct cbuf cbuf;
    size_t view;
    size_t cursor;
    char buf[CGA_BACK_BUFFER_SIZE];
    bool cursor_enabled;
};

static struct cga_bbuf cga_bbuf;

static uint16_t
cga_build_cell(char c)
{
    return (CGA_FOREGROUND_COLOR << 8) | c;
}

static void
cga_write(size_t index, const void *ptr, size_t size)
{
    assert((index + size) <= CGA_MEMORY_SIZE);
    memcpy(cga_memory + index, ptr, size);
}

static uint16_t
cga_get_cursor_position(void)
{
    uint16_t tmp;

    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_LOC_HIGH_REG);
    tmp = io_read_byte(CGA_PORT_CRTC_DATA) << 8;
    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_LOC_LOW_REG);
    tmp |= io_read_byte(CGA_PORT_CRTC_DATA);

    return tmp;
}

static void
cga_set_cursor_position(uint16_t position)
{
    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_LOC_HIGH_REG);
    io_write_byte(CGA_PORT_CRTC_DATA, position >> 8);
    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_LOC_LOW_REG);
    io_write_byte(CGA_PORT_CRTC_DATA, position & 0xff);
}

static void
cga_enable_cursor(void)
{
    uint8_t tmp;

    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_START_REG);
    tmp = io_read_byte(CGA_PORT_CRTC_DATA);
    io_write_byte(CGA_PORT_CRTC_DATA, tmp & ~CGA_CSR_DISABLED);
}

static void
cga_disable_cursor(void)
{
    uint8_t tmp;

    io_write_byte(CGA_PORT_CRTC_ADDR, CGA_CRTC_CURSOR_START_REG);
    tmp = io_read_byte(CGA_PORT_CRTC_DATA);
    io_write_byte(CGA_PORT_CRTC_DATA, tmp | CGA_CSR_DISABLED);
}

static void
cga_bbuf_init(struct cga_bbuf *bbuf, size_t cursor)
{
    cbuf_init(&bbuf->cbuf, bbuf->buf, sizeof(bbuf->buf));
    bbuf->view = cbuf_start(&bbuf->cbuf);
    cbuf_write(&bbuf->cbuf, bbuf->view, cga_memory, CGA_MEMORY_SIZE);
    bbuf->cursor = bbuf->view + cursor;
    bbuf->cursor_enabled = true;
}

static size_t
cga_bbuf_cursor_offset(const struct cga_bbuf *bbuf)
{
    return bbuf->cursor - bbuf->view;
}

static int
cga_bbuf_get_phys_cursor(const struct cga_bbuf *bbuf, uint16_t *cursorp)
{
    uint16_t cursor;

    cursor = cga_bbuf_cursor_offset(bbuf);
    assert((cursor & 1) == 0);

    if (cursor >= CGA_MEMORY_SIZE) {
        return ENODEV;
    }

    *cursorp = (cursor >> 1);
    return 0;
}

static void
cga_bbuf_update_phys_cursor(struct cga_bbuf *bbuf)
{
    bool cursor_enabled;
    uint16_t cursor = 0;
    int error;

    error = cga_bbuf_get_phys_cursor(bbuf, &cursor);
    cursor_enabled = !error;

    if (cursor_enabled != bbuf->cursor_enabled) {
        bbuf->cursor_enabled = cursor_enabled;

        if (cursor_enabled) {
            cga_enable_cursor();
        } else {
            cga_disable_cursor();
        }
    }

    if (cursor_enabled) {
        cga_set_cursor_position(cursor);
    }
}

static void
cga_bbuf_redraw(struct cga_bbuf *bbuf)
{
    size_t size;
    int error;

    size = CGA_MEMORY_SIZE;
    error = cbuf_read(&bbuf->cbuf, bbuf->view, cga_memory, &size);
    assert(!error);
    assert(size == CGA_MEMORY_SIZE);
    cga_bbuf_update_phys_cursor(bbuf);
}

static bool
cga_bbuf_view_needs_scrolling(const struct cga_bbuf *bbuf)
{
    size_t view_size;

    view_size = cbuf_end(&bbuf->cbuf) - bbuf->view;

    if (view_size > CGA_MEMORY_SIZE) {
        return true;
    }

    /* Consider the cursor as a valid cell */
    view_size = (bbuf->cursor + 1) - bbuf->view;

    if (view_size > CGA_MEMORY_SIZE) {
        return true;
    }

    return false;
}

static void
cga_bbuf_scroll_once(struct cga_bbuf *bbuf)
{
    uint16_t spaces[CGA_COLUMNS];
    size_t i;

    for (i = 0; i < ARRAY_SIZE(spaces); i++) {
        spaces[i] = cga_build_cell(' ');
    }

    cbuf_write(&bbuf->cbuf, cbuf_end(&bbuf->cbuf), spaces, sizeof(spaces));
    bbuf->view += sizeof(spaces);
    cga_bbuf_redraw(bbuf);
}

static void
cga_bbuf_reset_view(struct cga_bbuf *bbuf)
{
    if ((bbuf->view + CGA_MEMORY_SIZE) == cbuf_end(&bbuf->cbuf)) {
        return;
    }

    bbuf->view = cbuf_end(&bbuf->cbuf) - CGA_MEMORY_SIZE;
    cga_bbuf_redraw(bbuf);
}

static void
cga_bbuf_push(struct cga_bbuf *bbuf, char c)
{
    size_t offset;
    uint16_t cell;

    cga_bbuf_reset_view(bbuf);

    cell = cga_build_cell(c);
    cbuf_write(&bbuf->cbuf, bbuf->cursor, &cell, sizeof(cell));
    offset = cga_bbuf_cursor_offset(bbuf);
    bbuf->cursor += sizeof(cell);

    if (cga_bbuf_view_needs_scrolling(bbuf)) {
        cga_bbuf_scroll_once(bbuf);
    } else {
        cga_write(offset, &cell, sizeof(cell));
        cga_bbuf_update_phys_cursor(bbuf);
    }
}

static void
cga_bbuf_newline(struct cga_bbuf *bbuf)
{
    uint16_t cursor = 0, spaces[CGA_COLUMNS];
    size_t i, nr_spaces, offset, size;
    int error;

    cga_bbuf_reset_view(bbuf);

    error = cga_bbuf_get_phys_cursor(bbuf, &cursor);
    assert(!error);

    nr_spaces = CGA_COLUMNS - (cursor % CGA_COLUMNS);

    for (i = 0; i < nr_spaces; i++) {
        spaces[i] = cga_build_cell(' ');
    }

    /*
     * The cursor may not point at the end of the view, in which case
     * any existing data must be preserved.
     */
    size = sizeof(spaces);
    cbuf_read(&bbuf->cbuf, bbuf->cursor, spaces, &size);

    cbuf_write(&bbuf->cbuf, bbuf->cursor,
               spaces, nr_spaces * sizeof(spaces[0]));
    offset = cga_bbuf_cursor_offset(bbuf);
    bbuf->cursor += nr_spaces * sizeof(spaces[0]);

    if (cga_bbuf_view_needs_scrolling(bbuf)) {
        cga_bbuf_scroll_once(bbuf);
    } else {
        cga_write(offset, spaces, nr_spaces * sizeof(spaces[0]));
        cga_bbuf_update_phys_cursor(bbuf);
    }

    cga_bbuf_update_phys_cursor(bbuf);
}

static void
cga_bbuf_move_cursor(struct cga_bbuf *bbuf, bool forward)
{
    cga_bbuf_reset_view(bbuf);

    if ((!forward && (bbuf->cursor == bbuf->view))
        || (forward && (bbuf->cursor == cbuf_end(&bbuf->cbuf)))) {
        return;
    }

    if (forward) {
        bbuf->cursor += sizeof(uint16_t);
    } else {
        bbuf->cursor -= sizeof(uint16_t);
    }

    cga_bbuf_update_phys_cursor(bbuf);
}

static void
cga_bbuf_move_cursor_left(struct cga_bbuf *bbuf)
{
    cga_bbuf_move_cursor(bbuf, false);
}

static void
cga_bbuf_move_cursor_right(struct cga_bbuf *bbuf)
{
    cga_bbuf_move_cursor(bbuf, true);
}

static void
cga_bbuf_backspace(struct cga_bbuf *bbuf)
{
    cga_bbuf_move_cursor_left(bbuf);
}

static void
cga_bbuf_scroll_up(struct cga_bbuf *bbuf)
{
    size_t start, size;

    bbuf->view -= CGA_SCROLL_PAGE;

    /* The back buffer size is a power-of-two, not a line multiple */
    size = cbuf_size(&bbuf->cbuf);
    size -= size % CGA_MEMORY_LINE_SIZE;
    start = cbuf_end(&bbuf->cbuf) - size;

    if ((bbuf->view - start) >= size) {
        bbuf->view = start;
    }

    cga_bbuf_redraw(bbuf);
}

static void
cga_bbuf_scroll_down(struct cga_bbuf *bbuf)
{
    size_t end;

    bbuf->view += CGA_SCROLL_PAGE;
    end = bbuf->view + CGA_MEMORY_SIZE;

    if (!cbuf_range_valid(&bbuf->cbuf, bbuf->view, end)) {
        bbuf->view = cbuf_end(&bbuf->cbuf) - CGA_MEMORY_SIZE;
    }

    cga_bbuf_redraw(bbuf);
}

void
cga_putc(char c)
{
    unsigned int i;

    switch (c) {
    case '\r':
        return;
    case '\n':
        cga_bbuf_newline(&cga_bbuf);
        break;
    case '\b':
        cga_bbuf_backspace(&cga_bbuf);
        break;
    case '\t':
        for(i = 0; i < CGA_TABULATION_SPACES; i++) {
            cga_putc(' ');
        }

        break;
    case CONSOLE_SCROLL_UP:
        cga_bbuf_scroll_up(&cga_bbuf);
        break;
    case CONSOLE_SCROLL_DOWN:
        cga_bbuf_scroll_down(&cga_bbuf);
        break;
    default:
        cga_bbuf_push(&cga_bbuf, c);
    }
}

static void __init
cga_setup_misc_out(void)
{
    uint8_t reg;

    reg = io_read_byte(CGA_PORT_MISC_OUT_READ);

    if (!(reg & CGA_MISC_OUT_IOAS)) {
        reg |= CGA_MISC_OUT_IOAS;
        io_write_byte(CGA_PORT_MISC_OUT_WRITE, reg);
    }
}

static int __init
cga_setup(void)
{
    cga_memory = (void *)vm_page_direct_va(CGA_MEMORY);
    cga_setup_misc_out();
    cga_bbuf_init(&cga_bbuf, cga_get_cursor_position());
    return 0;
}

INIT_OP_DEFINE(cga_setup);

void
cga_cursor_left(void)
{
    cga_bbuf_move_cursor_left(&cga_bbuf);
}

void
cga_cursor_right(void)
{
    cga_bbuf_move_cursor_right(&cga_bbuf);
}


code:
/*
 * Copyright (c) 2010, 2012 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 *
 *
 * Tiny CGA driver.
 */

#ifndef X86_CGA_H
#define X86_CGA_H

#include <kern/init.h>

/*
 * Append a character to the CGA screen.
 */
void cga_putc(char c);

/*
 * Cursor control functions.
 */
void cga_cursor_left(void);
void cga_cursor_right(void);

/*
 * This init operation provides :
 *  - module fully initialized
 */
INIT_OP_DECLARE(cga_setup);

#endif /* X86_CGA_H */


code:
/*
 * Copyright (c) 2012 Richard Braun.
 *
 * 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 3 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, see <http://www.gnu.org/licenses/>.
 *
 *
 * Architecture specific additions to the build system config.h header.
 */

/*
 * Avoid obscure bugs due to this historical built-in macro.
 */
#ifdef i386
#undef i386
#endif