/*
* ntloader -- Microsoft Windows NT6+ loader
* Copyright (C) 2025 A1ive.
*
* ntloader 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.
*
* ntloader 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 ntloader. If not, see .
*/
#include
#include
#include "bootapp.h"
#include "ntloader.h"
#include "pmapi.h"
#include "mm.h"
#if defined(__i386__) || defined(__x86_64__)
/*
* MM_MGMT_OVERHEAD is an upper bound of management overhead of
* each region, with any possible padding taken into account.
*
* The value must be large enough to make sure memalign(align, size)
* always succeeds after a successful call to
* bios_mm_init_region(addr, size + align + MM_MGMT_OVERHEAD),
* for any given addr, align and size (assuming no interger overflow).
*
* The worst case which has maximum overhead is shown in the figure below:
*
* +-- addr
* v |<- size + align ->|
* +---------+----------------+----------------+------------------+---------+
* | padding | mm_region | mm_header | usable bytes | padding |
* +---------+----------------+----------------+------------------+---------+
* |<- a ->|<- b ->|<- c ->|<- d ->|<- e ->|
* ^
* b == sizeof (struct mm_region) | / Assuming no other suitable
* c == sizeof (struct mm_header) | | block is available, then:
* d == size + align +-| If align == 0, this will be
* | the pointer returned by next
* Assuming addr % MM_ALIGN == 1, then: | memalign(align, size).
* a == MM_ALIGN - 1 | If align > 0, this chunk may
* | need to be split to fulfill
* Assuming d % MM_ALIGN == 1, then: | alignment requirements, and
* e == MM_ALIGN - 1 | the returned pointer may be
* \ inside these usable bytes.
* Therefore, the maximum overhead is:
* a + b + c + e == (MM_ALIGN - 1) + sizeof (struct mm_region)
* + sizeof (struct mm_header) + (MM_ALIGN - 1)
*/
#define MM_MGMT_OVERHEAD \
((MM_ALIGN - 1) \
+ sizeof (struct mm_region) \
+ sizeof (struct mm_header) \
+ (MM_ALIGN - 1))
/* The size passed to mm_add_region_fn() is aligned up by this value. */
#define MM_HEAP_GROW_ALIGN 4096
/* Minimal heap growth granularity when existing heap space is exhausted. */
#define MM_HEAP_GROW_EXTRA 0x100000
mm_region_t mm_base;
mm_add_region_func_t mm_add_region_fn;
/* Get a header from the pointer PTR, and set *P and *R to a pointer
* to the header and a pointer to its region, respectively. PTR must
* be allocated. */
static void
get_header_from_pointer (void *ptr, mm_header_t *p, mm_region_t *r)
{
if ((intptr_t) ptr & (MM_ALIGN - 1))
die ("unaligned pointer %p\n", ptr);
for (*r = mm_base; *r; *r = (*r)->next)
if ((intptr_t) ptr > (intptr_t) ((*r) + 1)
&& (intptr_t) ptr <= (intptr_t) ((*r) + 1) + (*r)->size)
break;
if (! *r)
die ("out of range pointer %p\n", ptr);
*p = (mm_header_t) ptr - 1;
if ((*p)->magic == MM_FREE_MAGIC)
die ("double free at %p\n", *p);
if ((*p)->magic != MM_ALLOC_MAGIC)
die ("alloc magic is broken at %p: %zx\n", *p, (*p)->magic);
}
/* Allocate the number of units N with the alignment ALIGN from the ring
* buffer given in *FIRST. ALIGN must be a power of two. Both N and
* ALIGN are in units of MM_ALIGN. Return a non-NULL if successful,
* otherwise return NULL.
*
* Note: because in certain circumstances we need to adjust the ->next
* pointer of the previous block, we iterate over the singly linked
* list with the pair (prev, cur). *FIRST is our initial previous, and
* *FIRST->next is our initial current pointer. So we will actually
* allocate from *FIRST->next first and *FIRST itself last.
*/
static void *
real_malloc (mm_header_t *first, size_t n, size_t align)
{
mm_header_t cur, prev;
/* When everything is allocated side effect is that *first will have alloc
* magic marked, meaning that there is no room in this region. */
if ((*first)->magic == MM_ALLOC_MAGIC)
return 0;
/* Try to search free slot for allocation in this memory region. */
for (prev = *first, cur = prev->next; ; prev = cur, cur = cur->next)
{
uint64_t extra;
extra = ((intptr_t) (cur + 1) >> MM_ALIGN_LOG2) & (align - 1);
if (extra)
extra = align - extra;
if (! cur)
die ("null in the ring\n");
if (cur->magic != MM_FREE_MAGIC)
die ("free magic is broken at %p: 0x%zx\n", cur, cur->magic);
if (cur->size >= n + extra)
{
extra += (cur->size - extra - n) & (~(align - 1));
if (extra == 0 && cur->size == n)
{
/* There is no special alignment requirement and memory block
* is complete match.
*
* 1. Just mark memory block as allocated and remove it from
* free list.
*
* Result:
* +---------------+ previous block's next
* | alloc, size=n | |
* +---------------+ v
*/
prev->next = cur->next;
}
else if (align == 1 || cur->size == n + extra)
{
/* There might be alignment requirement, when taking it into
* account memory block fits in.
*
* 1. Allocate new area at end of memory block.
* 2. Reduce size of available blocks from original node.
* 3. Mark new area as allocated and "remove" it from free
* list.
*
* Result:
* +---------------+
* | free, size-=n | next --+
* +---------------+ |
* | alloc, size=n | |
* +---------------+ v
*/
cur->size -= n;
cur += cur->size;
}
else if (extra == 0)
{
mm_header_t r;
r = cur + extra + n;
r->magic = MM_FREE_MAGIC;
r->size = cur->size - extra - n;
r->next = cur->next;
prev->next = r;
if (prev == cur)
{
prev = r;
r->next = r;
}
}
else
{
/* There is alignment requirement and there is room in memory
* block. Split memory block to three pieces.
*
* 1. Create new memory block right after section being
* allocated. Mark it as free.
* 2. Add new memory block to free chain.
* 3. Mark current memory block having only extra blocks.
* 4. Advance to aligned block and mark that as allocated and
* "remove" it from free list.
*
* Result:
* +------------------------------+
* | free, size=extra | next --+
* +------------------------------+ |
* | alloc, size=n | |
* +------------------------------+ |
* | free, size=orig.size-extra-n | <------+, next --+
* +------------------------------+ v
*/
mm_header_t r;
r = cur + extra + n;
r->magic = MM_FREE_MAGIC;
r->size = cur->size - extra - n;
r->next = cur;
cur->size = extra;
prev->next = r;
cur += extra;
}
cur->magic = MM_ALLOC_MAGIC;
cur->size = n;
/* Mark find as a start marker for next allocation to fasten it.
* This will have side effect of fragmenting memory as small
* pieces before this will be un-used. */
/* So do it only for chunks under 32K. */
if (n < (0x8000 >> MM_ALIGN_LOG2)
|| *first == cur)
*first = prev;
return cur + 1;
}
/* Search was completed without result. */
if (cur == *first)
break;
}
return 0;
}
/* Allocate SIZE bytes with the alignment ALIGN and return the pointer. */
void *
bios_memalign (size_t align, size_t size)
{
mm_region_t r;
size_t n = ((size + MM_ALIGN - 1) >> MM_ALIGN_LOG2) + 1;
size_t grow;
int count = 0;
if (!mm_base)
goto fail;
if (size > ~(size_t) align)
goto fail;
grow = size + align;
/* We currently assume at least a 32-bit size_t,
* so limiting allocations to - 1MiB
* in name of sanity is beneficial. */
if (grow > ~(size_t) 0x100000)
goto fail;
align = (align >> MM_ALIGN_LOG2);
if (align == 0)
align = 1;
again:
for (r = mm_base; r; r = r->next)
{
void *p;
p = real_malloc (&(r->first), n, align);
if (p)
return p;
}
/* If failed, increase free memory somehow. */
switch (count)
{
case 0:
/* Request additional pages, contiguous */
count++;
/*
* Calculate the necessary size of heap growth (if applicable),
* with region management overhead taken into account.
*/
if (safe_add (grow, MM_MGMT_OVERHEAD, &grow))
goto fail;
/* Preallocate some extra space if heap growth is small. */
grow = max (grow, MM_HEAP_GROW_EXTRA);
/* Align up heap growth to make it friendly to CPU/MMU. */
if (grow > ~(size_t) (MM_HEAP_GROW_ALIGN - 1))
goto fail;
grow = ALIGN_UP (grow, MM_HEAP_GROW_ALIGN);
/* Do the same sanity check again. */
if (grow > ~(size_t) 0x100000)
goto fail;
if (mm_add_region_fn != NULL &&
mm_add_region_fn (grow, MM_ADD_REGION_CONSECUTIVE) == 0)
goto again;
/* fallthrough */
case 1:
/* Request additional pages, anything at all */
count++;
if (mm_add_region_fn != NULL)
{
/*
* Try again even if this fails, in case it was able to partially
* satisfy the request
*/
mm_add_region_fn (grow, MM_ADD_REGION_NONE);
goto again;
}
/* fallthrough */
case 2:
///* Invalidate disk caches. */
//disk_cache_invalidate_all ();
count++;
goto again;
default:
break;
}
fail:
die ("out of memory\n");
return 0;
}
/* Allocate SIZE bytes and return the pointer. */
static void *
bios_malloc (size_t size)
{
return bios_memalign (0, size);
}
/* Deallocate the pointer PTR. */
static void
bios_free (void *ptr)
{
mm_header_t p;
mm_region_t r;
if (! ptr)
return;
get_header_from_pointer (ptr, &p, &r);
if (r->first->magic == MM_ALLOC_MAGIC)
{
p->magic = MM_FREE_MAGIC;
r->first = p->next = p;
}
else
{
mm_header_t cur, prev;
/* Iterate over all blocks in the free ring.
*
* The free ring is arranged from high addresses to low
* addresses, modulo wraparound.
*
* We are looking for a block with a higher address than p or
* whose next address is lower than p.
*/
for (prev = r->first, cur = prev->next; cur <= p || cur->next >= p;
prev = cur, cur = prev->next)
{
if (cur->magic != MM_FREE_MAGIC)
die ("free magic is broken at %p: 0x%zx\n", cur, cur->magic);
/* Deal with wrap-around */
if (cur <= cur->next && (cur > p || cur->next < p))
break;
}
/* mark p as free and insert it between cur and cur->next */
p->magic = MM_FREE_MAGIC;
p->next = cur->next;
cur->next = p;
/*
* If the block we are freeing can be merged with the next
* free block, do that.
*/
if (p->next + p->next->size == p)
{
p->magic = 0;
p->next->size += p->size;
cur->next = p->next;
p = p->next;
}
r->first = cur;
/* Likewise if can be merged with the preceeding free block */
if (cur == p + p->size)
{
cur->magic = 0;
p->size += cur->size;
if (cur == prev)
prev = p;
prev->next = p;
cur = prev;
}
/*
* Set r->first such that the just free()d block is tried first.
* (An allocation is tried from *first->next, and cur->next == p.)
*/
r->first = cur;
}
}
/* Initialize a region starting from ADDR and whose size is SIZE,
* to use it as free space. */
void
bios_mm_init_region (void *addr, size_t size)
{
mm_header_t h;
mm_region_t r, *p, q;
DBG ("Using memory for heap: start=%p, end=%p\n",
addr, (char *) addr + (unsigned int) size);
/* Exclude last 4K to avoid overflows. */
/* If addr + 0x1000 overflows then whole region is in excluded zone. */
if ((intptr_t) addr > ~((intptr_t) 0x1000))
return;
/* If addr + 0x1000 + size overflows then decrease size. */
if (((intptr_t) addr + 0x1000) > ~(intptr_t) size)
size = ((intptr_t) -0x1000) - (intptr_t) addr;
/* Attempt to merge this region with every existing region */
for (p = &mm_base, q = *p; q; p = &(q->next), q = *p)
{
/*
* Is the new region immediately below an existing region? That
* is, is the address of the memory we're adding now (addr) + size
* of the memory we're adding (size) + the bytes we couldn't use
* at the start of the region we're considering (q->pre_size)
* equal to the address of q? In other words, does the memory
* looks like this?
*
* addr q
* |----size-----|-q->pre_size-||
*/
if ((uint8_t *) addr + size + q->pre_size == (uint8_t *) q)
{
/*
* Yes, we can merge the memory starting at addr into the
* existing region from below. Align up addr to MM_ALIGN
* so that our new region has proper alignment.
*/
r = (mm_region_t) ALIGN_UP ((intptr_t) addr, MM_ALIGN);
/* Copy the region data across */
*r = *q;
/* Consider all the new size as pre-size */
r->pre_size += size;
/*
* If we have enough pre-size to create a block, create a
* block with it. Mark it as allocated and pass it to
* free (), which will sort out getting it into the free
* list.
*/
if (r->pre_size >> MM_ALIGN_LOG2)
{
h = (mm_header_t) (r + 1);
/* block size is pre-size converted to cells */
h->size = (r->pre_size >> MM_ALIGN_LOG2);
h->magic = MM_ALLOC_MAGIC;
/* region size grows by block size converted back to bytes */
r->size += h->size << MM_ALIGN_LOG2;
/* adjust pre_size to be accurate */
r->pre_size &= (MM_ALIGN - 1);
*p = r;
bios_free (h + 1);
}
/* Replace the old region with the new region */
*p = r;
return;
}
/*
* Is the new region immediately above an existing region? That
* is:
* q addr
* ||-q->post_size-|----size-----|
*/
if ((uint8_t *) q + sizeof (*q) + q->size + q->post_size ==
(uint8_t *) addr)
{
/*
* Yes! Follow a similar pattern to above, but simpler.
* Our header starts at address - post_size, which should align us
* to a cell boundary.
*
* Cast to (void *) first to avoid the following build error:
* kern/mm.c: In function ‘bios_mm_init_region’:
* kern/mm.c:211:15: error: cast increases required alignment of target type [-Werror=cast-align]
* 211 | h = (mm_header_t) ((uint8_t *) addr - q->post_size);
* | ^
* It is safe to do that because proper alignment is enforced in mm_size_sanity_check().
*/
h = (mm_header_t)(void *) ((uint8_t *) addr - q->post_size);
/* our size is the allocated size plus post_size, in cells */
h->size = (size + q->post_size) >> MM_ALIGN_LOG2;
h->magic = MM_ALLOC_MAGIC;
/* region size grows by block size converted back to bytes */
q->size += h->size << MM_ALIGN_LOG2;
/* adjust new post_size to be accurate */
q->post_size = (q->post_size + size) & (MM_ALIGN - 1);
bios_free (h + 1);
return;
}
}
/*
* If you want to modify the code below, please also take a look at
* MM_MGMT_OVERHEAD and make sure it is synchronized with the code.
*/
/* Allocate a region from the head. */
r = (mm_region_t) ALIGN_UP ((intptr_t) addr, MM_ALIGN);
/* If this region is too small, ignore it. */
if (size < MM_ALIGN + (char *) r - (char *) addr + sizeof (*r))
return;
size -= (char *) r - (char *) addr + sizeof (*r);
h = (mm_header_t) (r + 1);
h->next = h;
h->magic = MM_FREE_MAGIC;
h->size = (size >> MM_ALIGN_LOG2);
r->first = h;
r->pre_size = (intptr_t) r - (intptr_t) addr;
r->size = (h->size << MM_ALIGN_LOG2);
r->post_size = size - r->size;
/* Find where to insert this region. Put a smaller one before bigger ones,
* to prevent fragmentation. */
for (p = &mm_base, q = *p; q; p = &(q->next), q = *p)
if (q->size > r->size)
break;
*p = r;
r->next = q;
}
static void bios_putchar (int c)
{
struct bootapp_callback_params params;
memset (¶ms, 0, sizeof (params));
params.vector.interrupt = 0x10;
params.eax = (0x0e00 | c);
params.ebx = 0x0007;
call_interrupt (¶ms);
}
static int bios_getchar (void)
{
struct bootapp_callback_params params;
memset (¶ms, 0, sizeof (params));
params.vector.interrupt = 0x16;
call_interrupt (¶ms);
return params.al;
}
void __attribute__ ((noreturn)) bios_reboot (void);
#endif
void
bios_init (void)
{
#if defined(__i386__) || defined(__x86_64__)
pm->_reboot = bios_reboot;
pm->_putchar = bios_putchar;
pm->_getchar = bios_getchar;
pm->_malloc = bios_malloc;
pm->_free = bios_free;
#endif
}