BayGC/08 の変更点



 #topicpath
 #contents
 
 * リファクタリング [#z971e699]
 
 先ほどのコードは、無駄が多いので、リファクタリングしてコードを整理します。
 
 ** ソースコード [#a270ad03]
 
 *** List.h [#x75ed637]
 
 コピーコンストラクタを削ったり、残っていた delete を free にしたりしました。
 
  #ifndef __LIST_H__
  #define __LIST_H__
  
  /* 可変長配列クラス */
  template <class T> class List
  {
  public:
      List();
      ~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()
  {
      /* メモリの解放 */
      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_];
  
          /* オリジナルの配列を新しい配列にコピー */
          for (int i = 0; i < elements_; i++)
          {
              temp[i] = data_[i];
          }
  
          free(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];
  
      /* 空きを埋める */
      for (int i = index; i < elements_ - 1; i++)
      {
          data_[i] = data_[i + 1];
      }
      elements_--;
  
      return toRemove;
  }
  
  template <class T> T List<T>::remove(T element)
  {
      for (int i = 0; i < size_; i++)
      {
          /* 削除する要素が見つかった */
          if (data_[i] == element)
          {
              return (removeAt(i));
          }
      }
  
      return (T)NULL;
  }
  
  template <class T> void List<T>::removeAll()
  {
      /* メモリの解放 */
      free(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
  {
      /* 要素を探す */
      for (int i = 0; i < size_; i++)
      {
          /* 要素が見つかった */
          if (data_[i] == element)
          {
              return i;
          }
      }
  
      /* 見つからなかった */
      return -1;
  }
  
  #endif
 
 *** データ構造 [#zcd5a8bf]
 
 マークしたかどうかのフラグと、取得したアドレスをセットで格納するための構造体を用意しました。
 
  typedef struct
  {
      bool  marked;
      void* address;
  }
  ListEntry;
 
 *** 17.cpp [#aff08934]
 
  #include <stdio.h>
  #include <stdlib.h>
  #include "List.h"
  
  char* ebp;
  char* esp;
  int gc_count;
  
  typedef struct
  {
      bool  marked;
      void* address;
  }
  ListEntry;
  
  List<ListEntry*>* entry_list;
  
  void gc_mark()
  {
      asm volatile("movl %%esp, %0" : "=g"(esp));
      int start = (int) esp;
      int end   = (int) ebp;
      printf("\t==== marking start !!!! ====\n");
      printf("\t\tesp = 0x%08x\n", (int*) start);
      printf("\t\tebp = 0x%08x\n", (int*) end);
      for (int i = 0; i < end - start; i++)
      {
          int p = *((int *) &esp[i]);
          int J = entry_list->size();
          for (int j = 0; j < J; j++)
          {
              ListEntry* entry = entry_list->get(j);
              if (entry->marked == false && p == (int) entry->address)
              {
                  printf("\t\tmarked 0x%08x = 0x%08x\n", &esp[i], p);
                  entry->marked = true;
              }
          }
      }
      printf("\t==== marking end !!!! ====\n");
  }
  
  void gc_sweep()
  {
      printf("\t==== sweeping start !!!! ====\n");
      for (int j = 0; j < entry_list->size(); j++)
      {
          ListEntry* entry = entry_list->get(j);
          if (entry->marked == false)
          {
              printf("\t\tsweeped 0x%08x\n", (int) entry->address);
              entry_list->removeAt(j);
              delete (int *) entry->address;
              free(entry);
              j--;
          }
      }
      printf("\t==== sweeping end !!!! ====\n");
  }
  
  void gc()
  {
      gc_count = 0;
      gc_mark();
      gc_sweep();
  }
  
  void gc_init()
  {
      asm volatile("movl %%ebp, %0" : "=g"(ebp));
      gc_count = 0;
      entry_list = (List<ListEntry*>*) malloc(sizeof(List<ListEntry*>));
  }
  
  void* operator new(unsigned int size)
  {
      if (++gc_count % 4 == 0) gc();
      void* ret = malloc(size);
      printf("operator new(%d) = %p\n", size, ret);
      ListEntry* entry = (ListEntry *) malloc(sizeof(ListEntry));
      entry->marked  = false;
      entry->address = ret;
      entry_list->add(entry);
      return ret;
  }
  
  void test1()
  {
      int* a = new int;
      int* b = new int;
      int* c = new int;
      int* d = new int;
      int* e = new int;
      new int;
      new int;
      new int;
      new int;
      new int;
      new int;
      new int;
      new int;
  }
  
  void test2()
  {
      new int;
  }
  
  int main()
  {
      gc_init();
      test1();
      test2();
      gc();
      return 0;
  }
 
 *** void gc_init() [#t08969da]
 
 - GC の初期化を行います
 - ebp を取得します
 - gc のカウンターをゼロにします
 
 ***  void* operator new(unsigned int size) [#yd0f142e]
 
 - gc_count が 4 で割り切れるときだけ、GC を行います
 -- 毎回やると時間がかかるため、このようにしてみました
 - new したアドレスを entry に詰めて、entry を entry_list に追加します
 
 *** void gc() [#w91db4af]
 
 - gc のカウンターをゼロにします
 - マークします
 - スイープします
 
 ** 実行 [#t7678a10]
 
  g++ 17.cpp
  ./a.exe
 
  operator new(4) = 0x660158
  operator new(4) = 0x660590
  operator new(4) = 0x6605b0
          ==== marking start !!!! ====
                  esp = 0x0022cc50
                  ebp = 0x0022ccc8
                  marked 0x0022cc98 = 0x006605b0
                  marked 0x0022ccc0 = 0x00660590
                  marked 0x0022ccc4 = 0x00660158
          ==== marking end !!!! ====
          ==== sweeping start !!!! ====
          ==== sweeping end !!!! ====
  operator new(4) = 0x6605d0
  operator new(4) = 0x6605f0
  operator new(4) = 0x660610
  operator new(4) = 0x660630
          ==== marking start !!!! ====
                  esp = 0x0022cc50
                  ebp = 0x0022ccc8
                  marked 0x0022cc98 = 0x00660630
                  marked 0x0022ccb4 = 0x006605f0
                  marked 0x0022ccb8 = 0x006605d0
          ==== marking end !!!! ====
          ==== sweeping start !!!! ====
                  sweeped 0x00660610
          ==== sweeping end !!!! ====
  operator new(4) = 0x660610
  operator new(4) = 0x660650
  operator new(4) = 0x660670
  operator new(4) = 0x660690
          ==== marking start !!!! ====
                  esp = 0x0022cc50
                  ebp = 0x0022ccc8
                  marked 0x0022cc98 = 0x00660690
          ==== marking end !!!! ====
          ==== sweeping start !!!! ====
                  sweeped 0x00660610
                  sweeped 0x00660650
                  sweeped 0x00660670
          ==== sweeping end !!!! ====
  operator new(4) = 0x660610
  operator new(4) = 0x660650
  operator new(4) = 0x660670
          ==== marking start !!!! ====
                  esp = 0x0022cc90
                  ebp = 0x0022ccc8
          ==== marking end !!!! ====
          ==== sweeping start !!!! ====
                  sweeped 0x00660610
                  sweeped 0x00660650
                  sweeped 0x00660670
          ==== sweeping end !!!! ====
 
 無事、スイープされて、メモリが解放されているようです。

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

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.218 sec.