hroi / treebitmap Goto Github PK
View Code? Open in Web Editor NEWFast IP lookup table for IPv4/IPv6 prefixes
License: MIT License
Fast IP lookup table for IPv4/IPv6 prefixes
License: MIT License
If a tree node holds some mutable structure (like HashMap) it's desirable to modify it inline without removing, modifying and inserting it back.
The use of mem::zeroed
at
treebitmap/src/tree_bitmap/allocator.rs
Line 195 in 9540ae5
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
.
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... (:-)
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.
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.
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()
To make IpLookupTable
Send
.
I believe RawVec
from alloc
is Send
. Any reason our implementation should not be?
(When T
is Send
, of course.)
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);
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!) :)
When running insert multiple times it results in a exit-code 3221226356.
I assume this has something to do with unsafe code?
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
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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.