BayGC/07


Top / BayGC / 07

マーク&スイープ

スタック領域、ヒープ領域等から、使われているメモリーに印をつける作業を「マーク」、印のついていないメモリーを解放することを「スイープ」ということを知りました。先ほど走査したスタックからマーク&スイープを行います。

ソースコード

List.h

可変長配列です。最初は手抜きをして STL を使う予定でしたが、new をオーバーライドしているため、new をしている個所を malloc に書き換える必要があり、STL をいじるのは大変なので、自前のクラスを用意しました。元々は Mona の HList.h と List.h を混ぜたものです。

#ifndef __LIST_H__
#define __LIST_H__

/* 可変長配列クラス */
template <class T> class List {
public:
	List();
	List(int size);
	List(int size, int increase);
	~List();

public:
	void add(T element);
	T    get(int index) const;
	T    operator[](int index);
	T    removeAt(int index);
	T    remove(T element);
	void removeAll();
	int  size() const;
	bool isEmpty() const;
	int  indexOf(T element) const;

private:
	T*  data_;        /* 初期配列     */
	int size_;        /* 配列のサイズ */
	int elements_;    /* 要素数       */
	int increase_;    /* 増加分       */

	/* 初期化 */
	void init(int size, int increase);
};

/* コンストラクタ */
template <class T> List<T>::List()
{
	init(5, 5);
	return;
}

/* コピーコンストラクタ */
template <class T> List<T>::List(int size)
{
	init(size, 5);
	return;
}

/* コピーコンストラクタ */
template <class T> List<T>::List(int size, int increase)
{
	init(size, increase);
	return;
}

/* デスクトラクタ */
template <class T> List<T>::~List()
{
	/* メモリの解放 */
	//delete[] data_;
	free(data_);
	return;
}

/* 空かどうかを返す */
template <class T> bool List<T>::isEmpty() const
{
	return elements_ == 0;
}

/* 要素を追加する */
template <class T> void List<T>::add(T element)
{
	/* 配列が一杯になった */
	if (size_ == elements_) {

		/* 配列を2倍にする */
		size_ += increase_;
		T* temp = (T *) malloc(sizeof(T) * size_); //T[size_];

		/* 最適化? */
		int numElements = elements_;

		/* オリジナルの配列を新しい配列にコピー */
		for (int i = 0; i < numElements; i++) {
			temp[i] = data_[i];
		}

		delete[] data_;
		data_ = temp;
	}

	/* 要素の追加 */
	data_[elements_] = element;
	elements_++;
	return;
}

/* i番目の要素を得る */
template <class T> T List<T>::get(int index) const
{
	/* 範囲チェック */
	if (index < 0 || index >=elements_) {
		return (T)NULL;
	}
	return data_[index];
}

/* 配列のようにアクセスする */
template <class T> T List<T>::operator[](int index)
{
	return (this->get(index));
}

/* サイズを得る */
template <class T> int List<T>::size() const
{
	return elements_;
}

/* i番目の要素を削除する */
template <class T> T List<T>::removeAt(int index)
{
	/* 範囲チェック */
	if (index < 0 || index >=elements_) {
		return (T)NULL;
	}

	/* 削除する要素をコピー */
	T toRemove = data_[index];

	/* 空きを埋める */
	int numElements = elements_;
	for (int i = index; i < numElements - 1; i++) {
		data_[i] = data_[i + 1];
	}
	elements_--;
	return toRemove;
}

template <class T> T List<T>::remove(T element)
{
	/* 最適化? */
	int size = this->size();

	for (int i = 0; i < size; i++) {
		/* 削除する要素が見つかった */
		if (data_[i] == element) {
			return (removeAt(i));
		}
	}

	return (T)NULL;
}

template <class T> void List<T>::removeAll()
{
	/* メモリの解放 */
	delete[] data_;
	init(5, 5);
}

template <class T> void List<T>::init(int size, int increase)
{
	/* 要素数 */
	elements_ = 0;

	/* サイズと増加分を設定 */
	size_     = size     > 0 ? size : 5;
	increase_ = increase > 0 ? increase : 5;

	/* 初期配列を作る */
	data_ = (T *) malloc(sizeof(T) * size_); //new T[size_];
	return;
}

