Sample x86-64 page manager code (C++)

[jbemmel]

Some sample code that can be used to manage physical memory pages. This structure fits in 4KB ( 1 page ) and supports allocation of both 4K and 2M pages, for an area of 128MB of physical memory.

Note that it is not multi-thread safe.

Code: Select all

#ifndef CPAGEMAP_H
#define CPAGEMAP_H

typedef unsigned long u64;

namespace MyOS {
namespace MM {

/**
 * A bitmap structure that fits in a single 4KB page and covers 128MB of physical memory:
 *
 * 62 * 512 * 4KB pages + 2 * 2MB pages up to 64 * 2MB pages
 */
class pagemap_t {

public:
	static const u64 NO_ENTRY = ~0UL;

	pagemap_t( u64 init = ~0UL );

	u64 alloc4K();
	u64 alloc2M();

	void free4K( u64 frame_4k );
	void free2M( u64 frame_2m );

private:
	u64 _2mbpages;	//< 64 * 2MB page, last two cannot be split
	u64 _unused[ 7 ];
	u64 _4kbsearch[ 8 ];	//< Bit index helper, 1 == free pages available below

	u64 _4kbpages[ 496 ]; //< 62 * 512 * 4KB pages
};

}}

#endif

.cpp file:

Code: Select all

/*
 * CPageMap.cpp
 */
#include "CPageMap.h"

#define assert(x)

namespace MyOS {
namespace MM {

pagemap_t::pagemap_t( u64 init )
{
	for ( u64 i=0; i<sizeof(_4kbsearch)/sizeof(u64); ++i ) {
		_4kbsearch[i] = init;
	}
	_2mbpages = init;
	for ( u64 i=0; i<sizeof(_4kbpages)/sizeof(u64); ++i ) {
		_4kbpages[i] = init;
	}
}

/*
 * Allocates an available 4KB frame
 *
 * Worst case, this implementation references 9 qwords ( in 2 cache lines )
 * It executes 2 0-count operations, and performs 2 or 3 memory writes
 */
u64 pagemap_t::alloc4K() {
	for (u64 i = 0; i < 8; ++i) {
		u64 bits = _4kbsearch[i];
		if ( bits!=0 ) {
			u64 index = __builtin_ctzl( bits );
			u64 index4k = 64 * i + index;
			// for i==8, last 2 bytes represent full 2MB page only
			if (index4k < 496) {
				u64 bits4k = _4kbpages[index4k];
				assert( bits4k );
				u64 bitindex = __builtin_ctzl(bits4k);
				_4kbpages[index4k] &= ~(1UL << bitindex);
				_2mbpages &= ~(1UL << (index4k/8));
				if ( bits4k == (1UL << bitindex)) {
					_4kbsearch[i] &= ~(1UL << index);
				}
				return (index4k * 64 + bitindex) << 12;
			}
		}
	}
	return NO_ENTRY;
}

u64 pagemap_t::alloc2M() {
	if ( _2mbpages!=0 ) {
		// Start at index of pages that can only be allocated as 2MB
		u64 index = 63 - __builtin_clzl( _2mbpages );
		_2mbpages &= ~(1UL << index);

		// Indices 62 and 63 are only allocated as full 2MB pages, but it
		// does not hurt to clear the bits anyway
		// 8 bits to clear, 8*64=512
		_4kbsearch[index/8] &= ~(0xFFUL << 8*(index&7));
		return index<<(9+12);
	}
	return NO_ENTRY;
}

void pagemap_t::free4K( u64 frame_4k ) {
	u64 page = frame_4k >> 12;
	_4kbpages[ page/64 ] |= ( 1UL << (page&63) );
	page /= 64;	// 0..511
	u64 bits = _4kbsearch[ page/64 ];
	if ( (bits & ( 1UL << (page&63)) ) == 0 ) {
		bits |= ( 1UL << (page&63) );
		_4kbsearch[ page/64 ] = bits;

		// If 8 subsequent bits in _4kbsearch are now free, free the 2MB page
		const u64 bytemask = ( 0xFFUL << (page&0x38) );
		if ( (bits & bytemask) == bytemask ) {
			_2mbpages |= ( 1UL << (page/8) );
		}
	}
}

void pagemap_t::free2M( u64 frame_2m ) {
	u64 index = (frame_2m>>(9+12)) & 63;
	assert( ((_2mbpages & ( 1UL << index )) == 0) );
	_2mbpages |= ( 1UL << index );
	_4kbsearch[index/8] |= (0xFFUL << 8*(index&7));

	// Assume bits in _4kbpages are already set correctly
}

}}

