import "io"

static { free_page_list = 0, num_free_pages = 0, num_pages_allocated = 0,
         pages_needed_for_free_list = 0, last_used_page_addr = 0, PD_addr = 0 }

manifest { out_of_memory = -999 }

let organise_free_pages() be
{ let size_needed, total_words = 0, total_pages, first_free_page_addr, pos, page_addr;
  let addresses = vec(16);
  size_needed := $memory_available(nil, 0);
  $memory_available(addresses, size_needed);   

  out("these areas of memory exist:\n");
  for i = 2 to size_needed - 1 by 2 do
  { out("  %d: 0x%08X to 0x%08X\n", i, addresses ! i, addresses ! (i + 1));
    total_words +:= addresses ! (i + 1) - addresses ! i + 1 }

  total_pages := total_words / page$size;
  out("%d words = %d pages in total\n", total_words, total_pages);
  out("this program is occupying 0x%08X to 0x%08X\n", addresses ! 0, addresses ! 1);

  first_free_page_addr := (addresses ! 1 + page$size - 1) bitand bitnot page$offsetmask;
  out("first free page is number %d at address 0x%08X\n",
      first_free_page_addr >> page$offsetbits, first_free_page_addr);

  last_used_page_addr := first_free_page_addr - page$size;
  pages_needed_for_free_list := total_pages + page$size - 1 >> page$offsetbits;
  out("%d pages needed for free list\n", pages_needed_for_free_list);
  free_page_list := first_free_page_addr;
  first_free_page_addr +:= pages_needed_for_free_list << page$offsetbits;

  num_free_pages := 0;
  pos := free_page_list;
  addresses ! 2 := first_free_page_addr;
  for i = 2 to size_needed - 1 by 2 do
  { page_addr := addresses ! i;
    while page_addr ##<= addresses ! (i + 1) do
    { ! pos := page_addr;
      num_free_pages +:= 1;
      pos +:= 1;
      page_addr +:= page$size } }
  page_addr := 0;
  while page_addr ##<= last_used_page_addr do
  { ! pos := page_addr;
    num_free_pages +:= 1;
    pos +:= 1;
    page_addr +:= page$size }

  out("%d free pages\n", num_free_pages) }


// the following version will only work while physical addresses are still in use

let get_free_page() be
{ let addr;

  if num_free_pages <= 0 then
    resultis out_of_memory;

  addr := free_page_list ! num_pages_allocated;

  num_pages_allocated +:= 1;
  num_free_pages -:= 1;
  resultis addr }


// the following will never be used, it is just illustrative

let make_page_free(addr) be
{ // proper page addresses only have zeros in their last 11 bits
  if (addr bitand page$offsetmask) <> 0 then
  { out("\nbad page address %08X given to make_page_free\n", addr);
    resultis out_of_memory }

  num_free_pages +:= 1;
  num_pages_allocated -:= 1;

  if num_pages_allocated < 0 then
  { out("\nmemory management error, too many free pages\n");
    resultis out_of_memory }

  free_page_list ! num_pages_allocated := addr;
  resultis 1 }

manifest { bottom_user_code_va = 0x00000000,
           top_user_stack_va =   0x7FFFFFFF,
           bottom_os_code_va =   0x80000000,
           top_os_stack_va =     0xBFFFFFFF,
           bottom_os_attic_va =  0xC0000000,
           os_attic_page2_va =   0xC0000800,
           after_os_attic_va =   0xC0000000 + page$size * page$size }

manifest { num_free_pages_offset = 0,
           num_pages_allocated_offset = 1,
           free_page_list_offset = 2 }

let pd_position_for_va(a) = page$tablenumsel from a;

let pt_position_for_va(a) = page$pageintablesel from a;

let word_position_for_va(a) = page$offsetsel from a;

let single_va_test(a) be
{ out("0x%08x: table %4d, page %4d, offset %4d\n", a,
      pd_position_for_va(a),
      pt_position_for_va(a),
      word_position_for_va(a)) }

let va_test() be
{ single_va_test(bottom_user_code_va);
  single_va_test(top_user_stack_va);
  single_va_test(bottom_os_code_va);
  single_va_test(top_os_stack_va);
  single_va_test(bottom_os_attic_va);
  single_va_test(os_attic_page2_va);
  single_va_test(after_os_attic_va) }
  

