Cache line Allocator with Lock-free Malloc

alloc_test.cc

#include <gtest/gtest.h>
#include "cache_alloc.h"

TEST(alloc,test){
	cache_alloc<int, 64> a;
}
TEST(alloc,do_alloc){
	cache_alloc<int, 64> a;
	void* t = a.allocate();
	EXPECT_FALSE(t ==NULL);
}

TEST(alloc,address_ok){
	cache_alloc<int, 64> a;
	void* t = a.allocate();
	*reinterpret_cast<int*>(t) = 32;
}
TEST(alloc,aligned){
	cache_alloc<int, 64> a;
	void* ptr = a.allocate();
	EXPECT_EQ(reinterpret_cast<int>(ptr) & 63, 0);
}

TEST(alloc,alloc_and_use){
	cache_alloc<int, 64> a;
	int* t = reinterpret_cast<int*>(a.allocate());
	for(int i=0;i<16;i++){
		t[i] = i;
	}
}

TEST(alloc,alloc_and_use_5times){
	cache_alloc<int, 64> a;
	for(int j=0;j<232;j++){
		int* t = reinterpret_cast<int*>(a.allocate());
		for(int i=0;i<16;i++){
			t[i] = i;
		}
	}
}

#include<vector>
TEST(alloc,alloc_and_free){
	std::vector<int*> allocced;
	cache_alloc<int, 64> a;
	for(int j=0;j<232;j++){
		int* t = reinterpret_cast<int*>(a.allocate());
		for(int i=0;i<16;i++){
			t[i] = i;
		}
		
	}
}

cachealloc.h

#ifndef CACHEALLOC_H
#define CACHEALLOC_H

#define PAGESIZE 4096

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <limits>
#include <list>
#include <assert.h>
template<typename T, int SIZE>
class cache_alloc{
public:
	cache_alloc() throw(): head(NULL){}
	cache_alloc(const cache_alloc&) throw(){}
	template <class U> cache_alloc(const cache_alloc<U, SIZE>&) throw(){}
	~cache_alloc() throw(){}
	
	// メモリを割り当てる
	void* allocate()
	{
		while(true){
			page** ptr = &head;
			if(*ptr != NULL){
				page* next = (*ptr)->next;
				page* old_ptr = *ptr;
				if(old_ptr->next != next){continue;}
				if(__sync_bool_compare_and_swap(ptr, old_ptr, next)){
					return reinterpret_cast<void*>(old_ptr);
				}
			}

			page* newpage = get_newpage();
			if(!__sync_bool_compare_and_swap(ptr, NULL, newpage)){
				drop_page(newpage);
			}
		}
	}

	// メモリを解放する
	void free(void* ptr)
	{
		while(true){
			page* old_head = head;
			if(__sync_bool_compare_and_swap(&head, old_head, ptr)){
				break;
			}
		}
	}
	
	size_t rest() const throw()
	{
		return std::numeric_limits<size_t>::max() / sizeof(T);
	}

	int validate(){
		page* p = head;
		int cnt = 0;
		while(p != NULL){
			++cnt;
			p = p->next;
		}
		printf("page: %d  %p\n", cnt, head);
		return cnt;
	}
private:
	struct page{
		page* next;
	};
	page* head;
	
private:

	page* get_newpage(){
		void* memory = malloc(PAGESIZE);
		int address = reinterpret_cast<int>(memory);

		page* const beginpage = reinterpret_cast<page*>(
			(address + SIZE - 1) - ((address + SIZE - 1) % SIZE));
		page* const endpage = reinterpret_cast<page*>(
			(address + PAGESIZE) - ((address + PAGESIZE) % SIZE)) - SIZE;
		{
			page* oldpage = NULL;
			for(page* currpage = endpage; currpage >= beginpage; currpage = 
						reinterpret_cast<page*>(reinterpret_cast<int>(currpage) - SIZE)){
				currpage->next = oldpage;
				oldpage = currpage;
			}
		}
		return reinterpret_cast<page*>(beginpage);
	}
	void drop_page(page* const p){
		free(reinterpret_cast<void*>(p));
	}
};

#endif