import "io"

static { free_page_list = 0, num_free_pages = 0, num_used_pages = 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);   

  for i = 2 to size_needed - 1 by 2 do
    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_used_pages;

  num_used_pages +:= 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_used_pages -:= 1;

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

  free_page_list ! num_used_pages := addr;
  resultis 1 }

manifest { pt_pos_for_usr_code = 0,
           pt_pos_for_usr_stk  = 511,
           pt_pos_for_sys_code = 512,
           pt_pos_for_sys_stk  = 767,
           pt_pos_for_attic    = 768,
           pt_pos_for_trick_pd = 769,

           bottom_usr_code_va  = pt_pos_for_usr_code << 22,                 // this is 00000000
           bottom_sys_code_va  = pt_pos_for_sys_code << 22,                 // this is 80000000
           bottom_attic_va     = pt_pos_for_attic    << 22,                 // this is C0000000
           pt_va_base          = pt_pos_for_trick_pd << 22,                 // this is C0400000
           top_usr_stk_va      = bottom_sys_code_va - 1,                    // this is 7FFFFFFF
           top_sys_stk_va      = bottom_attic_va - 1,                       // this is BFFFFFFF
           after_attic_va      = bottom_attic_va + (1 << 22),               // this is C0400000

           usr_code_pt_va      = pt_va_base + (pt_pos_for_usr_code << 11),  // this is C0400000
           usr_stk_pt_va       = pt_va_base + (pt_pos_for_usr_stk  << 11),  // this is C04FF800
           sys_code_pt_va      = pt_va_base + (pt_pos_for_sys_code << 11),  // this is C0500000
           sys_stk_pt_va       = pt_va_base + (pt_pos_for_sys_stk  << 11),  // this is C057F800
           attic_pt_va         = pt_va_base + (pt_pos_for_attic    << 11),  // this is C0580000
           trick_pd_va         = pt_va_base + (pt_pos_for_trick_pd << 11),  // this is C0580800

           num_free_pages_offset = 0,
           num_used_pages_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_usr_code_va);
  single_va_test(top_usr_stk_va);
  single_va_test(bottom_sys_code_va);
  single_va_test(top_sys_stk_va);
  single_va_test(bottom_attic_va);
  single_va_test(pt_va_base);
  single_va_test(after_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 page directory at PA %08X = pp %d:\n", pdaddr, pdaddr >> 11);

  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: for VAs 0x%08x to 0x%08x in PA %08X = pp %d:\n",
             ptn, ptn << 22, ((ptn + 1) << 22) - 1, ptppn << 11, ptppn);

      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: for VAs 0x%08x to 0x%08x in PA %08X = pp %d\n",
                     dpn, baseva, baseva + 2047, dpppn << 11, dpppn); } } }


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

manifest
{ free_page_list_ptr = bottom_attic_va + free_page_list_offset,
  num_used_pages_ptr = bottom_attic_va + num_used_pages_offset,
  num_free_pages_ptr = bottom_attic_va + num_free_pages_offset }

let compute() be
{ showdec(! num_free_pages_ptr);
  showch(' ');
  showhex((! free_page_list_ptr) ! (! num_used_pages_ptr));
  showch('\n');
  showdec(recursive(600));
  showch('\n');
  exit(0) }

and exit(n) be
{ assembly { halt } }

