Date | Commit message (Collapse) |
|
When parsing network masks, we forget to update the length of
the IP address before scanning it for ':' to detect if an
address is IPv6 or not. This caused memchr to falsely detect
':' past the end of string (but not the allocated array) if the
stack had a dirty ':' leftover.
Falsely detecting ':' leads to AF_INET6 being passed to
inet_pton() on some AF_INET (IPv4) addresses, causing
a failure.
Fortunately this bug could not cause a segfault or bus error
(and thus went undetected by valgrind). The code was always
accessing memory within the stack allocated in the "save" array
of INET6_ADDRSTRLEN bytes.
|
|
* IPv6 support: Patricia.new(:AF_INET6)
* minor internal cleanups and speedups
|
|
Most of the recent code (and therefore, bugs) are my fault :)
|
|
This avoids compiler warnings.
|
|
|
|
Ruby won't do anything with it, but it avoids a compiler
warning.
|
|
We need to ensure IPv4-mapped-IPv6 addresses work.
|
|
Ruby strings may contain embedded null bytes that
could create false positives. Also, in Ruby 1.9, Ruby
strings may not be null-terminated internally, StringValueCStr
ensures null-termination upon export.
|
|
This way we're less inclined to ignore warnings that may
point to real problems.
|
|
New_Prefix2 takes a second argument which allows us to
use a static or stack variable to avoid hitting the heap.
This results in speedups for places where we previously
allocated and freed a prefix:
--------------------------- 8< ------------------------
require "rpatricia"
require "benchmark"
nr = 1000000
addr = "127.1.1.1"
p = Patricia.new
p.add "127.0.0.0/8"
res = Benchmark.measure do
nr.times { p.include?(addr) }
end
p res
--------------------------- 8< ------------------------
user system total real
before 0.470000 0.000000 0.470000 ( 0.467902)
after 0.330000 0.000000 0.330000 ( 0.328538)
|
|
Hitting assertions in C code is bad user-experience, raise in
Ruby-land before this happens.
|
|
IPv4 is still the default and will likely remain so
indefinitely.
|
|
We have the INET6_ADDRSTRLEN constant to help us determine
the proper length.
|
|
getaddrinfo will happily parse IPv6 or IPv4 addresses
with AI_NUMERICHOST.
|
|
prefix_toa() is not used anywhere outside of debugging, so
remove that since this is well-tested code.
The destination buffer of prefix_toa2x() is now enforced for the
caller. The previous array of static buffer is both wasteful
and not safe since the i++ used to switch buffers is never
guaranteed to be atomic.
|
|
ifdefs make code hard to maintain, and all modern systems
have IPv6-capable userspace anyways.
|
|
They're unused by our Ruby module, so there's no need to
preserve them.
|
|
It's standardized in POSIX.1-2001
|
|
* fix segfault from unpredictable GC ordering
when node objects outlive the trees they come from
|
|
We cannot guarantee GC will mark valid nodes when the tree
the node belongs to is destroyed, so we have to allocate
a new node that is a copy of the original node whenever
we create Patricia::Node objects
|
|
* rely on Ruby GC for allocations/free
no need to explicitly destroy objects anymore
* Ruby 1.9.2 C API compatibility
* allow creation of subclasses of Patricia class
* non-String objects may be stored as node-data
* Patricia::Node objects are returned when match succeeds
It's no longer possible to call tree methods on node
objects and cause segfaults.
* Patricia#show_nodes may be given a custom IO-like object
* sync docs with remove, match_best and match_exact behavior
* ArgumentError is raised for invalid addresses
no more assertion failures for bad addresses
* Patricia#show_nodes and Patricia#num_nodes no longer
segfaults on empty trees
|
|
This makes it easy to dump the node output to an
alternate IO/StringIO object without temporarily
replacing $stdout.
|
|
match_best and match_exact will both return nil instead
of false on failures, matching the documentation.
remove documentation is updated to match the code, which
returns true or false, never nil.
|
|
Ruby's xcalloc() has built-in failure handling and will force
GC to run if memory is needed. Patricia.new will no longer
fail with anything other than NoMemoryError, which rare.
|
|
This behaves like Patricia#match_best, but is more
efficient as it does not need to allocate a new object
on successful matches.
|
|
While the GC can take care of this, this is still useful
if one wishes to reuse the same object.
|
|
Instead of defining the Patricia.new singleton method, we
only need to define the allocation function. The allocation
function allows "dup" and "clone" methods to be called on
Patricia instances and we will walk the original tree
to copy node prefixes and data into the new one.
This also allows us to subclass Patricia and create
objects from that subclass.
|
|
Patricia#num_nodes properly returns zero and
Patricia#show_nodes displays nothing.
|
|
This allows the output of Patricia#show_nodes to be redirected
to StringIO objects (or anything else that responds to printf).
Since Ruby 1.9 no longer uses stdio, this lets us go through the
normal output stream used by Ruby.
|
|
This prevents improper dereferencing and segfaults if the code
is misused. Instead NoMethodError should be raised when it
would previously segfault.
|
|
This is preferable to hitting an assertion and killing
the running process. The plan is this code will deal with
potentially hostile/invalid user inputs in a network server,
so we do not have the luxury if just letting a process die.
|
|
rb_str_dup should be slightly faster as the call stack
is shallower and does not need additional method lookups
|
|
STR2CSTR has been deprecated for a while now, and is
completely removed in Ruby 1.9.2-preview3
|
|
This prevents segfaults from double free() calls when using
Patricia#destroy on node data or the same object twice.
Patricia#destroy and Patricia#clear are now no-ops for backwards
compatibility.
One (hopefully welcome) side effect of this change is that
arbitrary Ruby objects may be attached to nodes, not just
strings. String objects will continue to alway be duplicated
when returned to the user for backwards compatibility, but
arbitrary Ruby objects may be attached to each node. This
feature can now be used to track node usage data directly in the
Patricia object without the need for a separate lookup table.
The only downside of this change is that the GC mark phase
takes a tiny bit longer due to the presence of more Ruby
objects.
There are also additional tests for the new behavior, including
an expensive test to force GC pressure and ensure there are no
memory leaks.
|
|
There is no need for these functions and global variable
to be visible outside of rpatricia.c, so mark them as
static to avoid potential conflicts with other libraries.
|
|
- reorganized directory layout
no chance of accidentally having 'extconf' in the require path
|
|
This makes it easier to avoid accidentally putting extconf.rb
and test.rb in an application $LOAD_PATH
|
|
To build the gem:
gem build rpatricia.gemspec
|
|
|