Replace memory system with binary pages and bitwise permissions

[daiagi]

What we need to do

Current memory system uses nested maps (%{page => %{offset => byte}}) which is slow. Replace with pre-allocated binary pages and fast bitwise permission checking.

Expected outcome

3x speedup on memory operations (30% of all instructions)

New Memory Architecture

Core structure:

defmodule PVM.Memory.Fast do
  defstruct [
    pages: %{},           # %{page_num => <<4096_bytes>>}
    permissions: <<>>,    # 2 bits per page: 00=none, 01=read, 10=write, 11=both  
    page_size: 0x1000,
    size: 0x1_0000_0000
  ]
end

1. Construct Memory

Replace PreMemory.finalize() complex logic:

def construct_memory(regions) do
  # Build permissions bitstring from regions
  permissions = build_permissions(regions)
  
  # Load initial data into binary pages
  pages = load_initial_pages(regions)
  
  %Memory.Fast{pages: pages, permissions: permissions}
end

defp build_permissions(regions) do
  max_pages = 0x10_0000
  
  # Start with all pages having no access (00)
  permissions = for _page <- 0..(max_pages-1), into: <<>>, do: <<0::2>>
  
  # Apply each region in order (later regions override earlier ones)
  Enum.reduce(regions, permissions, fn {start_page, end_page, access_type}, acc ->
    perm_bits = case access_type do
      nil -> 0      # 00 = no access
      :read -> 1    # 01 = read only  
      :write -> 2   # 10 = write only
      _ -> 3        # 11 = read+write
    end
    
    set_page_permissions(acc, start_page, end_page, perm_bits)
  end)
end

defp load_initial_pages(regions) do
  Enum.reduce(regions, %{}, fn
    {start_addr, _end, data, _access} when is_binary(data), acc ->
      page_num = div(start_addr, 0x1000)
      page_offset = rem(start_addr, 0x1000)
      
      page = Map.get(acc, page_num, <<0::8*0x1000>>)
      updated_page = write_to_page_binary(page, page_offset, data)
      Map.put(acc, page_num, updated_page)
      
    _empty_region, acc -> acc
  end)
end

2. Construct Permissions

Replace RangeManager complexity with direct bitstring ops:

defp set_page_permissions(permissions, start_page, end_page, perm_bits) do
  # Update permissions for page range
  for page <- start_page..end_page, reduce: permissions do
    acc -> 
      bit_offset = page * 2
      <<before::bitstring-size(bit_offset), _old::2, after_::bitstring>> = acc
      <<before::bitstring, perm_bits::2, after_::bitstring>>
  end
end

3. Check Permissions

Replace O(log n) binary search with O(1) bitwise check:

# Current (slow): binary search through ranges
def find_access_for_page(access_ranges, page) do
  RangeManager.binary_search_range(ranges_tuple, page, 0, size - 1)
end

# New (fast): direct bitwise lookup
def can_access?(permissions, page_num, access_type) do
  bit_offset = page_num * 2
  <<_::bitstring-size(bit_offset), perm::2, _::bitstring>> = permissions
  
  case {access_type, perm} do
    {:read, p} when p in [1, 3] -> true   # 01 or 11
    {:write, p} when p in [2, 3] -> true  # 10 or 11
    _ -> false
  end
end

# Edge case: always grant permission for 0 bytes/pages
def can_access?(_permissions, _page_num, _access_type, 0), do: true

4. Write Memory

Replace nested map updates with binary pattern matching:

# Current (slow): per-byte map operations
def write_to_sparse(memory, address, value) do
  Enum.reduce(bytes, memory.data, fn {byte, index}, acc ->
    updated_page = Map.get(acc, page_num, %{}) |> Map.put(page_offset, byte)
    Map.put(acc, page_num, updated_page)
  end)
end

# New (fast): direct binary update
def write(memory, address, value) do
  page_num = div(address, memory.page_size)
  page_offset = rem(address, memory.page_size)
  
  # Check permissions (O(1) instead of O(log n))
  if can_access?(memory.permissions, page_num, :write) do
    # Get or create page
    page = Map.get(memory.pages, page_num, <<0::8*memory.page_size>>)
    
    # Update using binary pattern matching
    updated_page = write_to_page_binary(page, page_offset, value)
    
    {:ok, %{memory | pages: Map.put(memory.pages, page_num, updated_page)}}
  else
    {:error, {:fault, page_num * memory.page_size}}
  end
end

defp write_to_page_binary(page, offset, value) do
  value_size = byte_size(value)
  <<before::binary-size(offset), _old::binary-size(value_size), after_::binary>> = page
  <<before::binary, value::binary, after_::binary>>
end

5. Read Memory

Replace per-byte map lookups with binary slicing:

# Current (slow): byte-by-byte map access
def read_from_sparse(memory, address, length) do
  Enum.map(0..(length-1), fn offset ->
    Map.get(data, page_num, %{}) |> Map.get(page_offset, 0)
  end) |> :binary.list_to_bin()
end

# New (fast): direct binary slice
def read(memory, address, length) do
  # Edge case: 0 bytes always succeeds
  if length == 0, do: {:ok, <<>>}
  
  page_num = div(address, memory.page_size) 
  page_offset = rem(address, memory.page_size)
  
  if can_access?(memory.permissions, page_num, :read) do
    page = Map.get(memory.pages, page_num, <<0::8*memory.page_size>>)
    <<_::binary-size(page_offset), data::binary-size(length), _::binary>> = page
    {:ok, data}
  else
    {:error, {:fault, page_num * memory.page_size}}
  end
end

6. Edge Cases

Handle 0-byte operations efficiently:

# Always grant permission for empty operations
def check_access(_memory, _address, 0, _access_type), do: true
def write(_memory, _address, <<>>), do: {:ok, memory}
def read(_memory, _address, 0), do: {:ok, <<>>}

# Handle cross-page reads/writes by splitting into page chunks
def read_multi_page(memory, address, length) when length > memory.page_size do
  # Split into page-sized chunks and read each
end

Implementation Tasks

Task 1: Replace RangeManager.binary_search_range with can_access? bitwise checks
Task 2: Convert PreMemory.finalize complex overlap resolution to build_permissions
Task 3: Update Memory.write to use binary pattern matching instead of nested maps
Task 4: Update Memory.read to use binary slicing instead of per-byte map access

[daiagi]

EDIT
due to your question about bitstring write efficiency
so indeed, the entire 4096 bitstring will be re-allocated per write => not good

here is other solution:

Page representation:

• nil → page not allocated (no access)
• binary → read-only page (compact, immutable, cheap to clone)
• :atomics → read/write page (fast O(1) updates, concurrent-safe)
• Unallocated pages (nil) can be optimized further (Lazy Allocation):

• First read → just return 0.
• First write → allocate an :atomics page.

Permissions:

• bitstring should be fine, since we don't expect many permissions changes
• can consider doing an atomics version and benchmark the two against eachother,
• bitstring is O(1) reads and O(n) write and takes 256kb memory
• atomics are O(1) read/write, but 1MB of memory

Page transitions

• RO → RW: allocate :atomics, copy binary into it (~4 KiB copy).
• RW → RO: can consider packing :atomics back into binary (~4 KiB copy). (reduce memory allocation)