From 6d4fd203724acffc9d3fc443edc5064d3360e6c4 Mon Sep 17 00:00:00 2001
From: AceVest <zhaoyanbai@126.com>
Date: Sat, 5 Apr 2014 14:28:39 +0800
Subject: [PATCH] add support to init the buddy system

---
 README          |  10 -----
 include/page.h  |  30 ++++++++++++-
 mm/buddy.c      | 110 +++++++++++++++++++++++++++++++++++++++++++-----
 scripts/link.ld |   2 +-
 4 files changed, 129 insertions(+), 23 deletions(-)
 delete mode 100644 README

diff --git a/README b/README
deleted file mode 100644
index 19ba022..0000000
--- a/README
+++ /dev/null
@@ -1,10 +0,0 @@
-kernel
-======
-
-I can't find a satisfactory name for my kernel.
-
-### HOW TO GET THE LATEST SOURCECODE?
-    git clone https://github.com/acevest/kernel
-### WHEN DID YOU START TO DO THIS WORK?
-    Maybe 2006.12
-### HOW TO COMPILE THIS KERNEL?
diff --git a/include/page.h b/include/page.h
index d1cdc2d..07cfda2 100644
--- a/include/page.h
+++ b/include/page.h
@@ -30,6 +30,7 @@
 
 #ifndef    ASM
 #include <types.h>
+#include <bits.h>
 #define get_npd(vaddr)    (((u32)(vaddr))>>22)
 #define get_npt(vaddr)    ((((u32)(vaddr))>>12) & 0x3FF)
 
@@ -65,14 +66,41 @@ typedef unsigned long pte_t;
 
 #define MAX_OLD_ORDER    (11)
 
+enum page_flags {
+    PG_Private,
+};
+
+
 typedef struct page
 {
+    unsigned long flags;
+    unsigned long private;
     unsigned long index;
+    list_head_t   lru;
 } page_t;
 
+#define __GETPAGEFLAG(name)                                         \
+    static inline int Page##name(page_t *page)                      \
+            {return constant_test_bit(PG_##name, &page->flags); }
+
+#define __SETPAGEFLAG(name)                                         \
+    static inline int SetPage##name(page_t *page)                   \
+            {return test_and_set_bit(PG_##name, &page->flags); }
+
+#define __CLEARPAGEFLAG(name)                                       \
+    static inline int ClearPage##name(page_t *page)                 \
+            {return test_and_clear_bit(PG_##name, &page->flags); }
+
+
+__GETPAGEFLAG(Private)
+__SETPAGEFLAG(Private)
+__CLEARPAGEFLAG(Private)
+
+
 typedef struct free_area
 {
-    unsigned long count;
+    unsigned long free_count;
+    list_head_t   free_list;
 } free_area_t;
 
 // TODO Remove
diff --git a/mm/buddy.c b/mm/buddy.c
index eab076c..7253252 100644
--- a/mm/buddy.c
+++ b/mm/buddy.c
@@ -8,42 +8,130 @@
  */
 #include <mm.h>
 
-#define MAX_ORDER       4
+#define MAX_ORDER       10
 struct buddy_system
 {
-    page_t      **page_map;
+    page_t      *page_map;
     free_area_t free_area[MAX_ORDER + 1];
 };
 
 struct buddy_system buddy_system;
 
+int buddy_is_free(page_t *page, unsigned int order)
+{
+    if(PagePrivate(page) && page->private == order)
+        return 1;
+
+    return 0;
+}
+
+void __free_pages(page_t *page, unsigned int order)
+{
+    if(order > MAX_ORDER)
+        return ;
+
+    page_t *buddy = 0;
+    page_t *base  = buddy_system.page_map;
+    unsigned long page_inx  = page - base;
+    while(order < MAX_ORDER)
+    {
+        unsigned long buddy_inx = page_inx ^ (1UL << order);
+        buddy = base + buddy_inx;
+        if(!buddy_is_free(buddy, order)) {
+            break;
+        }
+
+        list_del(&buddy->lru);
+        buddy_system.free_area[order].free_count--;
+
+        ClearPagePrivate(buddy);
+        buddy->private = 0;
+
+        page_inx &= buddy_inx;
+
+        order++;
+    }
+
+    page_t *p  = base + page_inx;
+    p->private = order;
+    p->index   = page_inx;
+    SetPagePrivate(p);
+    list_add(&(p->lru), &(buddy_system.free_area[order].free_list));
+    buddy_system.free_area[order].free_count++;
+}
+
+void dump_buddy_system()
+{
+    unsigned long i;
+    for(i=0; i<MAX_ORDER+1; ++i)
+    {
+        printk("order %2d free_count %d ", i, buddy_system.free_area[i].free_count);
+
+        if(buddy_system.free_area[i].free_count < 100)
+        {
+            list_head_t *p;
+            page_t *page;
+            printk("pfn:");
+            list_for_each(p, &buddy_system.free_area[i].free_list)
+            {
+                page = list_entry(p, page_t, lru);
+                printk(" %d", page->index);
+            }
+        }
+
+        printk("\n");
+    }
+
+}
+
 void init_buddy_system()
 {
+    page_t *page;
+    unsigned long i;
     unsigned long pfn_cnt = bootmem_total_pages();
 
-    buddy_system.page_map = alloc_bootmem(pfn_cnt*sizeof(page_t*), sizeof(page_t*));
+    // init free area
+    memset(&buddy_system, 0, sizeof(buddy_system));
+
+    for(i=0; i<MAX_ORDER+1; ++i)
+    {
+        INIT_LIST_HEAD(&(buddy_system.free_area[i].free_list));
+    }
+
+
+    // init page map
+    unsigned long page_map_size = pfn_cnt*sizeof(page_t);
+    buddy_system.page_map = alloc_bootmem(page_map_size, PAGE_SIZE);
     if(0 == buddy_system.page_map) {
         printk("can not go on playing...\n");
         while(1);
     }
 
-    unsigned long i;
+    printk("page_map begin %08x end %08x\n", buddy_system.page_map, buddy_system.page_map + pfn_cnt);
+
     for(i=0; i<pfn_cnt; ++i)
     {
-        buddy_system.page_map[i] = alloc_bootmem(sizeof(page_t), sizeof(unsigned long));
-        if(0 == buddy_system.page_map[i]) {
-            printk("can not go on playing...\n");
-            while(1);
-        }
+        page = buddy_system.page_map + i;
+        page->private = 0;
+        page->index   = i;
+        INIT_LIST_HEAD(&(page->lru));
+        ClearPagePrivate(page);
     }
 
+    // get free pages from bootmem
     for(i=0; i<pfn_cnt; ++i)
     {
+        page = buddy_system.page_map + i;
+
         if(BOOTMEM_PAGE_FREE == bootmem_page_state(i))
         {
             // free to buddy system
+            __free_pages(page, 0);
         }
-        
-        buddy_system.page_map[i]->index = i;
     }
+
+    // free bootmem bitmap pages to buddy system
+    // ...
+
+    dump_buddy_system();
 }
diff --git a/scripts/link.ld b/scripts/link.ld
index 0de77af..5a47fb6 100644
--- a/scripts/link.ld
+++ b/scripts/link.ld
@@ -56,5 +56,5 @@ SECTIONS
 
     end = .;
     _end = .;
-    kernel_end = (end + 0x1000 - 1) & ~ (0x1000 -1);
+    kernel_end = ALIGN(0x1000);
 }
-- 
2.44.0