template <class T> int List<T>::indexOf(T element) const
{
	/* 最適化? */
	int size = this->size();

	/* 要素を探す */
	for (int i = 0; i < size; i++) {
		/* 要素が見つかった */
		if (data_[i] == element) {
			return i;
		}
	}

	/* 見つからなかった */
	return -1;
}

#endif

15.cpp

new したアドレスのリストを ptr_list に、マークしたポインターのリストを match_list に格納しています。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "List.h"

List<void*> ptr_list;
List<void*> match_list;

char* ebp;
char* esp;

void test();
void baygc();

int main() {
	asm volatile("movl %%ebp, %0" : "=g"(ebp));
	printf("ebp = %p\n", ebp);
	test();
	return 0;
}

void* operator new(unsigned int size) {
	void* ret = malloc(size);
	printf("operator new(%d) = %p\n",
		size, ret);
	ptr_list.add(ret);
	return ret;
}

void test() {
	printf("b: ");
	int* b = new int;
	printf("c: ");
	int* c = new int;
	new int;
	new int;
	new int;
	new int;
	new int;
	new int;
	new int;
	new int;
	new int;
	baygc();
}

void baygc() {
 	asm volatile("movl %%esp, %0" : "=g"(esp));
	printf("esp = %p\n", esp);
	int d = ebp - esp;
	char* temp_list = new char[d];
	memcpy(temp_list, esp, d);
	for (int i = 0; i < d; i++) {
		for (int j = 0; j < ptr_list.size(); j++) {
			int* pp = (int *)&temp_list[i];
			if (*pp == (int) ptr_list[j]) {
				match_list.add((void*)*pp);
				printf("match esp[%d] = 0x%08x\n", i, *pp);
			}
		}
	}
	int i, j;
	for (i = 0; i < ptr_list.size(); i++) {
		for (j = 0; j < match_list.size(); j++) {
			if ((int*) ptr_list[i] == (int*)match_list[j]) {
				break;
			}
		}
		if (j == match_list.size()) {
			printf("ptr_list[%d] = %p <- delete!!\n", i, ptr_list[i]);
		}
	}
	delete [] temp_list;
}

実行

g++ 15.cpp
./a.exe
ebp = 0x22cce8
b: operator new(4) = 0x660578
c: operator new(4) = 0x660588
operator new(4) = 0x660598
operator new(4) = 0x6605a8
operator new(4) = 0x6605b8
operator new(4) = 0x6605c8
operator new(4) = 0x660140
operator new(4) = 0x660608
operator new(4) = 0x660618
operator new(4) = 0x660628
operator new(4) = 0x660638
esp = 0x22cc70
operator new(120) = 0x6606f0
match esp[0] = 0x006606f0
match esp[20] = 0x00660638
match esp[24] = 0x00660638
match esp[28] = 0x006606f0
match esp[64] = 0x00660588
match esp[68] = 0x00660578
ptr_list[2] = 0x660598 <- delete!!
ptr_list[3] = 0x6605a8 <- delete!!
ptr_list[4] = 0x6605b8 <- delete!!
ptr_list[5] = 0x6605c8 <- delete!!
ptr_list[6] = 0x660140 <- delete!!
ptr_list[7] = 0x660608 <- delete!!
ptr_list[8] = 0x660618 <- delete!!
ptr_list[9] = 0x660628 <- delete!!

MENU

now: 9

リンク


最新の20件
2018-10-07 2018-09-20 2018-09-03 2018-05-09 2017-09-29 2017-01-10 2016-12-11 2016-10-04 2016-08-14 2016-05-29 2015-12-28 2013-02-25 2013-02-21 2013-02-20 2013-02-12 2013-02-11 2013-02-10
最新の20件
2010-02-01 2010-01-31 2010-01-30 2010-01-29 2010-01-16

Counter: 2543, today: 1, yesterday: 1

リロード   新規 編集 凍結 差分 添付 複製 改名   トップ 一覧 検索 最終更新 バックアップ   ヘルプ   最終更新のRSS

Last-modified: 2008-03-28 (金) 15:47:54 (3887d);  Modified by mona
PukiWiki 1.4.6 Copyright © 2001-2005 PukiWiki Developers Team. License is GPL.
Based on "PukiWiki" 1.3 by yu-ji
Powered by PHP 5.2.17
HTML convert time to 0.086 sec.