OSDev.org

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

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

Code: Select all

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

Code: Select all

pagemap_t( u64 init = ~0UL );

Code: Select all

explicit pagemap_t( u64 init = ~0UL );