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; }