• R/O
  • SSH
  • HTTPS

nos: 提交


Commit MetaInfo

修訂372 (tree)
時間2010-01-11 16:11:21
作者uchan_nos

Log Message

メモリマネージャの変更
固定長領域を用意するようにした。

Change Summary

差異

--- bitnos5/trunk/kernel/boot.cpp (revision 371)
+++ bitnos5/trunk/kernel/boot.cpp (revision 372)
@@ -222,7 +222,7 @@
222222 // タスクスケジューリング開始
223223 taskman->StartScheduling();
224224
225- Debug::WriteLine("mem = %d MB", physicalMemorySize >> 20);
225+ Debug::WriteLine("mem = %d MB, %d B", physicalMemorySize >> 20, physicalMemorySize);
226226
227227 /*
228228 for (int i = 0; i <= shtman->top; i++) {
--- bitnos5/trunk/kernel/memory.cpp (revision 371)
+++ bitnos5/trunk/kernel/memory.cpp (revision 372)
@@ -485,6 +485,233 @@
485485 }
486486
487487
488+#elif MEMMAN == 3
489+
490+const size_t SizeList[5] = { 32, 128, 512, 2048, 0 };
491+const int CountList[5] = { 32 * 1024, 8 * 1024, 2 * 1024, 512, 0 };
492+
493+void StaticMemoryManager::List::Init()
494+{
495+ this->begin.SetPrev(0);
496+ this->begin.LinkTo(&this->end);
497+ this->end.SetNext(0);
498+ this->count = 0;
499+}
500+
501+void StaticMemoryManager::List::Add(MemInfo *item)
502+{
503+ if (item != 0) {
504+ item->LinkTo(this->begin.GetNext());
505+ this->begin.LinkTo(item);
506+ this->count++;
507+ }
508+}
509+
510+StaticMemoryManager::MemInfo *StaticMemoryManager::List::Remove(MemInfo *item)
511+{
512+ if (item != 0 && item->GetPrev()->GetNext() == item && item->GetNext()->GetPrev() == item) {
513+ item->GetPrev()->LinkTo(item->GetNext());
514+ item->Init(0, 0);
515+ this->count--;
516+ return item;
517+ }
518+ return 0;
519+}
520+
521+StaticMemoryManager::MemInfo *StaticMemoryManager::List::RemoveFirst()
522+{
523+ return Remove(this->begin.GetNext());
524+}
525+
526+void StaticMemoryManager::List::Merge(MemInfo *item)
527+{
528+ if (item != 0) {
529+ MemInfo *prev = &this->begin;
530+ while (prev->GetNext() != &this->end && prev->GetNext() < item) {
531+ prev = prev->GetNext();
532+ }
533+ item->LinkTo(prev->GetNext());
534+ prev->LinkTo(item);
535+ this->count++;
536+
537+ item = Merge(prev, item);
538+ item = Merge(item, item->GetNext());
539+ }
540+}
541+
542+void StaticMemoryManager::List::AddRange(MemInfo *begin, MemInfo *end, int count)
543+{
544+ if (begin != 0 && end != 0) {
545+ end->LinkTo(this->begin.GetNext());
546+ this->begin.LinkTo(begin);
547+ this->count += count;
548+ }
549+}
550+
551+StaticMemoryManager::MemInfo *StaticMemoryManager::List::Merge(MemInfo *prev, MemInfo *next)
552+{
553+ // prevとnextが結合可能?
554+ if ((uintptr_t)prev + sizeof(MemInfo) + sizeof(size_t) + prev->GetSize() == (uintptr_t)next) {
555+ prev->SetSize(prev->GetSize() + sizeof(MemInfo) + sizeof(size_t) + next->GetSize());
556+ prev->LinkTo(next->GetNext());
557+ this->count--;
558+ return prev;
559+ }
560+ return next;
561+}
562+
563+
564+void StaticMemoryManager::Init(uintptr_t begin, size_t size)
565+{
566+ uintptr_t end = begin + size;
567+
568+ begin = (begin + 3) & ~3;
569+ end = end & ~3;
570+ this->begin = begin;
571+ this->end = end;
572+
573+ MemInfo *mi = (MemInfo*)begin, *next;
574+
575+ MemInfo *miBegin, *miEnd;
576+
577+ int sizeKind;
578+
579+ /*
580+ * リストの初期化
581+ */
582+ for (sizeKind = 0; sizeKind < SizeKind; sizeKind++) {
583+ freeLists[sizeKind].Init();
584+ allocLists[sizeKind].Init();
585+ }
586+
587+ /*
588+ * 固定メモリ領域
589+ */
590+ for (sizeKind = 0; sizeKind < SizeKind - 1; sizeKind++) {
591+ miBegin = mi;
592+ for (int i = 0; i < CountList[sizeKind] - 1; i++) {
593+ next = (MemInfo*)((uintptr_t)mi + SizeList[sizeKind]);
594+ mi->LinkTo(next);
595+ mi = next;
596+ }
597+ miEnd = mi;
598+ freeLists[sizeKind].AddRange(miBegin, miEnd, CountList[sizeKind]);
599+
600+ mi = (MemInfo*)((uintptr_t)mi + SizeList[sizeKind]);
601+ }
602+
603+ /*
604+ * 可変メモリ領域
605+ */
606+ mi->SetSize(end - (uintptr_t)mi - sizeof(MemInfo) - sizeof(size_t));
607+ freeLists[sizeKind].Add(mi);
608+}
609+
610+void* StaticMemoryManager::Alloc(size_t size)
611+{
612+ const size_t MemInfoSize = sizeof(MemInfo) + sizeof(size_t);
613+
614+ uintptr_t result;
615+ MemInfo *mi = 0;
616+ List *l;
617+ int sizeKind, i;
618+
619+ size = (size + 3) & ~0x00000003;
620+
621+ for (i = 0; i < SizeKind - 1; i++) {
622+ if (size <= SizeList[i] - sizeof(MemInfo)) {
623+ break;
624+ }
625+ }
626+ sizeKind = i;
627+
628+ result = 0;
629+ for (; sizeKind < SizeKind - 1; sizeKind++) {
630+ l = freeLists + sizeKind;
631+ if (l->GetCount() > 0) {
632+ // 固定長領域に空きがある
633+ mi = l->RemoveFirst();
634+ allocLists[sizeKind].Add(mi);
635+ return (void*)((uintptr_t)mi + sizeof(MemInfo));
636+ }
637+ }
638+ l = freeLists + SizeKind - 1;
639+ if (l->GetCount() > 0) {
640+ // 固定長領域に空きがないか、固定長領域には入りきらないsizeである
641+ mi = l->GetBegin()->GetNext();
642+ for (; mi != l->GetEnd(); mi = mi->GetNext()) {
643+ if (mi->GetSize() >= size) {
644+ // 十分な大きさの空き領域が見つかった(first fit)
645+
646+ // 新しくMemInfoを作るかどうか
647+ if (mi->GetSize() > size + MemInfoSize) {
648+ // 新しい領域を作る
649+ // newInfoが確保する領域
650+ MemInfo *newInfo = (MemInfo*)((uintptr_t)mi + MemInfoSize + mi->GetSize() - size - MemInfoSize);
651+ newInfo->SetSize(size);
652+ mi->SetSize(mi->GetSize() - size - MemInfoSize);
653+ mi = newInfo;
654+ } else {
655+ // 1つの空き領域すべてを転用
656+ freeLists[SizeKind - 1].Remove(mi);
657+ }
658+ allocLists[SizeKind - 1].Add(mi);
659+ return (void*)((uintptr_t)mi + sizeof(MemInfo));
660+ }
661+ }
662+ }
663+
664+ return (void*)0;
665+}
666+
667+void StaticMemoryManager::Free(void *ptr)
668+{
669+ if (this->begin <= (uintptr_t)ptr && (uintptr_t)ptr < this->end) {
670+ uintptr_t begin = this->begin;
671+ uintptr_t end;
672+ int sizeKind;
673+ MemInfo *mi;
674+
675+ for (sizeKind = 0; sizeKind < SizeKind - 1; sizeKind++) {
676+ end = begin + SizeList[sizeKind] * CountList[sizeKind];
677+ if ((uintptr_t)ptr < end) {
678+ // ptrが固定領域のポインタだった
679+ mi = (MemInfo*)((uintptr_t)ptr - sizeof(MemInfo));
680+
681+ allocLists[sizeKind].Remove(mi);
682+ freeLists[sizeKind].Add(mi);
683+ goto free_end;
684+ }
685+ begin = end;
686+ }
687+ // ptrは可変長領域のポインタだった
688+ mi = (MemInfo*)((uintptr_t)ptr - sizeof(MemInfo) - sizeof(size_t));
689+ mi = allocLists[sizeKind].Remove(mi);
690+ freeLists[sizeKind].Merge(mi);
691+ goto free_end;
692+
693+ free_end:
694+ return;
695+ }
696+
697+}
698+
699+size_t StaticMemoryManager::GetFreeSize()
700+{
701+ size_t sum = 0;
702+ int sizeKind;
703+ for (sizeKind = 0; sizeKind < SizeKind - 1; sizeKind++) {
704+ sum += (SizeList[sizeKind] - sizeof(MemInfo)) * freeLists[sizeKind].GetCount();
705+ }
706+ MemInfo *mi = freeLists[sizeKind].GetBegin()->GetNext();
707+ while (mi != freeLists[sizeKind].GetEnd()) {
708+ sum += mi->GetSize();
709+ mi = mi->GetNext();
710+ }
711+ return sum;
712+}
713+
714+
488715 #endif
489716
490717 MemoryManager memman;
--- bitnos5/trunk/include/bitnos/memory.h (revision 371)
+++ bitnos5/trunk/include/bitnos/memory.h (revision 372)
@@ -10,6 +10,7 @@
1010
1111 #include <stdint.h>
1212 #include <bitnos/uncopyable.h>
13+#include <stddef.h>
1314
1415 /*
1516 * 物理メモリの総容量を計算する
@@ -16,12 +17,12 @@
1617 */
1718 uintptr_t GetPhysicalMemoryCapacity(uintptr_t begin, uintptr_t end);
1819
19-#define MEMMAN 2
20+#define MEMMAN 3
2021
22+#if MEMMAN == 1
2123 /*
22- * メモリ使用情報を入れておく
24+ * メモリ使用情報を入れておく
2325 */
24-#if MEMMAN == 1
2526 struct MemInfo
2627 {
2728 uintptr_t addr;
@@ -139,6 +140,154 @@
139140 void Unlink(MemInfo* mi);
140141 };
141142
143+#elif MEMMAN == 3
144+
145+extern const size_t SizeList[5];
146+extern const int CountList[5];
147+
148+class StaticMemoryManager
149+{
150+ uintptr_t begin, end;
151+
152+ class MemInfo
153+ {
154+ MemInfo* prev;
155+ MemInfo* next;
156+ public:
157+ MemInfo* GetPrev()
158+ {
159+ return this->prev;
160+ }
161+ void SetPrev(MemInfo* prev)
162+ {
163+ this->prev = prev;
164+ }
165+ MemInfo* GetNext()
166+ {
167+ return this->next;
168+ }
169+ void SetNext(MemInfo* next)
170+ {
171+ this->next = next;
172+ }
173+ void LinkTo(MemInfo* mi)
174+ {
175+ this->next = mi;
176+ if (mi != 0) {
177+ mi->prev = this;
178+ }
179+ }
180+ void Init(MemInfo* prev, MemInfo* next)
181+ {
182+ this->prev = prev;
183+ this->next = next;
184+ }
185+
186+ uintptr_t GetEndAddress()
187+ {
188+ return (uintptr_t)this + sizeof(MemInfo);
189+ }
190+ size_t GetSize()
191+ {
192+ return ((size_t*)GetEndAddress())[0];
193+ }
194+ void SetSize(size_t size)
195+ {
196+ ((size_t*)GetEndAddress())[0] = size;
197+ }
198+ };
199+
200+ class List
201+ {
202+ MemInfo begin;
203+ MemInfo end;
204+ int count;
205+ public:
206+
207+ void Init();
208+
209+ /*
210+ * itemをリストの先頭に加える。
211+ */
212+ void Add(MemInfo *item);
213+
214+ /*
215+ * itemをリストから削除する。
216+ */
217+ MemInfo *Remove(MemInfo *item);
218+
219+ /*
220+ * 先頭の要素をリストから削除する。
221+ */
222+ MemInfo *RemoveFirst();
223+
224+ /*
225+ * itemをアドレス順になるようにリストに加え、
226+ * 前後と結合できるならする。
227+ */
228+ void Merge(MemInfo *item);
229+
230+ /*
231+ * リストをリストの先頭に加える。
232+ */
233+ void AddRange(MemInfo *begin, MemInfo *end, int count);
234+
235+ /*
236+ * リストの要素数を返す。
237+ */
238+ int GetCount()
239+ {
240+ return this->count;
241+ }
242+
243+ MemInfo *GetBegin()
244+ {
245+ return &this->begin;
246+ }
247+
248+ MemInfo *GetEnd()
249+ {
250+ return &this->end;
251+ }
252+
253+ private:
254+ /*
255+ * prevとnextが結合できるならする。
256+ * 結合したならprevを、結合していないならnextを返す。
257+ */
258+ MemInfo* Merge(MemInfo *prev, MemInfo *next);
259+ };
260+
261+ static const int SizeKind = sizeof(SizeList) / sizeof(SizeList[0]);
262+
263+ List allocLists[SizeKind];
264+ List freeLists[SizeKind];
265+
266+public:
267+ /*
268+ * 管理する領域の情報を与える。
269+ */
270+ void Init(uintptr_t begin, size_t size);
271+
272+ /*
273+ * 指定されたサイズ以上の領域を確保して返す。
274+ */
275+ void* Alloc(size_t size);
276+
277+ /*
278+ * 指定された領域を解放する。
279+ */
280+ void Free(void *ptr);
281+
282+ /*
283+ * 空き領域を計算する
284+ */
285+ size_t GetFreeSize();
286+
287+};
288+
289+typedef StaticMemoryManager MemoryManager;
290+
142291 #endif
143292
144293 extern MemoryManager memman;
Show on old repository browser