wasm-server-experiment/src/memory.wat

(func $memory_init
  (local $memorySize i32)
  ;; starting location
  i32.const 4

  ;; get num pages
  memory.size

  ;; shift left by 16 bits to get byte size
  i32.const 16
  i32.shl
  i32.const 4
  i32.sub

  ;; place start/end tags
  call $memory_markBlockSize
)

;; this runs into issue when allocating the final block in memory
;; our end spot is not aligned with our block size rounding
(func $memory_alloc (export "alloc") (param $requestedBytes i32) (result i32)
  (local $blockAddr i32)
  local.get $requestedBytes
  call $memory_findFreeBlock
  local.tee $blockAddr

  ;; check if we found a block
  i32.eqz
  if
    i32.const 0
    return
  end

  ;; potentially split block
  local.get $blockAddr
  local.get $requestedBytes
  call $memory_splitFreeBlock

  ;; mark used
  local.get $blockAddr
  call $memory_markBlockUsed

  ;; offset boundary address to get usable pointer
  local.get $blockAddr
  i32.const 4
  i32.add
  return
)

(func $memory_free (export "free_block") (param $pointer i32)
  (local $startPointer i32)
  (local $blockSize i32)
  (local $temp i32)

  ;; start with the direct block
  local.get $pointer
  i32.const 4
  i32.sub
  local.tee $startPointer
  call $memory_getUsableSizeOfBlock
  i32.const 8
  i32.add
  local.set $blockSize

  ;; check block before
  local.get $startPointer
  i32.const 4
  i32.sub
  local.tee $temp
  call $memory_isBlockUsed
  i32.eqz
  local.get $temp
  i32.const 4 ;; start of allocateable memory
  i32.ge_u
  i32.and

  if
    ;; update start of block
    local.get $temp
    local.get $temp
    call $memory_getUsableSizeOfBlock
    i32.const 4
    i32.add
    i32.sub
    local.tee $startPointer

    ;; update size
    call $memory_getUsableSizeOfBlock
    local.get $blockSize
    i32.const 8
    i32.add
    i32.add
    local.set $blockSize
  end

  ;; check block after
  local.get $startPointer
  local.get $blockSize
  i32.add
  local.tee $temp

  memory.size ;; first make sure it's inside memory
  i32.const 16
  i32.shl
  i32.lt_u

  if
    ;; check if not used
    local.get $temp
    call $memory_isBlockUsed
    i32.eqz

    if
      ;; update size
      local.get $temp
      call $memory_getUsableSizeOfBlock
      local.get $blockSize
      i32.const 8
      i32.add
      i32.add
      local.set $blockSize
    end
  end

  ;; re-init block
  local.get $startPointer
  local.get $blockSize
  call $memory_markBlockSize
)

;; returns address of boundary word for first free block
(func $memory_findFreeBlock (export "findFree") (param $minimumBytes i32) (result i32)
  (local $memorySize i32)
  (local $currentBlock i32)

  ;; get memory size in bytes
  memory.size
  i32.const 16 ;; convert pages to bytes
  i32.shl
  local.set $memorySize

  ;; start 4 bytes in so we don't ever get a 0 address
  i32.const 4
  local.set $currentBlock

  block $exitBlock
    loop $blockLoop
      ;; make sure we're not past the end
      local.get $currentBlock
      local.get $memorySize
      i32.ge_u
      br_if $exitBlock

      ;; check if current block is used (result pushed to stack)
      local.get $currentBlock
      call $memory_isBlockUsed

      ;; check if current block is smaller than we need (result pushed to stack)
      local.get $currentBlock
      call $memory_getUsableSizeOfBlock
      local.get $minimumBytes
      i32.lt_u

      ;; if either is true
      i32.or
      if
        ;; move pointer
        local.get $currentBlock
        i32.load ;; get size
        i32.const -2 ;; mask least-significant bit
        i32.and
        local.get $currentBlock
        i32.add
        local.set $currentBlock

        ;; continue loop
        br $blockLoop
      end

      ;; block is free and big enough
      local.get $currentBlock
      return
    end
  end

  ;; reached the end of memory, cannot find a block
  i32.const 0
  return
)

;; checks to see if block at given address can be split into part of at least $minimumBytes
;; and splits if it is able
(func $memory_splitFreeBlock (export "splitFree") (param $boundaryTagAddress i32) (param $minimumBytes i32)
  (local $desiredSize i32)
  (local $oldBlockSize i32)
  (local $newBlockSize i32)

  ;; desiredSize = minimumBytes + tags
  local.get $minimumBytes
  i32.const 8
  i32.add
  local.set $desiredSize

  ;; oldBlockSize
  local.get $boundaryTagAddress
  i32.load
  i32.const -2
  i32.and
  local.set $oldBlockSize

  ;; newBlockSize (rounding up to nearest 16-byte chunk)
  local.get $desiredSize
  i32.const 15
  i32.add
  i32.const -16
  i32.and
  local.set $newBlockSize

  ;; mark new block
  local.get $boundaryTagAddress
  local.get $newBlockSize
  call $memory_markBlockSize

  ;; mark remaining if it exists
  local.get $newBlockSize
  local.get $oldBlockSize
  i32.lt_u
  if
    ;; address
    local.get $boundaryTagAddress
    local.get $newBlockSize
    i32.add

    ;; remaining size
    local.get $oldBlockSize
    local.get $newBlockSize
    i32.sub

    call $memory_markBlockSize
  end
)

;; marks a block as used
(func $memory_markBlockUsed (export "markUsed") (param $boundaryTagAddress i32)
  (local $blockSize i32)
  local.get $boundaryTagAddress
  i32.load
  i32.const -2
  i32.and
  local.set $blockSize

  local.get $boundaryTagAddress
  local.get $blockSize
  i32.const 1
  i32.or
  i32.store

  local.get $boundaryTagAddress
  local.get $blockSize
  i32.add
  i32.const 4
  i32.sub
  local.get $blockSize
  i32.const 1
  i32.or
  i32.store
)

;; sets boundary tags for unused block
(func $memory_markBlockSize (export "markSize") (param $boundaryTagAddress i32) (param $sizeWithTags i32)
  ;; put size at tag location
  local.get $boundaryTagAddress
  local.get $sizeWithTags
  i32.store

  ;; put size at tag + size - 4
  local.get $boundaryTagAddress
  local.get $sizeWithTags
  i32.add
  i32.const 4
  i32.sub
  local.get $sizeWithTags
  i32.store
)

;; check if block at given boundary tag address is used
(func $memory_isBlockUsed (export "isUsed") (param $boundaryTagAddress i32) (result i32)
  local.get $boundaryTagAddress
  i32.load
  i32.const 1
  i32.and
)

(func $memory_getUsableSizeOfBlock (export "getUsableSize") (param $boundaryTagAddress i32) (result i32)
  local.get $boundaryTagAddress
  i32.load
  i32.const -2
  i32.and
  i32.const 8
  i32.sub
)