1. 18 Jun, 2019 1 commit
    • Yorick Peterse's avatar
      Implement Inko's lexer in Inko itself · a518c120
      Yorick Peterse authored
      This adds std::compiler::lexer, which can be used to lex Inko source
      code into a sequence of tokens. These tokens in turn can be used to
      build an Abstract Syntax Tree.
      a518c120
  2. 17 Jun, 2019 2 commits
    • Yorick Peterse's avatar
      Fix rehashing of HashMap · feb8e42e
      Yorick Peterse authored
      The in-place rehashing approach was broken. Depending on the hash value
      of a pair, it could be placed in the wrong bucket. This commit fixes the
      problem by using a new Array for the buckets. This is less memory
      efficient, but:
      
      1. Correct
      2. Simpler
      
      Making the rehashing logic more memory efficient is something we may
      look into in the future.
      feb8e42e
    • Yorick Peterse's avatar
      6385da73
  3. 16 Jun, 2019 1 commit
    • Yorick Peterse's avatar
      Rework HashMap internals and add RNG support · 770bc946
      Yorick Peterse authored
      The internals of HashMap, and in particular the hashing logic, were
      broken. Internally the VM reused Rust's DefaultHasher type for hashing
      values. This type is mutable. When storing a HashMap in a constant,
      concurrent access to this HashMap could result in wrong hashes being
      produced, as all threads use the same DefaultHasher.
      
      To solve this, Inko takes a similar approach as Rust: we provide a
      RandomState type, which can be used to create a DefaultHasher. A
      DefaultHasher now takes two keys as arguments, used for seeding the
      hasher. The RandomState type generates two keys randomly, similar to
      Rust. The hash seeds are generated by taking a thread-local randomly
      generated number, then incrementing it (wrapping around on overflow).
      This ensures that it is very unlikely for two different HashMaps to use
      the same seeds, making certain hash attacks [1] more difficult.
      
      Random number generation is provided by the std::random module. This
      module provides methods for randomly generating integers, floats, and
      bytes. Integers and floats can also be generated in a given range, for
      example:
      
          import std::random
      
          random.integer_between(min: 0, max: 10)
      
      [1]: https://github.com/rust-lang/rust/issues/36481 and
           https://internals.rust-lang.org/t/help-harden-hashmap-in-libstd/4138/18
      770bc946
  4. 14 Jun, 2019 3 commits
  5. 30 May, 2019 1 commit
  6. 27 May, 2019 1 commit
  7. 26 May, 2019 7 commits
    • Yorick Peterse's avatar
      Add support for building the VM with jemalloc · e6aa5900
      Yorick Peterse authored
      Support for using jemalloc is hidden behind a feature flag that is
      disabled by default. To use it, one can build the VM like so:
      
          cargo build --release --features jemalloc
      
      Alternatively, one can use the Makefile vm/Makefile like so:
      
          make release FEATURES='jemalloc'
      e6aa5900
    • Yorick Peterse's avatar
      Require Rust 1.34 or newer · e5f31fcc
      Yorick Peterse authored
      The use of AtomicU16 requires Rust 1.34 or newer, as it's only available
      when using nightly Rust on older versions.
      e5f31fcc
    • Yorick Peterse's avatar
      Use AtomicU16 for Immix histograms · b513911a
      Yorick Peterse authored
      Now that this type is available in stable Rust we can use it for the
      Immix histograms, reducing memory usage of these histograms by up to
      four times. This is especially noticeable when spawning many processes.
      b513911a
    • Yorick Peterse's avatar
      Add ByteArray.slice · fc417e39
      Yorick Peterse authored
      Just like String.slice can be used to slice a String, ByteArray.slice
      can be used to slice a ByteArray.
      fc417e39
    • Yorick Peterse's avatar
      Remove support for setting compiler options · ded03aad
      Yorick Peterse authored
      Instead of exposing these through the syntax, we now determine the
      values of these options based on the module names. This allows us to
      achieve the exact same as before, without having to complicate the
      parser and compiler.
      ded03aad
    • Yorick Peterse's avatar
      Remove support for `object ... impl` syntax · 53ff6b02
      Yorick Peterse authored
      This removes support for the `object ... impl` syntax, in favour of just
      implementing traits separately.
      
      This fixes #166
      53ff6b02
    • Yorick Peterse's avatar
      Remove use of `object ... impl` syntax · 0b9ccdab
      Yorick Peterse authored
      As per #166 we will be removing
      support for the `object ... impl` syntax. In preparation for that, this
      commit updates the runtime code to no longer use this syntax.
      0b9ccdab
  8. 25 May, 2019 2 commits
    • Yorick Peterse's avatar
      Add Range.cover? · eddffb9f
      Yorick Peterse authored
      The method std::range::Range.cover? can be used to check if a Range
      includes a value, without having to evaluate all the values in the
      range.
      eddffb9f
    • Yorick Peterse's avatar
      Fix failing Clippy builds · 468a7044
      Yorick Peterse authored
      The latest version of Clippy detects some offenses it didn't catch
      previously. We also remove the "map_io!" macro as it is no longer
      necessary.
      468a7044
  9. 24 May, 2019 1 commit
    • Yorick Peterse's avatar
      Fix two use-after-free bugs regarding sockets · da7e3128
      Yorick Peterse authored
      This fixes two use-after-free bugs that could happen when a process was
      rescheduled immediately after being registered with the system poller.
      There were two separate bugs:
      
      1. Saving the instruction pointer after registering a process, which
         could lead to either the wrong instruction being retried, or a
         use-after-free bug.
      
      2. Setting the "registered" flag of a socket _after_ registering it.
         If a process was rescheduled fast enough, it might drop the socket
         before the "registered" flag could be written.
      
      Both these issues were uncovered using AddressSanitizer, but still took
      a few days to debug as the problem was not immediately clear. Due to the
      heavy use of references in the VM, we sadly can't take advantage of
      Rust's move semantics to guard ourselves against these problems. Some
      comments were added to clarify these issues, hopefully preventing them
      from happening again in the future.
      da7e3128
  10. 21 May, 2019 1 commit
    • Yorick Peterse's avatar
      Add Enumerator for writing iterators · 55473d46
      Yorick Peterse authored
      The new type std::iterator::Enumerator makes it much easier to write
      iterators and removes the need for having to define an object for every
      kind of iterator. We also add std::iterator.index_enumerator, which
      makes it easy to write an Enumerator/Iterator for a range based
      collection such as an Array.
      
      An alternative approach to making it easier to write iterators would be
      to use generators, backed by either a coroutine or a continuation.
      Unfortunately, both continuations and coroutines come with various
      drawbacks that make them unappealing for Inko. Both require invasive and
      extensive changes to the VM, as well as parser and compiler changes.
      Worse, there's no real use case for both outside of generators, which
      makes it feel redundant to add continuations and/or coroutines.
      
      Introducing the Enumerator type removes the need for adding more VM
      instructions and complexity, at the cost of writing iterators requiring
      a little bit more work compared to using generators.
      
      Fixes #146
      55473d46
  11. 15 May, 2019 2 commits
  12. 14 May, 2019 1 commit
    • Yorick Peterse's avatar
      Refactor connecting of sockets · 53675b7a
      Yorick Peterse authored
      This commit makes the following changes:
      
      1. We remove the InProgress constant from the VM.
      
      2. When we detect EISCONN as the result of a connect(2), we ignore it.
      
      3. We properly read SO_ERROR from a socket when connecting in order to
         determine the actual result of connect(2).
      
      4. We fix cloning of registered sockets.
      
      == Removal of InProgress
      
      Using the InProgress variant meant that the result register of
      SocketConnect would not be set when a connect is in progress. This could
      lead to unexpected results if one were to assume it was actually set.
      
      == Using SO_ERROR
      
      Socket::connect() in the VM now checks the value of SO_ERROR when a
      connect(2) is reported as blocking. On at least Windows, the result of
      connect(2) always appears to be EAGAIN/WSAEWOULDBLOCK, with the actual
      error being stored in SO_ERROR. Not checking this value could result in
      a connect getting stuck in the loop of: performing the connect ->
      reported as blocking -> retrying later on -> repeat.
      
      == Socket cloning
      
      We also fix the cloning of sockets to make sure that the "registered"
      flag is not cloned, as doing this could lead to errors when trying to
      register a socket with a network poller.
      53675b7a
  13. 11 May, 2019 4 commits
    • Yorick Peterse's avatar
      Release v0.4.0 · 0631b684
      Yorick Peterse authored
      0631b684
    • Yorick Peterse's avatar
      Fix non-blocking socket reads · 2fb8e93f
      Yorick Peterse authored
      Prior to this commit, if a read size was given we would use Rust's Take
      trait to read up to N bytes from a socket. Unfortunately, sockets don't
      produce an EOF until they are closed, which meant the read would
      continue indefinitely. To work around this we use the same buffering
      logic as is used by our recv_from implementation.
      2fb8e93f
    • Yorick Peterse's avatar
      Turn accepted sockets into non-blocking sockets · 0393df5b
      Yorick Peterse authored
      When a socket is produced using accept(), it does not inherit the
      non-blocking status from the listener. This would cause socket
      operations using such a socket to block.
      0393df5b
    • Yorick Peterse's avatar
      Added support for shutting down sockets · f9131174
      Yorick Peterse authored
      This is necessary to gracefully terminate STREAM sockets, as otherwise
      clients may produce "Connection reset by peer" errors.
      f9131174
  14. 10 May, 2019 2 commits
  15. 09 May, 2019 1 commit
    • Yorick Peterse's avatar
      Added support for non-blocking network IO · 3974f47c
      Yorick Peterse authored
      This adds support for performing non-blocking network operations, such
      as reading and writing to/from a socket. The runtime API exposed is
      similar to Erlang, allowing one to write code that uses non-blocking
      APIs without having to resort to using callbacks. For example, in a
      typicall callback based language you may write the following to read
      from a socket:
      
          socket.create do (socket) {
            socket.read do (data) {
      
            }
          }
      
      In Inko, you instead would (more or less) write the following:
      
          import std::net::socket::TcpStream
      
          let socket = try! TcpStream.new(ip: '192.0.2.0', port: 80)
          let message = try! socket.read_string(size: 4)
      
      The VM then takes care of using the appropriate non-blocking operations,
      and will reschedule processes whenever necessary.
      
      This functionality is exposed through the following runtime modules:
      
      * std::net::ip: used for parsing IPv4 and IPv6 addresses.
      * std::net::socket: used for TCP and UDP sockets.
      * std::net::unix: used for Unix domain sockets.
      
      The VM uses the system's native polling mechanism to determine when a
      file descriptor is available for a read or write. On Linux we use epoll,
      while using kqueue for the various BSDs and Mac OS. For Windows we use
      wepoll (https://github.com/piscisaureus/wepoll). Wepoll exposes an API
      that is compatible with the epoll API, but uses Windows IO completion
      ports under the hoods.
      
      When a process attempts to perform a non-blocking operation, the process
      is registered (combined with the file descriptor to poll) in a global
      poller and suspended. When the file descriptor becomes available for a
      read or write, the corresponding process is rescheduled. The polling
      mechanism is set up in such a way that a process can not be rescheduled
      multiple times at once.
      
      We do not use MIO (https://github.com/tokio-rs/mio), instead we use
      epoll, kqueue, and wepoll (using
      https://crates.io/crates/wepoll-binding) directly. At the time of
      writing, while MIO offers some form of support for Windows it comes with
      various issues:
      
      1. https://github.com/tokio-rs/mio/issues/921
      2. https://github.com/tokio-rs/mio/issues/919
      3. https://github.com/tokio-rs/mio/issues/776
      4. https://github.com/tokio-rs/mio/issues/913
      
      It's not clear when these issues would be addressed, as the maintainers
      of MIO appear to not have the experience and resources to resolve them
      themselves. MIO is part of the Google Summer of Code 2019, with the goal
      of improving Windows support. Unfortunately, this likely won't be done
      before the end of 2019, and we don't want to wait that long.
      
      Another issue with MIO is its implementation. Internally, MIO uses
      various forms of synchronisation which can make it expensive to use a
      single poller across multiple threads; it certainly is not a zero-cost
      library. It also offers more than we need, such as being able to poll
      arbitrary objects.
      
      We are not the first to run into these issues. For example, the Amethyst
      video game engine also ran into issues with MIO as detailed in
      https://community.amethyst.rs/t/sorting-through-the-mio-mess/561.
      
      With all of this in mind, I decided it was not worth the time to wait
      for MIO to get fixed, and to instead spend time directly using epoll,
      kqueue, and wepoll. This gives us total control over the code, and
      allows us to implement what we need in the way we need it. Most
      important of all: it works on Linux, BSD, Mac, and Windows.
      3974f47c
  16. 28 Mar, 2019 5 commits
    • Yorick Peterse's avatar
      Removed use of "extern crate" · 99c9f044
      Yorick Peterse authored
      This is no longer required in Rust 2018.
      99c9f044
    • Yorick Peterse's avatar
      Use Rust 2018 for the VM · 5ca5a292
      Yorick Peterse authored
      5ca5a292
    • Yorick Peterse's avatar
      Removed unused code from the compiler · e9331a77
      Yorick Peterse authored
      e9331a77
    • Yorick Peterse's avatar
      Reduce Immix block size to 8 KB · ff6297fd
      Yorick Peterse authored
      A block size of 8 KB reduces memory usage when running many processes,
      at the cost of a tiny increase in garbage collection timings. This
      increase is likely something we can optimise in the future. Reducing the
      block size also appears to speed up the test suite by 5-10 milliseconds.
      
      Fixes #159
      ff6297fd
    • Yorick Peterse's avatar
      Remove PIDs from processes · 11ee161e
      Yorick Peterse authored
      This removes the use of PIDs for processes in favour of using proper
      process objects. This means we no longer need to allocate PIDs. This
      allows us to spawn processes without having to obtain a lock on a global
      process table.
      
      The removal of PIDs means that sending messages feels a bit nicer now.
      Instead of writing this:
      
          import std::process
      
          let pid = process.spawn {}
      
          process.send(pid: pid, message: 'hello')
      
      You now write this instead:
      
          import std::process
      
          let proc = process.spawn {}
      
          proc.send('hello')
      
      We also remove the `std::process.channel` method and associated types.
      This API was not very pleasant to use, and was not very efficient
      either. We hope to (re-)introduce a better type-safe API for message
      passing in the future, if possible.
      
      Fixes #161
      11ee161e
  17. 26 Mar, 2019 1 commit
    • Yorick Peterse's avatar
      Refactor the global allocator and block sizes · c7c0befb
      Yorick Peterse authored
      This refactors the global allocator so that it doesn't require on
      explicit locking as much, and changes various parts of Immix blocks (and
      tests) to no longer rely directly on the block size. This makes it a bit
      easier to adjust the block size in the future, without having to fix
      various tests.
      c7c0befb
  18. 20 Mar, 2019 1 commit
    • Yorick Peterse's avatar
      Fix storing module methods in globals · bd3465a0
      Yorick Peterse authored
      Due to the use of an incorrect scope object, the compiler would use -1
      as the index for methods stored in module globals. Due to overflowing
      this would result in the VM allocating memory for 65 535 globals,
      resulting in at least 512 KB of memory being used for every module that
      defined a module method. Worse, if a module were to use these methods
      the VM might end up executing the wrong method due to all of them using
      the same slot.
      bd3465a0
  19. 19 Mar, 2019 3 commits