import "io"

static { free_page_list = 0, num_free_pages = 0, num_pages_allocated = 0,
         pages_needed_for_free_list = 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,
      last_used_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 }

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) }


manifest { num_free_pages_offset = 0,
           num_pages_allocated_offset = 1 }

let create_page_table_and_start() be
{ let start_address, code_addr, srcaddr, last_used_page, pn, flags;
  let OS_stack_PT, OS_code_PT, OS_attic_PT, USR_stack_PT, USR_code_PT,
  OS_attic_first_page, pa;

                                  // 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;

  pa := get_free_page();
  $clear_physical_page(pa);
  USR_code_PT ! pt_position_for_va(page$size) := pa 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;
  OS_attic_PT ! pt_position_for_va(bottom_os_attic_va) := pa bitor page$validmask;
  for pi = 0 to pages_needed_for_free_list do
    OS_attic_PT ! (page$size - pages_needed_for_free_list + pi) :=
      (free_page_list + pi * page$size) bitor page$validmask }


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); } } }


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