let free_pages_test_one() be
{ let v = vec(10);

  for i = 0 to 9 do
  { v ! i := get_free_page();      
    out("got page %08X\n", v ! i) }

  for i = 8 to 2 by -2 do
  { make_page_free(v ! i);
    out("freeing page %08X\n", v ! i) }

  for i = 0 to 9 do
  { v ! i := get_free_page();
    out("got page %08X\n", v ! i) } }


let free_pages_test_two() be
{ let addr, total = 0;

  while true do
  { addr := get_free_page();
    if addr = out_of_memory then    
      break;
    out("%08X ", addr);
    total +:= 1 }

  out("\nTotal %d\n", total) }


let print_mem_map(pdaddr) be
{ out("Memory map stored in pp %d:\n", pdaddr >> 11); // pp = physical page

  for ptn = 1023 to 0 by -1 do            // ptn = page table number
    if pdaddr ! ptn <> 0 then
    { let ptppn = (pdaddr ! ptn) >> 11;   // page table's phys page num
      let ptaddr = ptppn << 11;           // page table's address
      out("  %4d: pp %d for VAs 0x%08x to 0x%08x:\n",
             ptn,   ptppn,     ptn << 22, ((ptn + 1) << 22) - 1);

      for dpn = 2047 to 0 by -1 do        // data page number
        if ptaddr ! dpn bitand page$validmask then
        { let dpppn = (ptaddr ! dpn) >> 11;  // data page's phys page num
          let baseva = (ptn << 22) + (dpn << 11);
          out("      %4d: pp %d for VAs 0x%08x to 0x%08x\n",
                     dpn,    dpppn,     baseva,   baseva + 2047); } } }


// this is going to be our user "program"

let compute() be
{ let x = 0, 
      nfree = bottom_os_attic_va ! num_free_pages_offset,
      nalloc = bottom_os_attic_va ! num_pages_allocated_offset,
      freelist = bottom_os_attic_va ! free_page_list_offset;
  showdec(nfree);
  showch(' ');
  showhex(freelist ! nalloc);
  showch('\n');
  showdec(recursive(600)); }

/*  for i = 0 to 15 do
  { let ch = i + 'A';
       only the compute function is going to be copied into the user addr space,
       not the whole io library, so we can't print things in the normal way.
    assembly
    { type [<ch>] }
    for j = 1 to 200 do
    { for k = 0 to 1000 do
        x +:= 1;
      for k = 0 to 999 do
        x -:= 1 } } }
*/

and recursive(n) be
{ let x = 0;
  if n > 0 then
    resultis 1 + recursive(n - 1);
  resultis 0; }

and showch(c) be
  assembly 
  { type [<c>] } 

and showdec(n) be
{ let d = n rem 10 + '0';
  if n > 9 then
    showdec(n / 10);
  showch(d) }

and showhex(n) be
{ let r = n bitand 0b1111,
      q = n >> 4;
  if q > 0 then
    showhex(q);
  test r > '9' then
    showch('A' + r - 10)
  else
    showch('0' + r) }

let after_compute() be
{ }


let run_user() be
{ let addr = 0xC0000000;
  out("Pretend operating system jumping to 0x800\n");
  assembly
  { load r0, [<addr>]
    store r0, sp }
  $set_flag(flag$sys, 0);

  0x800() }

manifest
{ free_page_list_ptr = 0xC0000000 + free_page_list_offset,
  num_alloc_pages_ptr = 0xC0000000 + num_pages_allocated_offset,
  usr_stack_pt = 0xC04FF800 }

let handler pf(oldflags, intcode, info1, info2, fp, sp, r12, r11, r10, r9,
              r8, r7, r6, r5, r4, r3, r2, r1, r0) be
{ out("%d %08X %08X\n", intcode, info1, info2); 
  if info1 = 0 then
    finish;
  usr_stack_pt ! 2046 := (! free_page_list_ptr) ! (! num_alloc_pages_ptr) bitor 1 }

