From cf7cd8be60c254b44b444c97dcb238d7cf3afd4c Mon Sep 17 00:00:00 2001 From: Brett Weiland Date: Tue, 21 Sep 2021 10:50:33 -0500 Subject: palloc smp safe (testing required, NOT pfree) --- src/debug/gdbinit.gdb | 3 + src/include/libc.h | 6 +- src/include/paging.h | 1 + src/include/random.h | 1 + src/include/smp.h | 23 ++- src/include/smp_racetest.h | 6 + src/include/smp_sync.h | 23 --- src/include/testmalloc.h | 6 - src/indigo_os | Bin 43424 -> 45152 bytes src/kernel/heap.c | 6 +- src/kernel/kernel.c | 23 ++- src/kernel/libc.c | 8 + src/kernel/page.c | 97 +++++++-- src/kernel/random.c | 7 +- src/kernel/smp.c | 30 ++- src/kernel/smp_racetest.c | 52 +++++ src/kernel/smp_trampoline.asm | 1 + src/kernel/testmalloc.c | 35 ---- src/makefile | 4 +- src/page_backup.c | 465 ++++++++++++++++++++++++++++++++++++++++++ 20 files changed, 702 insertions(+), 95 deletions(-) create mode 100644 src/include/smp_racetest.h delete mode 100644 src/include/smp_sync.h delete mode 100644 src/include/testmalloc.h create mode 100644 src/kernel/smp_racetest.c delete mode 100644 src/kernel/testmalloc.c create mode 100644 src/page_backup.c diff --git a/src/debug/gdbinit.gdb b/src/debug/gdbinit.gdb index a658ba4..516deba 100644 --- a/src/debug/gdbinit.gdb +++ b/src/debug/gdbinit.gdb @@ -1,6 +1,9 @@ target remote localhost:1234 symbol-file debug/debug_syms.o +set scheduler-locking step + +hb page.c:357 define cs2bs print (1 << (5 + $arg0)) diff --git a/src/include/libc.h b/src/include/libc.h index d0789cf..030f05f 100644 --- a/src/include/libc.h +++ b/src/include/libc.h @@ -2,10 +2,12 @@ #define _STRING_H_ #include #include +#include void *strcpy(char *dest, char *src); -void *memcpy(void *dest, void *src, size_t n); //TODO -void *bzero(const void *dest, size_t size); +void *memcpy(void *dest, void *src, size_t n); +void *bzero(void *dest, size_t size); +bool *is_empty(void *dest, size_t size); void *memset(void *s, char c, size_t n); size_t strlen(const char *s); int strcmp(const char *str1, const char *str2); diff --git a/src/include/paging.h b/src/include/paging.h index 5d33ca5..b1f8e9a 100644 --- a/src/include/paging.h +++ b/src/include/paging.h @@ -10,6 +10,7 @@ void unmap_lowmem(); size_t map_complete_physical(); void debug_pzone(); +void init_pmap_smp(); struct phys_map *init_pmap(size_t pagetable_size); diff --git a/src/include/random.h b/src/include/random.h index 6f35278..95b7147 100644 --- a/src/include/random.h +++ b/src/include/random.h @@ -1,5 +1,6 @@ #ifndef random_header #define random_header void randinit(); +void sync_malloc(); unsigned int randint(); #endif diff --git a/src/include/smp.h b/src/include/smp.h index f4e3aa8..e331036 100644 --- a/src/include/smp.h +++ b/src/include/smp.h @@ -1,7 +1,10 @@ #ifndef SMP_INCLUDED #define SMP_INCLUDED #include -void smp_boot(); +#include +#include +#include +void smp_prepare(); extern uint8_t corecount; static inline void lock(uint8_t *lock) { @@ -18,9 +21,25 @@ static inline void unlock(uint8_t *lock) { asm("lock andb [%0], 0"::"r"(lock)); } -static inline void waitup(uint8_t *loto) { +static inline bool get_set_mutex(uint16_t *mutex) { + bool ret; + asm("lock bts %1, 0\n" + "jc .mutex_taken\n" + "mov %0, 0\n" + "jmp .done\n" + ".mutex_taken:\n" + "mov %0, 1\n" + ".done:\n" + :"=r"(ret) + :"m"(*mutex)); + return ret; } + + +//THIS IS ONLY UNTIL WE GET MULTITHREADING SET UP +uint8_t get_coreid(); + #define CREATE_LOTO(name) #endif diff --git a/src/include/smp_racetest.h b/src/include/smp_racetest.h new file mode 100644 index 0000000..25ab7f3 --- /dev/null +++ b/src/include/smp_racetest.h @@ -0,0 +1,6 @@ +#ifndef testmalloc_header +#define testmalloc_header + +void test_malloc(unsigned int cnt); + +#endif diff --git a/src/include/smp_sync.h b/src/include/smp_sync.h deleted file mode 100644 index 93aac35..0000000 --- a/src/include/smp_sync.h +++ /dev/null @@ -1,23 +0,0 @@ -#ifndef SMP_SYNC_INCLUDED -#define SMP_SYNC_INCLUDED - -static inline void lock(uint8_t *lock) { - asm("mov al, 1\n" - "spinlock:\n" - "lock xchgb [%0], al\n" - "test al, al\n" - "pause\n" - "jnz spinlock\n" - ::"r"(lock):"al"); -} - -static inline void unlock(uint8_t *lock) { - asm("lock andb [%0], 0"::"r"(lock)); -} - -static inline void waitup(uint8_t *loto) { -} - -#define CREATE_LOTO(name) - -#endif diff --git a/src/include/testmalloc.h b/src/include/testmalloc.h deleted file mode 100644 index 25ab7f3..0000000 --- a/src/include/testmalloc.h +++ /dev/null @@ -1,6 +0,0 @@ -#ifndef testmalloc_header -#define testmalloc_header - -void test_malloc(unsigned int cnt); - -#endif diff --git a/src/indigo_os b/src/indigo_os index 9a92fc5..821f97a 100755 Binary files a/src/indigo_os and b/src/indigo_os differ diff --git a/src/kernel/heap.c b/src/kernel/heap.c index db6392f..e2dcbc7 100644 --- a/src/kernel/heap.c +++ b/src/kernel/heap.c @@ -26,10 +26,11 @@ typedef struct __attribute__((packed)) heap_chunk { - unsigned int free:1; unsigned int size:4; //will use with flags later if needed unsigned int lsize:4; - unsigned long reserved:55; + unsigned int free:1; + unsigned int mutex:1; + unsigned long reserved:54; struct heap_chunk *fd; struct heap_chunk *bk; } chunk; @@ -203,6 +204,7 @@ void *malloc(size_t size) { return (void *)on_chunk + sizeof(chunk); } + void *realloc(void *old_chunk, size_t size) { void *new_chunk = malloc(size); memcpy(new_chunk, old_chunk, CHUNK_SIZE_FROM_INDEX(((chunk *)(old_chunk-24))->size)); diff --git a/src/kernel/kernel.c b/src/kernel/kernel.c index ab60f18..0aa394e 100644 --- a/src/kernel/kernel.c +++ b/src/kernel/kernel.c @@ -18,15 +18,24 @@ #include //testing headers -//#include +#include void kmain() { + printf("Kernal started on core %i\n", get_coreid()); + sync_malloc(); PANIC(KERNEL_PANIC_KERNEL_RETURNED); } +static bool smp_unlocked = false; void smp_kinit() { - printf("Kernal started on core <<<<< \n"); + + asm(".wait_for_release:\n" + "mov al, [%0]\n" + "test al, al\n" + "jz .wait_for_release\n" + ::"m"(smp_unlocked)); + smp_load_idt(); kmain(); } @@ -39,7 +48,8 @@ void kernel_init() { pmap_size = map_complete_physical(); init_klog(); init_pmap(pmap_size); - printf("\nKernal started on CPU 1!\n"); + printf("\nKernal started on core 1!\n"); + //test_malloc(100); find_root_sdp(); @@ -52,7 +62,12 @@ void kernel_init() { clear_screen(); debug_pzone(); - smp_boot(); + smp_prepare(); + + //the rest of this needs to get done before the cores start executing + init_pmap_smp(); + smp_unlocked = true; + fix_stack(); unmap_lowmem(); kmain(); diff --git a/src/kernel/libc.c b/src/kernel/libc.c index 4278281..f46c59f 100644 --- a/src/kernel/libc.c +++ b/src/kernel/libc.c @@ -1,5 +1,6 @@ #include #include +#include // TODO clean up variable names int strncmp(const char *s1, const char *s2, unsigned int n) { int i; @@ -18,6 +19,13 @@ size_t strlen(const char *s) { return(len); } +bool is_empty(const char *s, size_t size) { + for(size_t i = 0; i < size; i++) { + if(s[i]) return false; + } + return true; +} + int strcmp(const char *s1, const char *s2) { int i; for(i = 0; ((s1[i] != '\0') && (s2[i] != '\0')); i++) { diff --git a/src/kernel/page.c b/src/kernel/page.c index dea3941..0b286a4 100644 --- a/src/kernel/page.c +++ b/src/kernel/page.c @@ -7,11 +7,15 @@ #include #include #include +#include + +#include //just using char because c is a lil bitch and won't let us use void extern char _kernel_shared_zone_begin; - +//expects core_id +#define waitlist_i(y) (((core_id) * sizeof(uintptr_t)) + (y)) // PAGE MAPPING #define PAGEMAP_LOCATION 0x10000 @@ -22,12 +26,21 @@ extern char _kernel_shared_zone_begin; typedef struct phys_map { struct phys_map *next; unsigned int max_buddy; + + //has to be a 16 bit variable + uint16_t mutex; //we might improve the speed of this later + uint64_t bsize[MAX_BUDDY_ORDER]; uint64_t *buddy[MAX_BUDDY_ORDER]; } pmap_t; static pmap_t *first_pmap; +//I'd like to find out a way to get rid of this... we only use it once +static unsigned int pmap_count = 0; + +static pmap_t **waiting_pmaps; + #define MEM_AVAILABLE 1 #define MEM_RESERVED 2 #define MEM_APCI_RECLAIMABLE 3 @@ -161,10 +174,10 @@ void debug_pmap() { //TODO I know you don't want to, but you need to thoroughly check this. void pfree(void *addr, size_t size) { int blevel = 0; - uint64_t *onbyte; //the byte out buddy resides on in the current level - uint64_t page_bitloc; // how many bits we are away from buddy[0]. Helps calculate bitshifts - int bbitlen; //length of free'd area in current level - int lshift; //lshift is how many bits we shift over, rightbit is what it sounds like dumbass + uint64_t *onbyte; + uint64_t page_bitloc; + int bbitlen; + int lshift; pmap_t *pmap = first_pmap; /* note: there's no security check to see if the page is actually allocated, @@ -176,7 +189,7 @@ void pfree(void *addr, size_t size) { if(((uintptr_t)addr & 4095) || (size & 4095)) { PANIC(KERNEL_PANIC_INVALID_PFREE); - return; //TODO [minor] some more specificity, not a huge deal + return; } size /= 0x1000; for(; pmap != 0; pmap = pmap->next) { @@ -221,7 +234,7 @@ void pfree(void *addr, size_t size) { if(bbitlen <= 1) { *onbyte |= ((uint64_t)1 << lshift); break; - } else if(bbitlen & 1) { //check me + } else if(bbitlen & 1) { size -= (1 << blevel); *onbyte |= ((uint64_t)1 << (bbitlen + lshift)); } @@ -232,12 +245,16 @@ void pfree(void *addr, size_t size) { void *palloc(size_t size) { + uint8_t core_id = get_coreid(); bool self_alloc; int min_blevel, blevel; - uint64_t bbit, unshifted_entry, threshold, bloc; //TODO move when you've confirmed casting stuff + uint64_t bbit, unshifted_entry, threshold, bloc; uint64_t buddy_i, *ret, *bentry; int itercount; + bool unlocked_pmaps_searched = false; pmap_t *pmap = first_pmap; + unsigned int waitingp_i = 0; + unsigned int searchingp_i; if(size == 0) return 0; @@ -263,7 +280,19 @@ void *palloc(size_t size) { } for(blevel = min_blevel; blevel < MAX_BUDDY_ORDER; blevel++) { - for(pmap = first_pmap; pmap != 0; pmap = pmap->next) { + //for(pmap = first_pmap; pmap != 0; pmap = pmap->next) { + //while(!unlocked_pmaps_searched || + // is_empty(waiting_pmaps[core_id], sizeof(&pmap) * pmap_count)) { + pmap = first_pmap; + while(pmap) { + + if(get_set_mutex(&pmap->mutex)) { + if(!unlocked_pmaps_searched) waiting_pmaps[waitlist_i(waitingp_i++)] = pmap; + goto get_next_pmap; + } + + + if(unlocked_pmaps_searched) waiting_pmaps[waitlist_i(waitingp_i)] = 0; for(buddy_i = 0; buddy_i < pmap->bsize[blevel]; buddy_i++) { if(pmap->buddy[blevel][buddy_i] > (uint64_t)0) { @@ -295,11 +324,42 @@ void *palloc(size_t size) { } *bentry |= (unshifted_entry << bloc); } - if(!self_alloc) bzero(ret, size * 0x1000); + pmap->mutex = 0; + if(!self_alloc) bzero(ret, size * 0x1000); //TODO do we really need to bezero here? return ret; } } +get_next_pmap: + pmap->mutex = 0; + if(unlocked_pmaps_searched) { + pmap = 0; + for(searchingp_i = waitingp_i + 1; searchingp_i < pmap_count; searchingp_i++) { + if(waiting_pmaps[waitlist_i(searchingp_i)]) { + pmap = waiting_pmaps[waitlist_i(searchingp_i)]; + break; + } + } + if(!pmap) { + for(searchingp_i = 0; searchingp_i <= waitingp_i; searchingp_i++) { + if(waiting_pmaps[waitlist_i(searchingp_i)]) { + pmap = waiting_pmaps[waitlist_i(searchingp_i)]; + break; + } + } + } + } + else { + if(!pmap->next) { + pmap = waiting_pmaps ? waiting_pmaps[waitlist_i(0)] : 0; + unlocked_pmaps_searched = true; + } + else { + pmap = pmap->next; + } + } } + unlocked_pmaps_searched = false; + waitingp_i = 0; } return 0; } @@ -374,12 +434,19 @@ size_t map_complete_physical() { } } -pmap_t *init_pmap(size_t pagetable_size) { +void init_pmap_smp() { + size_t pmap_arrsize = corecount * pmap_count * sizeof(waiting_pmaps); + waiting_pmaps = malloc(pmap_arrsize); + bzero(waiting_pmaps, pmap_arrsize); +} + +void *init_pmap(size_t pagetable_size) { pmap_t *pmap, *last_pmap; struct memory_table *zones = (void *)ZONE_MAP; int budorder, zone_i; uint64_t pmap_size, pmap_bbitsize, zone_size; bool first_pmap_i = true; + @@ -387,6 +454,7 @@ pmap_t *init_pmap(size_t pagetable_size) { if((zones[zone_i].type == MEM_AVAILABLE) && (zones[zone_i].ACPI & 1) && zones[zone_i].length >= (0x2000)) { printf("found allocatable map at %p\n", zones[zone_i].base); + pmap_count++; last_pmap = pmap; if(zones[zone_i].base == (void *)0x100000) { zone_size = zones[zone_i].length - (((uint64_t)&_kernel_shared_zone_begin - 0x100000) + pagetable_size); @@ -396,7 +464,6 @@ pmap_t *init_pmap(size_t pagetable_size) { zone_size = zones[zone_i].length; pmap = PHYS_TO_VIRT(zones[zone_i].base); } - if(first_pmap_i) { pmap->next = NULL; first_pmap_i = false; @@ -405,6 +472,8 @@ pmap_t *init_pmap(size_t pagetable_size) { pmap->next = last_pmap; } + pmap->mutex = 0; + for(budorder = 0; budorder < MAX_BUDDY_ORDER; budorder++) { pmap_bbitsize = zone_size / (0x1000 << budorder); pmap->bsize[budorder] = DIV_ROUND_UP(pmap_bbitsize , 64); @@ -440,8 +509,8 @@ pmap_t *init_pmap(size_t pagetable_size) { } pmap_size = (uint64_t)(pmap->buddy[pmap->max_buddy] + pmap->bsize[pmap->max_buddy]) - (uint64_t)pmap; - first_pmap = pmap; //we spoof palloc into allocating from the specific required pmap. - palloc(pmap_size); //TODO (MAJOR BUG) something isn't right, I don't think + first_pmap = pmap; + palloc(pmap_size); } } return pmap; diff --git a/src/kernel/random.c b/src/kernel/random.c index 404223a..c959f6c 100644 --- a/src/kernel/random.c +++ b/src/kernel/random.c @@ -7,10 +7,9 @@ static bool hw_random = false; static unsigned long int seed = -1; void randinit() { - unsigned int unused, eax, ecx; - eax = 0; + unsigned int unused, ecx; ecx = 0; - __get_cpuid(1, &eax, &unused, &ecx, &unused); + __get_cpuid(1, &unused, &unused, &ecx, &unused); hw_random = (ecx >> 30) & 1; printf("Kernel random source: %s.\n", (hw_random) ? "rdrand" : "pseudo"); } @@ -31,6 +30,6 @@ unsigned int randint() { seed = 1103515245 * seed + 12345; return(unsigned int)(seed / 65536) % 32768; } - return 0; + return random_long; } diff --git a/src/kernel/smp.c b/src/kernel/smp.c index ff08f93..a55fe49 100644 --- a/src/kernel/smp.c +++ b/src/kernel/smp.c @@ -53,11 +53,30 @@ struct cpu_info { static struct gdt_descriptor gdtr; +struct cores_info cores; -void smp_boot() { +struct apicid_to_coreid_deleteme { //WILL BE DELETED AFTER THREADING EXISTS TODO + uint8_t apic_id; + uint8_t core_id; +}; + +static struct apicid_to_coreid_deleteme *apicid_to_coreid; + + +uint8_t get_coreid() { //WILL BE DELETED AFTER THREADING EXISTS TODO + uint32_t ebx, unused_cpuid; + uint8_t apic_id; + __get_cpuid(1, &unused_cpuid, &ebx, &unused_cpuid, &unused_cpuid); + apic_id = ebx >> 24; + for(uint8_t core = 0; core < corecount; core++) { + if(apicid_to_coreid[core].apic_id == apic_id) return apicid_to_coreid[core].core_id; + } + return 0; +} + +void smp_prepare() { uint8_t cores_active = 1; uint8_t stack_i = 0, core_i; - struct cores_info cores; struct icr_reg icr; struct cpu_info *stackarray; get_coreinfo(&cores); @@ -72,11 +91,18 @@ void smp_boot() { corecount = cores.corecount; stackarray = malloc(sizeof(struct cpu_info) * (cores.corecount - 1)); + apicid_to_coreid = malloc(sizeof(struct apicid_to_coreid_deleteme) * (cores.corecount - 1)); for(core_i = 0; core_i < cores.corecount; core_i++) { + + //WILL BE DELETED AFTER THREADING EXISTS TODO + apicid_to_coreid[core_i].apic_id = cores.apic_id[core_i]; + apicid_to_coreid[core_i].core_id = core_i; + if(cores.apic_id[core_i] == cores.bsp) continue; stackarray[stack_i].apic_id = cores.apic_id[core_i]; stackarray[stack_i].stack = palloc(0x1000); stackarray[stack_i].secondary_bsp = (stack_i)? false : true; + stack_i++; } for(stack_i = 0; stack_i < (cores.corecount - 1); stack_i++) { diff --git a/src/kernel/smp_racetest.c b/src/kernel/smp_racetest.c new file mode 100644 index 0000000..f86e030 --- /dev/null +++ b/src/kernel/smp_racetest.c @@ -0,0 +1,52 @@ +#define CHUNK_SIZE_FROM_INDEX(i) ((1 << ((i) + 5))) + +#include +#include +#include +#include +#include +#include + +//will delete later + +static uint8_t lockeroni = 0; + +void test_malloc(unsigned int cnt) { + void *testchunks[cnt]; + unsigned int rindex[cnt], testchunk_size, i, x; + + bzero(rindex, cnt * sizeof(unsigned int)); + for(x = 0; x < cnt; x++) { + testchunk_size = (CHUNK_SIZE_FROM_INDEX(randint() % 7) - 24); + testchunks[x] = malloc(testchunk_size); + printf("ALLOCATING CHUNK %p SIZE %i\n", (void *)testchunks[x] - 24, testchunk_size); + } + for(x = 0; x < cnt;) { + i = randint() % cnt; + if(rindex[i]) continue; + rindex[i] = x; + x++; + } + + for(x = 0; x < cnt; x++) { + //printf("FREEING CHUNK %p\n", (void *)testchunks[rindex[x]]); + free(testchunks[rindex[x]]); + } + + printf("\nmalloc tester:\n"); + printf("THIS NEEDS TO BE EMPTY______________\n"); + debug_heap(); + printf("____________________________________\n"); + unlock(&lockeroni); +} +uint8_t cores_waiting = 4; +void sync_malloc() { + void *mtest; + asm("lock decb [%0]\n" + "spinlock:\n" + "cmpb [%0], 0\n" + "jnz spinlock\n" + ::"m"(cores_waiting)); + mtest = palloc(0x1000); + printf("Make sure none of these match -> %lx\n", mtest); +} diff --git a/src/kernel/smp_trampoline.asm b/src/kernel/smp_trampoline.asm index 20c971e..cc91c3a 100644 --- a/src/kernel/smp_trampoline.asm +++ b/src/kernel/smp_trampoline.asm @@ -185,6 +185,7 @@ pause jnz .wait_for_gdt lgdt [final_gdt_descriptor] + mov rax, smp_kinit jmp rax diff --git a/src/kernel/testmalloc.c b/src/kernel/testmalloc.c deleted file mode 100644 index 5733c7c..0000000 --- a/src/kernel/testmalloc.c +++ /dev/null @@ -1,35 +0,0 @@ -#define CHUNK_SIZE_FROM_INDEX(i) ((1 << ((i) + 5))) - -#include -#include -#include -#include - -//will delete later - -void test_malloc(unsigned int cnt) { - void *testchunks[cnt]; - unsigned int rindex[cnt], testchunk_size, i, x; - - bzero(rindex, cnt * sizeof(unsigned int)); - for(x = 0; x < cnt; x++) { - testchunk_size = (CHUNK_SIZE_FROM_INDEX(randint() % 7) - 24); - testchunks[x] = malloc(testchunk_size); - //printf("ALLOCATING CHUNK %p SIZE %i\n", (void *)testchunks[x] - 24, testchunk_size); - } - for(x = 0; x < cnt;) { - i = randint() % cnt; - if(rindex[i]) continue; - rindex[i] = x; - x++; - } - for(x = 0; x < cnt; x++) { - //printf("FREEING CHUNK %p\n", (void *)testchunks[rindex[x]]); - free(testchunks[rindex[x]]); - } - printf("\nmalloc tester:\n"); - printf("THIS NEEDS TO BE EMPTY______________\n"); - debug_heap(); - printf("____________________________________\n"); - -} diff --git a/src/makefile b/src/makefile index cbf3ce1..bb92e5f 100644 --- a/src/makefile +++ b/src/makefile @@ -1,5 +1,4 @@ LD=../compiler/indigo_gcc/bin/x86_64-elf-ld -#CC=../compiler/indigo_gcc/bin/x86_64-elf-gcc CC=../compiler/indigo_gcc/bin/x86_64-pc-linux-gnu-gcc OBJCPY=../compiler/indigo_gcc/bin/x86_64-elf-objcopy INC=-I./include @@ -60,6 +59,9 @@ smp_trampoline.o: run: qemu-system-x86_64 $(QEMU_OPTS) $(QEMU_PRINTDEBUG) -nographic +run_quiet: + qemu-system-x86_64 $(QEMU_OPTS) $(QEMU_PRINTDEBUG) -nographic 2>/dev/null + gdb: indigo_os tmux new-session -s os_gdb "qemu-system-x86_64 -S -s $(QEMU_OPTS) -nographic"\;\ split-window -h "gdb -x debug/gdbinit.gdb; killall qemu-system-x86_64" diff --git a/src/page_backup.c b/src/page_backup.c new file mode 100644 index 0000000..cf6834a --- /dev/null +++ b/src/page_backup.c @@ -0,0 +1,465 @@ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +//just using char because c is a lil bitch and won't let us use void +extern char _kernel_shared_zone_begin; + + + +// PAGE MAPPING +#define PAGEMAP_LOCATION 0x10000 + +#define MAX_BUDDY_ORDER 8 +#define PALLOC_AUTO_BLEVEL MAX_BUDDY_ORDER + +typedef struct phys_map { + struct phys_map *next; + unsigned int max_buddy; + + bool mutex; //we might improve the speed of this later + + uint64_t bsize[MAX_BUDDY_ORDER]; + uint64_t *buddy[MAX_BUDDY_ORDER]; +} pmap_t; + +static pmap_t *first_pmap; + +#define MEM_AVAILABLE 1 +#define MEM_RESERVED 2 +#define MEM_APCI_RECLAIMABLE 3 +#define MEM_APCI_NVS 4 +#define MEM_BAD 5 + +// ZONES +#define ZONE_MAP_PLOC 0x7000 +#define ZONE_MAP PHYS_TO_VIRT(ZONE_MAP_PLOC) + + + +//reorganized (moved) from header +typedef struct __attribute__((packed)) { + unsigned int present : 1; // present, must be one when accessed. + unsigned int read_write : 1; // if set to one, read and write is set + unsigned int user : 1; // For seperating CPL 0-2 and 3+ + unsigned int writethrough_cache : 1; // honestly maybe I should look into caching + unsigned int cachable : 1; // hardware chaching. 0 is enabled, whats the worst that could happen? + unsigned int accessed : 1; // we'll never use any of these! + unsigned int zg0 : 1; // needs to be (and will be) zero'd + unsigned int size : 1; // if set to 1, this entry points to physical memory + unsigned int zg1 : 1; // needs to be (and will be) zero'd + unsigned int software_marks : 3; // available for our own use, I doubt we'll use it in such a simple thing + + uintptr_t base_ptr : 40; + unsigned int avail:11; + unsigned int no_exec:1; +} page_table; + + +struct memory_table { + void *base; + uint64_t length; + uint32_t type; + uint32_t ACPI; +} __attribute__((packed)); + +static bool NX_capable; +static bool huge_page_capable; + + +void get_mem_capabilities() { + uint32_t unused, edx; + __get_cpuid(0x80000001, &unused, &unused, &unused, &edx); + huge_page_capable = (edx >> 26) & 1; + NX_capable = (edx >> 20) & 1; +} + +void fix_stack() { + struct stack_frame *frame; + + asm("addq rsp, %0\n" + "addq rbp, %0\n" + "mov %0, rbp" + :"=r"(frame) + :"r"(PA_OFFSET)); + + while(frame->next != 0) { + printf("%p\n", frame->function_base); + frame->next = PHYS_TO_VIRT((void *)frame->next); + frame = frame->next; + } +} + + +void unmap_lowmem() { + //[future] + //eventually, you should use the function that unmaps pages when you write it + page_table *entry = (page_table *)PAGEMAP_LOCATION; + entry[0].present = 0; +} + +void debug_pzone() { + struct memory_table *memtable = (void *)ZONE_MAP; + printf(" __________________________________________________________________________\n"); + printf("| type\tstart\t\t\tend\t\t\tsize\t\t |\n"); + printf("|--------------------------------------------------------------------------|\n"); + for(unsigned int i = 0; memtable[i].length > 0; i++) { + printf("| %u %u\t0x%p\t0x%p\t0x%p |\n", memtable[i].type, memtable[i].ACPI, memtable[i].base, (memtable[i].base + memtable[i].length), memtable[i].length); + } + printf("----------------------------------------------------------------------------\n"); +} + +void ram_stresser() { + struct memory_table *memtable = (void *)ZONE_MAP - PA_OFFSET; + memtable[6].length = 0x10000; +} + +void debug_pmap() { + pmap_t *pmap = first_pmap; + int pmap_i = 0, order; + uint64_t blong_i, bbit_i, buddy_chunksize, omit_cnt; + printf("Maximum buddy order: %u (up to %#x sized chunks)\n", MAX_BUDDY_ORDER, ((0x1000 << MAX_BUDDY_ORDER) - 1)); + for(; pmap != 0; pmap = pmap->next) { + printf("Table %u:\n" + "\tPhysical/pmap start:\t%#p\n" + "\tTable Size:\t%u\n", pmap_i, pmap, + (uint64_t)(pmap->buddy[MAX_BUDDY_ORDER - 1] + pmap->bsize[MAX_BUDDY_ORDER - 1]) - (uint64_t)pmap); + + for(order = 0; order <= MAX_BUDDY_ORDER - 1; order++) { + buddy_chunksize = (0x1000 << order); //TODO just put it in the for loop + printf("\tbuddy[%u]:\n" + "\t\tAddress:\t%#p\n" + "\t\tSize:\t\t%u\n" + "\t\tBuddies:\t\t\n", order, pmap->buddy[order], pmap->bsize[order]); + + omit_cnt = 0; + + for(blong_i = 0; blong_i < pmap->bsize[order]; blong_i++) { + for(bbit_i = 0; bbit_i < 64; bbit_i++) { + if((pmap->buddy[order][blong_i]) & ((uint64_t)1 << bbit_i)) { + if((omit_cnt < 20) || (blong_i == pmap->bsize[order] - 1)) { + printf("address %#p\tbit %u: %p\t is free\n", + pmap->buddy[order] + blong_i, + bbit_i, + ((uint64_t)pmap - PA_OFFSET) + ((((blong_i * 64) + bbit_i) * buddy_chunksize))); + } + omit_cnt++; + if(omit_cnt == 20) { + printf("\t\t\t[more entries ommited]\n"); + } + } + } + } + } + pmap_i++; + } +} + +//TODO I know you don't want to, but you need to thoroughly check this. +void pfree(void *addr, size_t size) { + int blevel = 0; + uint64_t *onbyte; //the byte out buddy resides on in the current level + uint64_t page_bitloc; // how many bits we are away from buddy[0]. Helps calculate bitshifts + int bbitlen; //length of free'd area in current level + int lshift; //lshift is how many bits we shift over, rightbit is what it sounds like dumbass + pmap_t *pmap = first_pmap; + + /* note: there's no security check to see if the page is actually allocated, + * or if we are freeing the table itself. + * This should be okay, as only the kernel will be calling it. + * If it gets too messy we can always come back. + */ + + + if(((uintptr_t)addr & 4095) || (size & 4095)) { + PANIC(KERNEL_PANIC_INVALID_PFREE); + return; //TODO [minor] some more specificity, not a huge deal + } + size /= 0x1000; + for(; pmap != 0; pmap = pmap->next) { + page_bitloc = (addr - (void *)pmap) / 0x1000; + onbyte = pmap->buddy[0] + (page_bitloc / 64); + if((addr >= (void *)pmap) && onbyte < pmap->buddy[1]) break; + } + + while(blevel < MAX_BUDDY_ORDER) { + lshift = (page_bitloc / (1 << blevel)) & 63; + onbyte = pmap->buddy[blevel] + ((page_bitloc / 64) / (1 << blevel)); + bbitlen = size / (1 << blevel); + + + //TODO clean up this part ------------------------------------------------------------- (below) + if(bbitlen <= 1) { + if(lshift & 1) { + if((*onbyte >> (lshift - 1)) & 1) { + *onbyte &= ~(((uint64_t)1 << (lshift - 1)) | ((uint64_t)1 << lshift)); + size += (1 << blevel); + page_bitloc -= (1 << blevel); + bbitlen = size / (1 << blevel); + } + } + else if((*onbyte >> (lshift + 1)) & 1) { + *onbyte &= ~(((uint64_t)1 << (lshift + 1)) | ((uint64_t)1 << lshift)); + size += (1 << blevel); + bbitlen = size / (1 << blevel); + } + } + else if(((lshift + bbitlen) & 1) && ((*onbyte >> (lshift + bbitlen)) & 1)) { + *onbyte ^= ((uint64_t)1 << (lshift + bbitlen)); + size += (1 << blevel); + bbitlen = size / (1 << blevel); + } + //TODO clean up this part ------------------------------------------------------------- (above) + + if((!((size - 1) & size)) && (bbitlen != 1)) { + blevel = 63 - __builtin_clzl(size); + } + else { + if(bbitlen <= 1) { + *onbyte |= ((uint64_t)1 << lshift); + break; + } else if(bbitlen & 1) { //check me + size -= (1 << blevel); + *onbyte |= ((uint64_t)1 << (bbitlen + lshift)); + } + blevel++; + } + } +} + + +void *palloc(size_t size) { + bool self_alloc; + int min_blevel, blevel; + uint64_t bbit, unshifted_entry, threshold, bloc; //TODO move when you've confirmed casting stuff + uint64_t buddy_i, *ret, *bentry; + int itercount; + pmap_t *pmap = first_pmap; + + + if(size == 0) return 0; + if(size & 4095) { + size = DIV_ROUND_UP(size, 0x1000); + } + else { + size = size / 0x1000; + } + + //checking if pmap has been initilized; if not we've been called to self allocate + //the first buddy should never be allocated; that's where our pmap lives + if(pmap->buddy[pmap->max_buddy][0] & 1) { + self_alloc = true; + min_blevel = pmap->max_buddy; + } + else { + //log(size, 2) + self_alloc = false; + min_blevel = 63 - __builtin_clzl(size); + if(size & (size - 1)) min_blevel++; + if(min_blevel > MAX_BUDDY_ORDER - 1) return 0; + } + + for(blevel = min_blevel; blevel < MAX_BUDDY_ORDER; blevel++) { + for(pmap = first_pmap; pmap != 0; pmap = pmap->next) { + //pmap->mutex = true; + /** + if(!maps_transversed && get_set_mutex(&pmap->mutex)) { + //change get_coreid once we multithread + asm("mov al, 1\n" + "mov cl, %0\n" + "shl al, cl\n" + "lock or [%1], al\n" + ::"r"(get_coreid()), "m"(pmap->threads_searched) + :); + } + **/ + + for(buddy_i = 0; buddy_i < pmap->bsize[blevel]; buddy_i++) { + if(pmap->buddy[blevel][buddy_i] > (uint64_t)0) { //found buddy + bentry = &pmap->buddy[blevel][buddy_i]; + bbit = __builtin_ctzl(*bentry); + bloc = bbit; + + *bentry ^= (uint64_t)1 << bbit; + + ret = (((buddy_i * 64) + bbit) * (0x1000 << blevel)) + (void *)pmap; + + threshold = 0b11; + + itercount = 1; + for(blevel--; blevel >= 0; blevel--) { + bentry = pmap->buddy[blevel] + ((bentry - pmap->buddy[blevel + 1]) * 2); + itercount++; + if(bloc >= 32) bentry += 1; + bloc = (bloc * 2) & 63; // will be the amount we need to shift + bbit = ceil((float)size / (1 << blevel)); + + + unshifted_entry = ((uint64_t)1 << bbit) & threshold; + if(unshifted_entry) { + threshold = ((uint64_t)1 << (bbit * 2)) - 1; + } + else { + threshold = (threshold << 2) | threshold; + } + *bentry |= (unshifted_entry << bloc); + } + if(!self_alloc) bzero(ret, size * 0x1000); //TODO do we really need to bezero here? + return ret; + } + } + } + } + return 0; +} + + +//returns size of pages needed +size_t map_complete_physical() { + uint64_t total_mem; + unsigned int pdpe_cnt, pde_cnt, pde_max_i; + int zone_i, entry_i; + struct memory_table *zones = (void *)ZONE_MAP_PLOC; + + + page_table *pml4 = (page_table *)PAGEMAP_LOCATION; + page_table *pdpe = (page_table *)&_kernel_shared_zone_begin; + page_table *pde; + + for(zone_i = 0; zones[zone_i].length > 0; zone_i++); + total_mem = (uint64_t)zones[zone_i - 1].base + zones[zone_i - 1].length; + + pdpe_cnt = (total_mem + (0x40000000 - 1)) / 0x40000000; + + + entry_i = (PA_OFFSET >> 39) & 0x1ff; + pml4[entry_i].base_ptr = (uintptr_t)&_kernel_shared_zone_begin >> 12; + pml4[entry_i].read_write = 1; + pml4[entry_i].user = 0; + pml4[entry_i].size = 0; + pml4[entry_i].no_exec = 1; + pml4[entry_i].present = 1; + + if(huge_page_capable) { + for(int pdpe_i = 0; pdpe_i < pdpe_cnt; pdpe_i++) { + pdpe[pdpe_i].base_ptr = pdpe_i << 18; + pdpe[pdpe_i].read_write = 1; + pdpe[pdpe_i].user = 0; + pdpe[pdpe_i].size = 1; + pdpe[pdpe_i].no_exec = NX_capable; + pdpe[pdpe_i].present = 1; + } + return pdpe_cnt * 0x1000; + } + else { + pde_cnt = (total_mem + 0x100000) / 0x200000; + for(int pdpe_i = 0; pdpe_i < pdpe_cnt; pdpe_i++) { + pde = (page_table *)(&_kernel_shared_zone_begin + (pdpe_cnt * 0x1000) + (pdpe_i * 0x1000)); + + if((pdpe_i < pdpe_cnt - 1) || (!(pde_cnt & 511))) { + pde_max_i = 512; + } + else { + pde_max_i = pde_cnt & 511; + } + + pdpe[pdpe_i].base_ptr = (uintptr_t)pde >> 12; + pdpe[pdpe_i].read_write = 1; + pdpe[pdpe_i].user = 0; + pdpe[pdpe_i].size = 0; + pdpe[pdpe_i].no_exec = NX_capable; + pdpe[pdpe_i].present = 1; + + for(int pde_i = 0; pde_i < pde_max_i; pde_i++) { + pde[pde_i].base_ptr = ((pdpe_i << 9) + pde_i) << 9; + pde[pde_i].read_write = 1; + pde[pde_i].user = 0; + pde[pde_i].size = 1; + pde[pde_i].no_exec = NX_capable; + pde[pde_i].present = 1; + } + } + return (pdpe_cnt * 2) * 0x1000; + } +} + +pmap_t *init_pmap(size_t pagetable_size) { + pmap_t *pmap, *last_pmap; + struct memory_table *zones = (void *)ZONE_MAP; + int budorder, zone_i; + uint64_t pmap_size, pmap_bbitsize, zone_size; + bool first_pmap_i = true; + + + + for(zone_i = 0; zones[zone_i].length > 0; zone_i++) { + if((zones[zone_i].type == MEM_AVAILABLE) && (zones[zone_i].ACPI & 1) && + zones[zone_i].length >= (0x2000)) { + printf("found allocatable map at %p\n", zones[zone_i].base); + last_pmap = pmap; + if(zones[zone_i].base == (void *)0x100000) { + zone_size = zones[zone_i].length - (((uint64_t)&_kernel_shared_zone_begin - 0x100000) + pagetable_size); + pmap = PHYS_TO_VIRT((void *)&_kernel_shared_zone_begin + pagetable_size); + } + else { + zone_size = zones[zone_i].length; + pmap = PHYS_TO_VIRT(zones[zone_i].base); + } + if(first_pmap_i) { + pmap->next = NULL; + first_pmap_i = false; + } + else { + pmap->next = last_pmap; + } + + pmap->mutex = false; + + for(budorder = 0; budorder < MAX_BUDDY_ORDER; budorder++) { + pmap_bbitsize = zone_size / (0x1000 << budorder); + pmap->bsize[budorder] = DIV_ROUND_UP(pmap_bbitsize , 64); + if(budorder) { + pmap->buddy[budorder] = pmap->buddy[budorder - 1] + pmap->bsize[budorder - 1]; + } + else { + pmap->buddy[0] = (void *)pmap + sizeof(*pmap); + } + if(budorder < MAX_BUDDY_ORDER - 1) { + bzero(pmap->buddy[budorder], pmap->bsize[budorder] * 8); + if(pmap_bbitsize & 1) { + pmap->buddy[budorder][pmap->bsize[budorder] - 1] = + ((uint64_t)1 << ((pmap_bbitsize - 1) & 63)); + } + if(pmap_bbitsize == 1) { + pmap->max_buddy = budorder; + for(budorder++; budorder < MAX_BUDDY_ORDER; budorder++) { + pmap->buddy[budorder] = 0; + pmap->bsize[budorder] = 0; + } + break; + } + } + else { + pmap->max_buddy = MAX_BUDDY_ORDER - 1; + memset(pmap->buddy[budorder], UINT8_MAX, pmap->bsize[budorder] * 8); + if((pmap_bbitsize / 64) != (pmap->bsize[budorder])) { + pmap->buddy[budorder][pmap->bsize[budorder] - 1] = + (((uint64_t)1 << (pmap_bbitsize & 63)) - 1); + } + } + } + + pmap_size = (uint64_t)(pmap->buddy[pmap->max_buddy] + pmap->bsize[pmap->max_buddy]) - (uint64_t)pmap; + first_pmap = pmap; //we spoof palloc into allocating from the specific required pmap. + palloc(pmap_size); + } + } + return pmap; +} -- cgit v1.2.3