x86(i386)向けのOS作成日記 - メモリマネージャ2

2017.11.19

今日はメモリマネージャを実装したい。（上記1,2,3の調査はやりたいけど資料を持ってくるのを忘れた...） 最初は本の通りに実装するけど、やっぱり線形リストに実装し直したい。

リストの除外操作が含まれるので、やっぱり双方向リストにする。

2017.11.21

メモリ操作のデバッグが辛すぎるので、開発効率を上げるためにも簡易テストモジュールを作った。 github.com

2017.11.23

勤労感謝の日。 簡易テストモジュール自体を修正しながらメモリ管理のテスト。双方向リストで書き直してみた。 結果汚くなってしまった感触が…。また、テーブルサイズも増えた…。

/* メモリ空き情報（双方向リスト） */
struct MemoryFreeInfo {
  struct MemoryFreeInfo *next; /* 次の情報 */
  struct MemoryFreeInfo *prev; /* 前の情報 */
  uintptr_t address;           /* 空きの開始アドレス */
  uintptr_t size;              /* 空きサイズ        */
};

/* メモリ管理構造体 */
struct MemoryManager {
  uint32_t flags;                  /* 各種状態フラグ */
  uint32_t num_free;               /* 空き情報個数 */
  uint32_t max_num_free;           /* 現在までの最大空き情報数 */
  uint32_t lostsize;               /* メモリ管理から外れたサイズ */
  uint32_t num_losts;              /* メモリ管理から外れた空き情報数 */
  struct MemoryFreeInfo *free_top; /* 空き情報リスト先頭 */
  struct MemoryFreeInfo free_info[MEMORY_MANAGER_MAX_NUM_FREEINFO];
                               /* 空き情報のメモリ領域 */
};

/* 常識的に考えてメモリ管理構造体は一つしかないはず */
/* スタティック変数で割りあてる */
static struct MemoryManager st_memory_manager;

確保ルーチン。配列をリストに置き換えた位でさしたる変化なし。

/* メモリ確保 */
void* MemoryManager_Alloc(uintptr_t size)
{
  uintptr_t addr;
  struct MemoryFreeInfo *p_free;

  /* 初期化前ならばNULLを返す */
  if (!(st_memory_manager.flags & MEMORY_MANAGER_FLAGS_INITIALIZED)) {
    return NULL;
  }

  /* サイズ0を要求してもNULL */
  if (size == 0) {
    return NULL;
  }

  /* 最初に見つけた空き領域に割り当てる
   * これはアルゴリズムを考察しても良いかも */
  for (p_free = st_memory_manager.free_top;
       p_free != NULL;
       p_free = p_free->next) {
    if (p_free->size >= size) {
      /* 十分な大きさの空きを発見 */
      addr = p_free->address;
      /* 空き情報を更新 */
      p_free->address += size;
      p_free->size    -= size;
      /* サイズがなくなったのでリストを前に詰める */
      if (p_free->size == 0) {
        st_memory_manager.num_free--;
        /* リストから要素を除外 */
        if (p_free == st_memory_manager.free_top) {
          st_memory_manager.free_top = p_free->next;
      if (st_memory_manager.free_top != NULL) {
        st_memory_manager.free_top->prev = NULL;
      }
        } else {
          p_free->prev->next = p_free->next;
      if (p_free->next != NULL) {
        p_free->next->prev = p_free->prev;
      }
        }
        /* 空き情報を無効化 */
        p_free->next    = NULL;
    p_free->prev    = NULL;
        p_free->address = 0;
      }
      return (void*)addr;
    }
  }

  return NULL;

}

領域解放ルーチン。条件判定はもしかしたら冗長かも。

/* 領域の解放 */
int32_t MemoryManager_Free(uintptr_t address, uintptr_t size)
{
  struct MemoryManager  *memman = &st_memory_manager;
  struct MemoryFreeInfo *p_free, *p_insert;
  
  /* 初期化前ならば失敗 */
  if (!(memman->flags & MEMORY_MANAGER_FLAGS_INITIALIZED)) {
    return -1;
  }
  
  /* サイズ0の登録は許容しない */
  if (size == 0) {
    return -2;
  }

  /* 初回時は、リストを生成して終了 */
  if (memman->free_top == NULL) {
      p_free           = &memman->free_info[0];
    p_free->address  = address;
    p_free->size     = size;
    p_free->next     = NULL;
    p_free->prev     = NULL;
    memman->free_top = p_free;
    memman->num_free++;
    return 0;
  }

  /* アドレス順に整列させるため、挿入位置を探索 */
  for (p_insert = memman->free_top;
       p_insert->next != NULL; 
       p_insert = p_insert->next) {
    if (p_insert->address > address) {
      break;
    }
  }

  /* リストに1つの要素しかない時の判定 */
  if (p_insert->prev == NULL && p_insert->next == NULL) {
    if (p_insert->address + p_insert->size == address) {
          p_insert->size += p_insert->size;
      return 0;
    } else if (address + size == p_insert->address) {
      p_insert->address = address;
      p_insert->size    += size;
      return 0;
    }
  }

  /* p_insert->prev->address < address < p_insert->address */

  /* 前の空き領域と纏められるかチェック */
    if (p_insert->prev != NULL
      && p_insert->prev->address + p_insert->prev->size == address) {
      /* 前の空き領域と纏められる */      
      p_insert->prev->size += size;
        if (address + size == p_insert->address) {
          /* 後ろも纏められる */
          p_insert->prev->size += p_insert->size;
          /* p_insertの要素を削除 */
      p_insert->address    = 0;
      p_insert->size       = 0;
          memman->num_free--;
      if (p_insert->prev != NULL) {
        p_insert->prev->next = p_insert->next;
      }
      if (p_insert->next != NULL) {
        p_insert->next->prev = p_insert->prev;
      }
      p_insert->prev       = NULL;
      p_insert->next       = NULL;
        }
      /* 成功終了 */
      return 0;
    }

  /* 後ろの空き領域と纏められるかチェック */
    if (address + size == p_insert->address) {
      /* 後ろと纏められる */
      p_insert->address = address;
      p_insert->size   += size;
      return 0;
    }

  /* 前にも後ろにも纏められない */
  if (memman->num_free < MEMORY_MANAGER_MAX_NUM_FREEINFO) {
    uint32_t i_free;
    
    /* 新しい単独の空き情報要素を探索 */
    for (i_free = 0; i_free < MEMORY_MANAGER_MAX_NUM_FREEINFO; i_free++) {
      p_free = &st_memory_manager.free_info[i_free];
      if (p_free->prev == NULL 
        && p_free->next == NULL
        && p_free->address == 0
        && p_free->size == 0) {
      break;
      }
    }

    /* 末尾まで達してしまった -> 失敗 */
    if (i_free == MEMORY_MANAGER_MAX_NUM_FREEINFO-1) {
      return -2;
    }

    /* 新しい単独の空き情報を作成 */
    p_free->address = address;
    p_free->size    = size;

    /* リストに追加 */
  p_free->next   = p_insert->next;
  p_insert->next = p_free;
  p_free->prev   = p_insert;

    /* 空き情報の最大数を更新 */
    memman->num_free++;
    if (memman->max_num_free < memman->num_free) {
      memman->max_num_free = memman->num_free;
    }

  return 0;
  }

  /* 後ろにずらせなかった -> 失敗 */
  memman->num_losts++;
  memman->lostsize += size;
  return -4;
  
}