let create_page_table_and_start() be
{ let start_address, code_addr, last_used_page, pn, flags, user_code_page,
      OS_stack_PT, OS_code_PT, OS_attic_PT, USR_stack_PT, USR_code_PT,
      OS_attic_first_page, pa, source_address;
  let iv = vec(sizeof$intvec);

                                  // get a page to be the page directory
  PD_addr := get_free_page();
                                  // get pages for the five page tables
  OS_stack_PT := get_free_page();
  OS_code_PT := get_free_page();
  OS_attic_PT := get_free_page();
  USR_stack_PT := get_free_page();
  USR_code_PT := get_free_page();

  $clear_physical_page(PD_addr);
  $clear_physical_page(OS_stack_PT);
  $clear_physical_page(OS_code_PT);
  $clear_physical_page(OS_attic_PT);
  $clear_physical_page(USR_stack_PT);
  $clear_physical_page(USR_code_PT);

  PD_addr ! pd_position_for_va(top_os_stack_va) := OS_stack_PT bitor page$validmask;
  PD_addr ! pd_position_for_va(bottom_os_code_va) := OS_code_PT bitor page$validmask;
  PD_addr ! pd_position_for_va(top_user_stack_va) := USR_stack_PT bitor page$validmask;
  PD_addr ! pd_position_for_va(bottom_user_code_va) := USR_code_PT bitor page$validmask;
  PD_addr ! pd_position_for_va(bottom_os_attic_va) := OS_attic_PT bitor page$validmask;


  pa := get_free_page();
  $clear_physical_page(pa);
  USR_stack_PT ! pt_position_for_va(top_user_stack_va) := pa bitor page$validmask;

  pa := get_free_page();
  $clear_physical_page(pa);
  OS_stack_PT ! pt_position_for_va(top_os_stack_va) := pa bitor page$validmask;

  user_code_page := get_free_page();
  $clear_physical_page(user_code_page);
  USR_code_PT ! pt_position_for_va(page$size) := user_code_page bitor page$validmask;

  pa := get_free_page();
  $clear_physical_page(pa);
  pa ! num_free_pages_offset := num_free_pages;
  pa ! num_pages_allocated_offset := num_pages_allocated;
  pa ! free_page_list_offset := after_os_attic_va - pages_needed_for_free_list * page$size;
  OS_attic_PT ! pt_position_for_va(bottom_os_attic_va) := pa bitor page$validmask;
  for pi = 0 to pages_needed_for_free_list - 1 do
    OS_attic_PT ! (page$size - pages_needed_for_free_list + pi) :=
      (free_page_list + pi * page$size) bitor page$validmask;

  // OS_attic_PT ! 1 := PD_addr bitor page$validmask;  
     // this makes the page directory available at virtual addresses C0000800 to C0000FFF

  PD_addr ! 769 := PD_addr bitor page$validmask;
     // this makes all of the page tables available, even ones not yet created:
     //    user code PT at VAs  C0400000 to C04007FF
     //    user stack PT at VAs C04FF800 to C04FFFFF
     //    sys code PT at VAs   C0500000 to C05007FF
     //    sys stack PT at VAs  C057F800 to C057FFFF
     //    sys attic PT at VAs  C0580000 to C05807FF
     //    page dir again at    C0580800 to C0580FFF

  out("%d free pages remaining\n", num_free_pages);      

  // make this entire program be the pretend operating system starting at 0x80000000

  for i = 0 to last_used_page_addr >> page$offsetbits do
    OS_code_PT ! i := (i << page$offsetbits) bitor page$validmask;

  print_mem_map(PD_addr);

  // make the pretend user program appear at virtual address 0x800

  $memory_move(user_code_page, compute, after_compute - compute);

  $memory_zero(iv, sizeof$intvec);
  iv ! int$pagefault := pf + 0x80000000;

  $set_special_register(sr$intvec, iv);
  $enable_interrupts();

  // finally let it happen
  
  $set_special_register(sr$pdbr, PD_addr);

  flags := $get_special_register(sr$flags) bitor flag$maskvm;

  // if jump before VM is on, destination VA won't work
  // if VM on before jump, next instruction (the jump) is lost
  // so the two actions must be simultaneous

  $set_flags_and_jump(flags, run_user + 0x80000000);

  outs("we won't see this\n") }


let start() be
{ organise_free_pages();
  create_page_table_and_start() }