#ifdef UNIT_TEST

#include <cstdio>

int main( int argc, char* argv[] )
{
	MyOS::MM::pagemap_t map;

	// Should be possible to allocate 124MB of 4K pages
	for ( int p=0; p<(124<<(20-12)); ++p ) {
		u64 index = map.alloc4K();
		assert( index != MyOS::MM::pagemap_t::NO_ENTRY );
	}

	// and then 2 more 2M pages
	for ( int p=0; p<2; ++p ) {
		u64 index = map.alloc2M();
		assert( index != MyOS::MM::pagemap_t::NO_ENTRY );
		fprintf( stderr, "\n2M[%d]=%lx", p, index );
	}

	// beyond this, we should get NO_ENTRY
	assert( map.alloc4K() == MyOS::MM::pagemap_t::NO_ENTRY );
	assert( map.alloc2M() == MyOS::MM::pagemap_t::NO_ENTRY );

	// Unless we free a page
	map.free4K( 0 );
	assert( map.alloc4K() == 0 );

	map.free2M( 0 );
	assert( map.alloc2M() == 0 );

	// This does not work: Freeing as 2M, and then allocating as 4K pages
	// map.free2M( 0 );
	for ( int p=0; p<512; ++p ) {
		map.free4K( p<<12 );
	}

	for ( int p=0; p<512; ++p ) {
		u64 index = map.alloc4K();
		assert( index != MyOS::MM::pagemap_t::NO_ENTRY );

		// if ( p<65 ) fprintf( stderr, "\n4K[%d]=%lx", p, index );
	}

	// It should be possible to free 512 4K pages and allocate them as 2MB though
	for ( int p=0; p<512; ++p ) {
		map.free4K( p<<12 );
	}
	assert( map.alloc2M() == 0 );

	fprintf( stderr, "\nAll tests passed!\n" );

	return 0;
}

#endif

[alexfru]

And a simple stack, containing physical addresses of free pages (4K only or separate stacks for 4K and 2M pages), would be simpler and easier to work with (need a page? pop. don't need a page anymore? push).

[jbemmel]

Sure, but assuming you would e.g. use 32 bits per page, a single 4KB page could only hold 1024 entries for a total of 1024*4K = 4MB of physical memory.
Moreover, supporting both 4K and 2M pages (and especially recombining them) would require complex logic and even more memory

[alexfru]

At boot time you don't need 4 megs as you receive just a handful of memory regions from the BIOS. The stack entry could describe a contiguous range using start and end addresses. Push and pop would still be loop-free. 0.1-0.2% of RAM isn't a terrible waste. And then another 0.1% of the virtual address space for the recursive mapping and then 25-50% of the address space for the kernel and then FS caches... There will be much worse offenders than this. And it's in a hobby OS, which rarely gets to need all RAM to its last byte. So, why not make things simpler?

[proxy]

For my system I have a stack of pages for "low memory" (pages which are directly accessible in kernel space) and the size is generally unbounded. The trick is to implement the stack as a linked list using the **page itself** as the node in the list. So you only need a single pointer to be the top of the stack.

To help visualize this, imagine a struct which looks like this:

Code: Select all

/* this struct is *exactly* 4096 bytes big */
struct page {
    struct page *next;
    uint8_t reserved[4096 - sizeof(struct page *)];
};

To allocate, I simply pluck the top node off the stack, zero out the pointer which was in first few bytes (we don't want any information leakage to user space) and we're done. Freeing is just as easy, I just cast the page to a "struct page *" and insert it into the list.

So for "sizeof(struct page *)", you can track as many pages as you like, as long as they are mapped into kernel space in some way so they are directly accessible.

[FallenAvatar]

At boot time you don't need 4 megs as you receive just a handful of memory regions from the BIOS.

What is the worst case scenario here? What is the maximum number of entries the BIOS could return?

- Monk

[Brendan]

Hi,

At boot time you don't need 4 megs as you receive just a handful of memory regions from the BIOS.

What is the worst case scenario here? What is the maximum number of entries the BIOS could return?

In theory the only maximum is the range of the 32-bit "continuation value" (or a little over 4 billion entries). In practice you'd choose a conservative/arbitrary limit of your own (e.g. reserve space for 256 entries) and have a "ran out of entries" error message in case you ever need more.


Cheers,

Brendan

[dlarudgus20]

Code: Select all

pagemap_t( u64 init = ~0UL );

Um, It should be explicit, shouldn't it?

Code: Select all

explicit pagemap_t( u64 init = ~0UL );