hroi/treebitmap

Fast IP lookup table for IPv4/IPv6 prefixes

treebitmap's Issues

Mark `RawVec` as `Send`?

To make IpLookupTable Send.

I believe RawVec from alloc is Send. Any reason our implementation should not be?

(When T is Send, of course.)

Stride optimization

The treebitmap is currently fixed-stride, 4 bits. Better compression can be achieved by a well-chosen variable-length stride.
The Tree-Bitmap paper suggests 13-4-4-4-4-3 as a good choice for IPv4.
A good stride pattern for IPv6 needs to be researched.

Option to combine Ipv4Addr and Ipv6Addr into a single IpAddr table.

Often, it would be nice to not have to decompose IpAddr into Ipv4Addr or Ipv6Addr and carry around two separate tables:

let mut v4_ifs = treebitmap::IpLookupTable::new();
let mut v6_ifs = treebitmap::IpLookupTable::new();

match ip {
    IpAddr::V4(ip4) => v4_ifs.insert(ip4, plen.into(), intf),
    IpAddr::V6(ip6) => v6_ifs.insert(ip6, plen.into(), intf),
};

Currently, this is required because of the type definitions of treebitmap:

treebitmap::IpLookupTable<Ipv4Addr, IfState>
treebitmap::IpLookupTable<Ipv6Addr, IfState>

But if instead, the tree definition was:

treebitmap::IpLookupTable<IpAddr, IfState>

We could use the same table for both where they can happily co-exist.

Consider making the Address trait publically accessible

The Address trait is public but it's in a private module, so it can't be used from outside the crate. This limits IpLookupTable to only working with Ipv4Addr or Ipv6Addr, and it also prevents using the Address trait as a constraint. Additionally, the address trait does not constrain the struct data type; this is more a matter of style. This means I can construct an instance of IpLookupTable but never be able to use any methods on it...

For example, I'm working with several address-like objects that are byte-compatible with Ipv4Addr, but implement a different trait. I can't make my trait different trait 'depend on' Address (trait MyTrait: Address). Nor can I wrap IpLookupTable in a generic struct which works with either Ipv4 or Ipv6 addresses.

Please consider this change. It's two lines... (:-)

do we have java version

Save/Cache a tree for reuse?

It takes a few seconds to insert a ~5 million ips. But i know these ips at compile time and they will not change. Would/could it be possible to avoid doing 5 million inserts and somehow load the tree from a file for example?

(I'm new to rust. No idea what's possible or not!) :)

Doesn't work with stable due to feature flags `alloc` and `test`

Due to the use of the alloc and test feature flags, treebitmap only works on nightly. I think the parts of the test suite that rely on unstable features could simple be made optional, and having those parts run only on builds using the nightly compiler. I'll try to come up with a PR to achieve that.

I still have to research on how would one avoid the use of the alloc feature flag on stable Rust.

Provide mutable versions of exact_match and longest_match

If a tree node holds some mutable structure (like HashMap) it's desirable to modify it inline without removing, modifying and inserting it back.

Useless lifetime

See rust-lang/rust#42467

Illegal use of mem::zeroed()

The use of mem::zeroed at

treebitmap/src/tree_bitmap/allocator.rs

Line 195 in 9540ae5

mem::zeroed(),

looks illegal: mem::zeroed may only be used for types that actually allow zero-initialization, and here this is done for any user-controlled type T. So, e.g. if T is a reference, this is UB as references must not be all-zero.

If you just want to write a bunch of zero bytes to memory, I suggest using write_bytes.

Insert errors with code 3221226356

Description

When running insert multiple times it results in a exit-code 3221226356.

I assume this has something to do with unsafe code?

insert() asserts when host portion non-zero

Hitting this assert when adding a interface address/prefix length into a table. I didn't zero out the host portion of the address before trying to insert it and it crashed.

I think it would be better if insert() returned None in this case. Or maybe insert() should return a Result with a value or an error?

thread 'insert_assert' panicked at 'assertion failed: ret > 0', src/tree_bitmap/node.rs:66:5

This test reproduces the assert:

#[test]
fn insert_assert() {
    let mut tbm = IpLookupTable::new();
    let ip1 = Ipv4Addr::from_str("10.255.71.185").unwrap();
    tbm.insert(ip1, 22, 1);

Panic on remove()

I'm getting an occasional panic using this library on calling IpLookupTable.remove(). Panic location is below:

thread '<unnamed>' panicked at 'index out of bounds: the len is 0 but the index is 0', /cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.4.0/src/tree_bitmap/mod.rs:297:22

The Rust binary in question is processing a couple hundred full BGP feeds but the list of prefixes which trigger the panic is suspiciously small... 49.255.11.17/32 is by far the most frequent culprit. It doesn't seem to happen every time and I have yet to be able to reliably reproduce it in a simple example. All the prefixes that trigger the crashes are /32 IPv4 prefixes.

I added some debug logging and something looks odd. I started logging whenever I insert that prefix so I know it's been seen. Immediately before the panic I dump the table to a file and the prefix exists, however if I try to lookup the prefix using either exact_match() or longest_match() I get a None back..

I realise this is probably tricky to troubleshoot without a reliable reproduction, but any tips on where I can start looking? I tried a build with this line changed to an assert!() but it still gets past that, so something seems to be happening in remove_child()

Removing nodes sometimes resulsts in a crash

Hi,

I'm still trying to get more details but this code:

extern crate treebitmap;

use std::net::Ipv4Addr;

use treebitmap::IpLookupTable;

fn main() {
    let mut table: IpLookupTable<Ipv4Addr, ()> = IpLookupTable::new();

    println!("len: {}", table.len());

    table.insert("2.93.185.24".parse().unwrap(), 32, ());
    table.insert("2.93.200.133".parse().unwrap(), 32, ());

    println!("len: {}", table.len());

    table.remove("2.93.185.24".parse().unwrap(), 32);
    table.remove("2.93.200.133".parse().unwrap(), 32);

    println!("len: {}", table.len());
}

results in a crash:

$  cargo build
   Compiling test v0.1.0 (file:///tmp/test)
    Finished dev [unoptimized + debuginfo] target(s) in 0.26s
$ RUST_BACKTRACE=1 ./target/debug/test 
len: 0
len: 2
thread 'main' panicked at 'tried to free non-empty collection', /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/allocator.rs:334:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:511
   5: std::panicking::begin_panic
             at /checkout/src/libstd/panicking.rs:445
   6: <treebitmap::tree_bitmap::allocator::Allocator<T>>::free
             at ./<panic macros>:3
   7: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove_child
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:324
   8: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove_child
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:317
   9: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove_child
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:317
  10: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove_child
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:317
  11: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove_child
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:317
  12: <treebitmap::tree_bitmap::TreeBitmap<T>>::remove
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/tree_bitmap/mod.rs:288
  13: <treebitmap::IpLookupTable<A, T>>::remove
             at /home/consus/.cargo/registry/src/github.com-1ecc6299db9ec823/treebitmap-0.3.1/src/lib.rs:108
  14: test::main
             at src/main.rs:17
  15: std::rt::lang_start::{{closure}}
             at /checkout/src/libstd/rt.rs:74
  16: std::panicking::try::do_call
             at libstd/rt.rs:59
             at libstd/panicking.rs:310
  17: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:105
  18: std::rt::lang_start_internal
             at libstd/panicking.rs:289
             at libstd/panic.rs:392
             at libstd/rt.rs:58
  19: std::rt::lang_start
             at /checkout/src/libstd/rt.rs:74
  20: main
  21: __libc_start_main
  22: _start