From 3c6471ed8174b870f8d463e8f39a781f8c731471 Mon Sep 17 00:00:00 2001 From: Jordan Bracco Date: Fri, 12 Nov 2021 00:15:31 +0100 Subject: initial commit --- .formatter.exs | 4 ++ .gitignore | 26 ++++++++ README.md | 21 +++++++ lib/tree_bitmap.ex | 18 ++++++ lib/tree_bitmap/nif.ex | 10 +++ mix.exs | 25 ++++++++ mix.lock | 5 ++ native/treebitmap_nif/.cargo/config | 12 ++++ native/treebitmap_nif/.gitignore | 1 + native/treebitmap_nif/Cargo.lock | 120 ++++++++++++++++++++++++++++++++++++ native/treebitmap_nif/Cargo.toml | 14 +++++ native/treebitmap_nif/README.md | 20 ++++++ native/treebitmap_nif/src/lib.rs | 107 ++++++++++++++++++++++++++++++++ priv/native/libtreebitmap_nif.so | Bin 0 -> 903892 bytes test/test_helper.exs | 1 + test/tree_bitmap_test.exs | 67 ++++++++++++++++++++ 16 files changed, 451 insertions(+) create mode 100644 .formatter.exs create mode 100644 .gitignore create mode 100644 README.md create mode 100644 lib/tree_bitmap.ex create mode 100644 lib/tree_bitmap/nif.ex create mode 100644 mix.exs create mode 100644 mix.lock create mode 100644 native/treebitmap_nif/.cargo/config create mode 100644 native/treebitmap_nif/.gitignore create mode 100644 native/treebitmap_nif/Cargo.lock create mode 100644 native/treebitmap_nif/Cargo.toml create mode 100644 native/treebitmap_nif/README.md create mode 100644 native/treebitmap_nif/src/lib.rs create mode 100755 priv/native/libtreebitmap_nif.so create mode 100644 test/test_helper.exs create mode 100644 test/tree_bitmap_test.exs diff --git a/.formatter.exs b/.formatter.exs new file mode 100644 index 0000000..d2cda26 --- /dev/null +++ b/.formatter.exs @@ -0,0 +1,4 @@ +# Used by "mix format" +[ + inputs: ["{mix,.formatter}.exs", "{config,lib,test}/**/*.{ex,exs}"] +] diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..0347882 --- /dev/null +++ b/.gitignore @@ -0,0 +1,26 @@ +# The directory Mix will write compiled artifacts to. +/_build/ + +# If you run "mix test --cover", coverage assets end up here. +/cover/ + +# The directory Mix downloads your dependencies sources to. +/deps/ + +# Where third-party dependencies like ExDoc output generated docs. +/doc/ + +# Ignore .fetch files in case you like to edit your project deps locally. +/.fetch + +# If the VM crashes, it generates a dump, let's ignore it too. +erl_crash.dump + +# Also ignore archive artifacts (built via "mix archive.build"). +*.ez + +# Ignore package tarball (built via "mix hex.build"). +tree_bitmap-*.tar + +# Temporary files, for example, from tests. +/tmp/ diff --git a/README.md b/README.md new file mode 100644 index 0000000..c175b02 --- /dev/null +++ b/README.md @@ -0,0 +1,21 @@ +# TreeBitmap + +**TODO: Add description** + +## Installation + +If [available in Hex](https://hex.pm/docs/publish), the package can be installed +by adding `tree_bitmap` to your list of dependencies in `mix.exs`: + +```elixir +def deps do + [ + {:tree_bitmap, "~> 0.1.0"} + ] +end +``` + +Documentation can be generated with [ExDoc](https://github.com/elixir-lang/ex_doc) +and published on [HexDocs](https://hexdocs.pm). Once published, the docs can +be found at [https://hexdocs.pm/tree_bitmap](https://hexdocs.pm/tree_bitmap). + diff --git a/lib/tree_bitmap.ex b/lib/tree_bitmap.ex new file mode 100644 index 0000000..6d1bc07 --- /dev/null +++ b/lib/tree_bitmap.ex @@ -0,0 +1,18 @@ +defmodule TreeBitmap do + @moduledoc """ + Documentation for `TreeBitmap`. + """ + + @doc """ + Hello world. + + ## Examples + + iex> TreeBitmap.hello() + :world + + """ + def hello do + :world + end +end diff --git a/lib/tree_bitmap/nif.ex b/lib/tree_bitmap/nif.ex new file mode 100644 index 0000000..740dbdf --- /dev/null +++ b/lib/tree_bitmap/nif.ex @@ -0,0 +1,10 @@ +defmodule TreeBitmap.NIF do + use Rustler, otp_app: :tree_bitmap, crate: "treebitmap_nif" + + def new(), do: :erlang.nif_error(:nif_not_loaded) + def length(_), do: :erlang.nif_error(:nif_not_loaded) + def add(_, _, _, _), do: :erlang.nif_error(:nif_not_loaded) + def lookup(_, _), do: :erlang.nif_error(:nif_not_loaded) + def remove(_, _, _), do: :erlang.nif_error(:nif_not_loaded) + +end diff --git a/mix.exs b/mix.exs new file mode 100644 index 0000000..a6b344d --- /dev/null +++ b/mix.exs @@ -0,0 +1,25 @@ +defmodule TreeBitmap.MixProject do + use Mix.Project + + def project do + [ + app: :tree_bitmap, + version: "0.1.0", + elixir: "~> 1.12-rc", + start_permanent: Mix.env() == :prod, + deps: deps() + ] + end + + def application do + [ + extra_applications: [:logger] + ] + end + + defp deps do + [ + {:rustler, "~> 0.22.2"} + ] + end +end diff --git a/mix.lock b/mix.lock new file mode 100644 index 0000000..f47b7a1 --- /dev/null +++ b/mix.lock @@ -0,0 +1,5 @@ +%{ + "jason": {:hex, :jason, "1.2.2", "ba43e3f2709fd1aa1dce90aaabfd039d000469c05c56f0b8e31978e03fa39052", [:mix], [{:decimal, "~> 1.0 or ~> 2.0", [hex: :decimal, repo: "hexpm", optional: true]}], "hexpm", "18a228f5f0058ee183f29f9eae0805c6e59d61c3b006760668d8d18ff0d12179"}, + "rustler": {:hex, :rustler, "0.22.2", "f92d6dba71bef6fe5f0d955649cb071127adc92f32a78890e8fa9939e59a1b41", [:mix], [{:jason, "~> 1.2", [hex: :jason, repo: "hexpm", optional: false]}, {:toml, "~> 0.5.2", [hex: :toml, repo: "hexpm", optional: false]}], "hexpm", "56b129141e86d60a2d670af9a2b55a9071e10933ef593034565af77e84655118"}, + "toml": {:hex, :toml, "0.5.2", "e471388a8726d1ce51a6b32f864b8228a1eb8edc907a0edf2bb50eab9321b526", [:mix], [], "hexpm", "f1e3dabef71fb510d015fad18c0e05e7c57281001141504c6b69d94e99750a07"}, +} diff --git a/native/treebitmap_nif/.cargo/config b/native/treebitmap_nif/.cargo/config new file mode 100644 index 0000000..1cb1d94 --- /dev/null +++ b/native/treebitmap_nif/.cargo/config @@ -0,0 +1,12 @@ +[target.x86_64-apple-darwin] +rustflags = [ + "-C", "link-arg=-undefined", + "-C", "link-arg=dynamic_lookup", +] + +[target.aarch64-apple-darwin] +rustflags = [ + "-C", "link-arg=-undefined", + "-C", "link-arg=dynamic_lookup", +] + diff --git a/native/treebitmap_nif/.gitignore b/native/treebitmap_nif/.gitignore new file mode 100644 index 0000000..ea8c4bf --- /dev/null +++ b/native/treebitmap_nif/.gitignore @@ -0,0 +1 @@ +/target diff --git a/native/treebitmap_nif/Cargo.lock b/native/treebitmap_nif/Cargo.lock new file mode 100644 index 0000000..c181954 --- /dev/null +++ b/native/treebitmap_nif/Cargo.lock @@ -0,0 +1,120 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "heck" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6d621efb26863f0e9924c6ac577e8275e5e6b77455db64ffa6c65c904e9e132c" +dependencies = [ + "unicode-segmentation", +] + +[[package]] +name = "lazy_static" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" + +[[package]] +name = "proc-macro2" +version = "1.0.27" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f0d8caf72986c1a598726adc988bb5984792ef84f5ee5aa50209145ee8077038" +dependencies = [ + "unicode-xid", +] + +[[package]] +name = "quote" +version = "1.0.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c3d0b9745dc2debf507c8422de05d7226cc1f0644216dfdfead988f9b1ab32a7" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rustler" +version = "0.22.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b787d3b2a80007f41cd4c0c310cdeb3936192768159585f65ecc7e96faf97fc3" +dependencies = [ + "lazy_static", + "rustler_codegen", + "rustler_sys", +] + +[[package]] +name = "rustler_codegen" +version = "0.22.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b5a1f867002b6f0130f47abf215cac4405646db6f5d7b009b21c890980490aa4" +dependencies = [ + "heck", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "rustler_sys" +version = "2.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1cb382fde4f421c51555919e9920b058c0286f6bf59e53d02eb4d281eae6758b" +dependencies = [ + "unreachable", +] + +[[package]] +name = "syn" +version = "1.0.73" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f71489ff30030d2ae598524f61326b902466f72a0fb1a8564c001cc63425bcc7" +dependencies = [ + "proc-macro2", + "quote", + "unicode-xid", +] + +[[package]] +name = "treebitmap" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6bf423939ac9ccf4083788879b883a7149176586f9cf8b0fb1fd88b66ad692b5" + +[[package]] +name = "treebitmap_nif" +version = "0.1.0" +dependencies = [ + "rustler", + "treebitmap", +] + +[[package]] +name = "unicode-segmentation" +version = "1.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8895849a949e7845e06bd6dc1aa51731a103c42707010a5b591c0038fb73385b" + +[[package]] +name = "unicode-xid" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8ccb82d61f80a663efe1f787a51b16b5a51e3314d6ac365b08639f52387b33f3" + +[[package]] +name = "unreachable" +version = "1.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "382810877fe448991dfc7f0dd6e3ae5d58088fd0ea5e35189655f84e6814fa56" +dependencies = [ + "void", +] + +[[package]] +name = "void" +version = "1.0.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6a02e4885ed3bc0f2de90ea6dd45ebcbb66dacffe03547fadbb0eeae2770887d" diff --git a/native/treebitmap_nif/Cargo.toml b/native/treebitmap_nif/Cargo.toml new file mode 100644 index 0000000..0c14233 --- /dev/null +++ b/native/treebitmap_nif/Cargo.toml @@ -0,0 +1,14 @@ +[package] +name = "treebitmap_nif" +version = "0.1.0" +authors = [] +edition = "2018" + +[lib] +name = "treebitmap_nif" +path = "src/lib.rs" +crate-type = ["cdylib"] + +[dependencies] +rustler = "0.22.0" +treebitmap = "0.4.0" diff --git a/native/treebitmap_nif/README.md b/native/treebitmap_nif/README.md new file mode 100644 index 0000000..67e961c --- /dev/null +++ b/native/treebitmap_nif/README.md @@ -0,0 +1,20 @@ +# NIF for Elixir.TreeBitmap.NIF + +## To build the NIF module: + +- Your NIF will now build along with your project. + +## To load the NIF: + +```elixir +defmodule TreeBitmap.NIF do + use Rustler, otp_app: :tree_bitmap, crate: "treebitmap_nif" + + # When your NIF is loaded, it will override this function. + def add(_a, _b), do: :erlang.nif_error(:nif_not_loaded) +end +``` + +## Examples + +[This](https://github.com/hansihe/NifIo) is a complete example of a NIF written in Rust. diff --git a/native/treebitmap_nif/src/lib.rs b/native/treebitmap_nif/src/lib.rs new file mode 100644 index 0000000..7ff0a90 --- /dev/null +++ b/native/treebitmap_nif/src/lib.rs @@ -0,0 +1,107 @@ +use std::sync::Mutex; +use rustler::{resource::ResourceArc, NifResult, NifRecord, Encoder, Env, Term, types::atom::Atom, types::tuple::make_tuple}; +//use std::net::Ipv6Addr; +use std::net::{Ipv4Addr}; +use treebitmap::{IpLookupTable}; + +struct TableResource { + pub table: Mutex> +} + +mod atoms { + rustler::atoms! { + ok, + nil, + error + } +} + +enum AddrTuple { + V4(TupleV4), + V6(TupleV6) +} + +#[derive(Debug, NifRecord)] +#[tag = "inet4"] +struct TupleV4 { + pub a: u8, + pub b: u8, + pub c: u8, + pub d: u8 +} + +#[derive(Debug, NifRecord)] +#[tag = "inet6"] +struct TupleV6 { + pub a1: u16, + pub a2: u16, + pub a3: u16, + pub a4: u16, + pub a5: u16, + pub a6: u16, + pub a7: u16, + pub a8: u16 +} + +#[rustler::nif] +fn new() -> NifResult> { + let table = IpLookupTable::new(); + let resource = ResourceArc::new(TableResource { + table: Mutex::new(table) + }); + Ok(resource) +} + +#[rustler::nif] +fn length(table_resource: ResourceArc) -> NifResult { + let table = table_resource.table.lock().unwrap(); + Ok(table.len()) +} + +#[rustler::nif] +fn add( + table_resource: ResourceArc, + ipv4: TupleV4, + masklen: u32, + value: u32 +) -> NifResult{ + let mut table = table_resource.table.lock().unwrap(); + let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); + table.insert(addr, masklen, value); + Ok(atoms::ok()) +} + +#[rustler::nif] +fn remove( + table_resource: ResourceArc, + ipv4: TupleV4, + masklen: u32 +) -> NifResult{ + let mut table = table_resource.table.lock().unwrap(); + let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); + table.remove(addr, masklen); + Ok(atoms::ok()) +} + +#[rustler::nif] +fn lookup<'a>( + env: rustler::Env<'a>, + table_resource: ResourceArc, + ipv4: TupleV4 +) -> Term { + let table = table_resource.table.lock().unwrap(); + let addr = Ipv4Addr::new(ipv4.a, ipv4.b, ipv4.c, ipv4.d); + if let Some((prefix, prefixlen, value)) = table.longest_match(addr) { + let addr = prefix.octets(); + make_tuple(env, &[atoms::ok().encode(env), addr.encode(env), prefixlen.encode(env), value.encode(env)]) + } else { + make_tuple(env, &[atoms::ok().encode(env), atoms::nil().encode(env)]) + } +} + +rustler::init!("Elixir.TreeBitmap.NIF", [new, length, add, remove, lookup], load = on_load); + +fn on_load(env: Env, _info: Term) -> bool { + rustler::resource!(TableResource, env); + true +} diff --git a/priv/native/libtreebitmap_nif.so b/priv/native/libtreebitmap_nif.so new file mode 100755 index 0000000..729cdbe Binary files /dev/null and b/priv/native/libtreebitmap_nif.so differ diff --git a/test/test_helper.exs b/test/test_helper.exs new file mode 100644 index 0000000..869559e --- /dev/null +++ b/test/test_helper.exs @@ -0,0 +1 @@ +ExUnit.start() diff --git a/test/tree_bitmap_test.exs b/test/tree_bitmap_test.exs new file mode 100644 index 0000000..ff1359f --- /dev/null +++ b/test/tree_bitmap_test.exs @@ -0,0 +1,67 @@ +defmodule TreeBitmapTest do + use ExUnit.Case + doctest TreeBitmap + alias TreeBitmap.NIF + + test "new/0" do + table = NIF.new() + assert is_reference(table) + end + + test "length/1" do + table = NIF.new() + assert 0 == NIF.length(table) + end + + test "add/4 and lookup/2" do + table = NIF.new() + assert :ok == NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {:ok, _, 24, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + assert {:ok, nil} = NIF.lookup(table, {:inet4, 1, 1, 1, 1}) + end + + test "remove/2" do + table = NIF.new() + assert :ok == NIF.add(table, {:inet4, 192, 168, 1, 0}, 24, 0) + assert {:ok, _, 24, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + assert :ok == NIF.remove(table, {:inet4, 192, 168, 1, 0}, 24) + assert {:ok, nil} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + end + + test "default route" do + table = NIF.new() + assert :ok == NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + assert {:ok, _, 0, 0} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + end + + test "more to less specific" do + table = NIF.new() + :ok = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) + :ok = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) + :ok = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + assert {:ok, _, _, 0} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 2} = NIF.lookup(table, {:inet4, 10, 69, 1, 2}) + assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 10, 69, 2, 2}) + end + + test "less to more specific" do + table = NIF.new() + :ok = NIF.add(table, {:inet4, 0, 0, 0, 0}, 0, 0) + :ok = NIF.add(table, {:inet4, 10, 69, 0, 0}, 16, 1) + :ok = NIF.add(table, {:inet4, 10, 69, 1, 0}, 24, 2) + assert {:ok, _, _, 0} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 2} = NIF.lookup(table, {:inet4, 10, 69, 1, 2}) + assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 10, 69, 2, 2}) + end + + test "multiple routes" do + table = NIF.new() + :ok = NIF.add(table, {:inet4, 8, 8, 8, 0}, 24, 8) + :ok = NIF.add(table, {:inet4, 1, 1, 0, 0}, 16, 1) + :ok = NIF.add(table, {:inet4, 192, 168, 1, 1}, 32, 200) + assert {:ok, _, _, 8} = NIF.lookup(table, {:inet4, 8, 8, 8, 8}) + assert {:ok, _, _, 1} = NIF.lookup(table, {:inet4, 1, 1, 0, 0}) + assert {:ok, _, _, 200} = NIF.lookup(table, {:inet4, 192, 168, 1, 1}) + end + +end -- cgit v1.2.3