/*  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
{ out("Pretend operating system jumping to 0x800\n");
  $set_special_register(sr$syssp, top_sys_stk_va + 1);
  $set_special_register(sr$sysfp, top_sys_stk_va + 1);
  $set_flag(flag$sys, 0);
  0x800() }

let rest_of_os() be
{ out("OS in command again\n") }

let handler halt_handler() be
{ let addr = rest_of_os;
  let flags;
  assembly
  { load r1,  [<addr>]
    store r1, [fp + 1]
    load r1,  [fp + 3]
    store r1, [<flags>] }
  flags := flags bitor flag$sys;
  assembly
  { load  r1, [<flags>]
    store r1, [fp + 3] } }

let handler page_fault_handler(oldflags, intcode, pf_address, info2, fp, sp, r12,
                               r11, r10, r9, r8, r7, r6, r5, r4, r3, r2, r1, r0) be
{ let pd_entry = pd_position_for_va(pf_address),
      pt_entry = pt_position_for_va(pf_address);
  out("\npage fault (%d) for address %08X, in page table %d, page %d\n", intcode, pf_address, pd_entry, pt_entry);
  if pd_entry <> pt_pos_for_usr_stk then
  { out("page fault not in user stack area\n"); 
    assembly
    { halt } }
  usr_stk_pt_va ! pt_entry := (! free_page_list_ptr) ! (! num_used_pages_ptr) bitor page$validmask }

let create_page_table_and_start() be
{ let start_address, code_addr, last_used_page, pn, flags, usr_code_page,
      sys_stk_pt, sys_code_pt, attic_pt, usr_stk_pt, usr_code_pt,
      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
  sys_stk_pt  := get_free_page();
  sys_code_pt := get_free_page();
  attic_pt    := get_free_page();
  usr_stk_pt  := get_free_page();
  usr_code_pt := get_free_page();

  $clear_physical_page(pd_addr);
  $clear_physical_page(sys_stk_pt);
  $clear_physical_page(sys_code_pt);
  $clear_physical_page(attic_pt);
  $clear_physical_page(usr_stk_pt);
  $clear_physical_page(usr_code_pt);

  pd_addr ! pd_position_for_va(top_sys_stk_va)     := sys_stk_pt  bitor page$validmask;
  pd_addr ! pd_position_for_va(bottom_sys_code_va) := sys_code_pt bitor page$validmask;
  pd_addr ! pd_position_for_va(top_usr_stk_va)     := usr_stk_pt  bitor page$validmask;
  pd_addr ! pd_position_for_va(bottom_usr_code_va) := usr_code_pt bitor page$validmask;
  pd_addr ! pd_position_for_va(bottom_attic_va)    := attic_pt    bitor page$validmask;


  pa := get_free_page();
  $clear_physical_page(pa);
  usr_stk_pt ! pt_position_for_va(top_usr_stk_va) := pa bitor page$validmask;

  pa := get_free_page();
  $clear_physical_page(pa);
  sys_stk_pt ! pt_position_for_va(top_sys_stk_va) := pa bitor page$validmask;

  usr_code_page := get_free_page();
  $clear_physical_page(usr_code_page);
  usr_code_pt ! pt_position_for_va(page$size) := usr_code_page bitor page$validmask;

  pa := get_free_page();
  $clear_physical_page(pa);
  pa ! num_free_pages_offset := num_free_pages;
  pa ! num_used_pages_offset := num_used_pages;
  pa ! free_page_list_offset := after_attic_va - pages_needed_for_free_list * page$size;
  attic_pt ! pt_position_for_va(bottom_attic_va) := pa bitor page$validmask;

  for pgidx = 0 to pages_needed_for_free_list - 1 do
    attic_pt ! (page$size - pages_needed_for_free_list + pgidx) :=
      (free_page_list + pgidx * page$size) bitor page$validmask;

  // attic_pt ! 1 := pd_addr bitor page$validmask;  
     // this made the page directory available at virtual addresses C0000800 to C0000FFF

  pd_addr ! pt_pos_for_trick_pd := 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
  iv ! int$pagefault := page_fault_handler + bottom_sys_code_va;
     //    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 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
    sys_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(usr_code_page, compute, after_compute - compute);

  $memory_zero(iv, sizeof$intvec);
  iv ! int$pagefault := page_fault_handler + bottom_sys_code_va;
  iv ! int$halt := halt_handler + bottom_sys_code_va;

  $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 + bottom_sys_code_va);

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


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