Skip Menu |

This queue is for tickets about the Net-Patricia CPAN distribution.

Report information
The Basics
Id: 14244
Status: resolved
Worked: 3 hours (180 min)
Priority: 0/
Queue: Net-Patricia

People
Owner: PHILIPP [...] cpan.org
Requestors: mark [...] asphyx.net
Cc:
AdminCc:

Bug Information
Severity: Normal
Broken in: 1.010
Fixed in: 1.15



Subject: match_string matches wrong node
Seems that match_string will sometimes match the wrong node. Look: use Net::Patricia; my $pt1 = new Net::Patricia; $pt1->add_string("10.0.0.0/16", "10.0.0.0/16"); $pt1->add_string("10.0.0.0/18", "10.0.0.0/18"); print $pt1->match_string("10.0.0.0/17") . "\n"; $pt1->add_string("10.0.64.0/18", "10.0.64.0/18"); print $pt1->match_string("10.0.0.0/17") . "\n"; output: 10.0.0.0/18 10.0.0.0/16 This is with: Net-Patricia-1.010 & perl v5.8.4 on Linux Rgds, Mark. If I compile libpatricia with #define PATRICIA_DEBUG 1 the output is: patricia_lookup: new_node #0 10.0.0.0/16 (head) patricia_lookup: stop at 10.0.0.0/16 patricia_lookup: differ_bit 16 patricia_lookup: new_node #2 10.0.0.0/18 (child) patricia_search_best: push 10.0.0.0/16 patricia_search_best: take left 10.0.0.0/16 patricia_search_best: stop at 10.0.0.0/18 patricia_search_best: pop 10.0.0.0/18 patricia_search_best: found 10.0.0.0/18 10.0.0.0/18 patricia_lookup: take left 10.0.0.0/16 patricia_lookup: stop at 10.0.0.0/18 patricia_lookup: differ_bit 17 patricia_lookup: new_node #4 10.0.64.0/18 (glue+node) patricia_search_best: push 10.0.0.0/16 patricia_search_best: take left 10.0.0.0/16 patricia_search_best: stop at 17 patricia_search_best: pop 10.0.0.0/16 patricia_search_best: found 10.0.0.0/16 10.0.0.0/16
This fix (and version bump to 1.015) fixes both this issue, plus the lack of the xxx_integer() API methods, i.e. add_integer() and remove_integer(). One concern is that this would affect applications that expect the previous (incorrect) behavior. Perhaps a solution is to add to the import list a name that enables the new functionality... otherwise, perhaps a major version bump (to 2.0) is required.
--- Net-Patricia-1.014/Patricia.pm.orig 2005-12-08 17:05:00.000000000 -0700 +++ Net-Patricia-1.014/Patricia.pm 2009-01-16 18:53:42.000000000 -0700 @@ -23,12 +23,12 @@ package Net::Patricia; use strict; use Carp; use vars qw($VERSION @ISA); -use Socket qw(AF_INET inet_aton); +use Socket qw(AF_INET inet_aton inet_ntoa); require DynaLoader; @ISA = qw(DynaLoader); -'$Revision: 1.14 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); +'$Revision: 1.15 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); bootstrap Net::Patricia $VERSION; @@ -91,6 +91,14 @@ sub Net::Patricia::AF_INET::add { _add($self,AF_INET,$packed,$bits || 32, $data); } +sub Net::Patricia::AF_INET::add_integer { + my ($self, $num, $bits, $data) = @_; + my $packed = pack("N", $num); + my $ip = inet_ntoa($packed) || croak("invalid address"); + $data ||= $bits ? "$ip/$bits" : $ip; + _add($self,AF_INET,$packed,$bits || 32, $data); +} + sub Net::Patricia::AF_INET::match_integer { my ($self, $num, $bits) = @_; _match($self,AF_INET,pack("N",$num),$bits || 32); @@ -119,6 +127,10 @@ sub Net::Patricia::AF_INET::remove { _remove($self,AF_INET,$packed,$bits || 32); } +sub Net::Patricia::AF_INET::remove_integer { + my ($self, $num, $bits) = @_; + _remove($self,AF_INET,pack("N",$num),$bits || 32); +} 1; __END__ --- Net-Patricia-1.014/libpatricia/patricia.c.orig 2005-12-07 13:55:39.000000000 -0700 +++ Net-Patricia-1.014/libpatricia/patricia.c 2009-01-16 15:44:49.000000000 -0700 @@ -639,7 +639,7 @@ patricia_search_best2 (patricia_tree_t * #endif /* PATRICIA_DEBUG */ if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix), - node->prefix->bitlen)) { + node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { #ifdef PATRICIA_DEBUG fprintf (stderr, "patricia_search_best: found %s/%d\n", prefix_toa (node->prefix), node->prefix->bitlen);
Modified fix, merging fix for 20219: http://rt.cpan.org/Public/Bug/Display.html?id=20219 including changes for add_integer() and remove_integer() methods.
--- Net-Patricia-1.014/Patricia.xs.orig 2005-12-08 15:26:33.000000000 -0800 +++ Net-Patricia-1.014/Patricia.xs 2009-01-25 18:06:02.000000000 -0800 @@ -140,7 +140,7 @@ not_there: #define Fill_Prefix(p,f,a,b,mb) \ do { \ - if (b <= 0 || b > mb) \ + if (b < 0 || b > mb) \ croak("invalid key"); \ memcpy(&p.add.sin, a, (mb+7)/8); \ p.family = f; \ --- Net-Patricia-1.014/Patricia.pm.orig 2005-12-08 16:05:00.000000000 -0800 +++ Net-Patricia-1.014/Patricia.pm 2009-01-25 18:10:15.000000000 -0800 @@ -23,12 +23,12 @@ package Net::Patricia; use strict; use Carp; use vars qw($VERSION @ISA); -use Socket qw(AF_INET inet_aton); +use Socket qw(AF_INET inet_aton inet_ntoa); require DynaLoader; @ISA = qw(DynaLoader); -'$Revision: 1.14 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); +'$Revision: 1.15 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); bootstrap Net::Patricia $VERSION; @@ -86,39 +86,51 @@ sub remove_string { sub Net::Patricia::AF_INET::add { my ($self, $ip, $bits, $data) = @_; - $data ||= $bits ? "$ip/$bits" : $ip; + $data ||= defined $bits ? "$ip/$bits" : $ip; my $packed = inet_aton($ip) || croak("invalid key"); _add($self,AF_INET,$packed,$bits || 32, $data); } +sub Net::Patricia::AF_INET::add_integer { + my ($self, $num, $bits, $data) = @_; + my $packed = pack("N", $num); + my $ip = inet_ntoa($packed) || croak("invalid address"); + $data ||= defined $bits ? "$ip/$bits" : $ip; + _add($self,AF_INET,$packed,defined $bits ? $bits : 32, $data); +} + sub Net::Patricia::AF_INET::match_integer { my ($self, $num, $bits) = @_; - _match($self,AF_INET,pack("N",$num),$bits || 32); + _match($self,AF_INET,pack("N",$num),defined $bits ? $bits : 32); } sub Net::Patricia::AF_INET::exact_integer { my ($self, $num, $bits) = @_; - _exact($self,AF_INET,pack("N",$num),$bits || 32); + _exact($self,AF_INET,pack("N",$num),defined $bits ? $bits : 32); } sub Net::Patricia::AF_INET::match { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || croak("invalid key"); - _match($self,AF_INET,$packed,$bits || 32); + _match($self,AF_INET,$packed,defined $bits ? $bits : 32); } sub Net::Patricia::AF_INET::exact { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || croak("invalid key"); - _exact($self,AF_INET,$packed,$bits || 32); + _exact($self,AF_INET,$packed,defined $bits ? $bits : 32); } sub Net::Patricia::AF_INET::remove { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || return undef; - _remove($self,AF_INET,$packed,$bits || 32); + _remove($self,AF_INET,$packed,defined $bits ? $bits : 32); } +sub Net::Patricia::AF_INET::remove_integer { + my ($self, $num, $bits) = @_; + _remove($self,AF_INET,pack("N",$num),defined $bits ? $bits : 32); +} 1; __END__ --- Net-Patricia-1.014/libpatricia/patricia.c.orig 2005-12-07 12:55:39.000000000 -0800 +++ Net-Patricia-1.014/libpatricia/patricia.c 2009-01-25 18:05:40.000000000 -0800 @@ -639,7 +639,7 @@ patricia_search_best2 (patricia_tree_t * #endif /* PATRICIA_DEBUG */ if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix), - node->prefix->bitlen)) { + node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { #ifdef PATRICIA_DEBUG fprintf (stderr, "patricia_search_best: found %s/%d\n", prefix_toa (node->prefix), node->prefix->bitlen);
Amended: left out some parens and a "defined" test.
--- Net-Patricia-1.014/Patricia.xs.orig 2005-12-08 15:26:33.000000000 -0800 +++ Net-Patricia-1.014/Patricia.xs 2009-01-25 18:06:02.000000000 -0800 @@ -140,7 +140,7 @@ not_there: #define Fill_Prefix(p,f,a,b,mb) \ do { \ - if (b <= 0 || b > mb) \ + if (b < 0 || b > mb) \ croak("invalid key"); \ memcpy(&p.add.sin, a, (mb+7)/8); \ p.family = f; \ --- Net-Patricia-1.014/Patricia.pm.orig 2005-12-08 16:05:00.000000000 -0800 +++ Net-Patricia-1.014/Patricia.pm 2009-01-25 18:10:15.000000000 -0800 @@ -23,12 +23,12 @@ package Net::Patricia; use strict; use Carp; use vars qw($VERSION @ISA); -use Socket qw(AF_INET inet_aton); +use Socket qw(AF_INET inet_aton inet_ntoa); require DynaLoader; @ISA = qw(DynaLoader); -'$Revision: 1.14 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); +'$Revision: 1.15 $' =~ m/(\d+)\.(\d+)/ && (( $VERSION ) = sprintf("%d.%03d", $1, $2)); bootstrap Net::Patricia $VERSION; @@ -86,39 +86,51 @@ sub remove_string { sub Net::Patricia::AF_INET::add { my ($self, $ip, $bits, $data) = @_; - $data ||= $bits ? "$ip/$bits" : $ip; + $data ||= defined $bits ? "$ip/$bits" : $ip; my $packed = inet_aton($ip) || croak("invalid key"); - _add($self,AF_INET,$packed,$bits || 32, $data); + _add($self,AF_INET,$packed,(defined $bits ? $bits : 32), $data); } +sub Net::Patricia::AF_INET::add_integer { + my ($self, $num, $bits, $data) = @_; + my $packed = pack("N", $num); + my $ip = inet_ntoa($packed) || croak("invalid address"); + $data ||= defined $bits ? "$ip/$bits" : $ip; + _add($self,AF_INET,$packed,(defined $bits ? $bits : 32), $data); +} + sub Net::Patricia::AF_INET::match_integer { my ($self, $num, $bits) = @_; - _match($self,AF_INET,pack("N",$num),$bits || 32); + _match($self,AF_INET,pack("N",$num),(defined $bits ? $bits : 32)); } sub Net::Patricia::AF_INET::exact_integer { my ($self, $num, $bits) = @_; - _exact($self,AF_INET,pack("N",$num),$bits || 32); + _exact($self,AF_INET,pack("N",$num),(defined $bits ? $bits : 32)); } sub Net::Patricia::AF_INET::match { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || croak("invalid key"); - _match($self,AF_INET,$packed,$bits || 32); + _match($self,AF_INET,$packed,(defined $bits ? $bits : 32)); } sub Net::Patricia::AF_INET::exact { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || croak("invalid key"); - _exact($self,AF_INET,$packed,$bits || 32); + _exact($self,AF_INET,$packed,(defined $bits ? $bits : 32)); } sub Net::Patricia::AF_INET::remove { my ($self, $ip, $bits) = @_; my $packed = inet_aton($ip) || return undef; - _remove($self,AF_INET,$packed,$bits || 32); + _remove($self,AF_INET,$packed,(defined $bits ? $bits : 32)); } +sub Net::Patricia::AF_INET::remove_integer { + my ($self, $num, $bits) = @_; + _remove($self,AF_INET,pack("N",$num),(defined $bits ? $bits : 32)); +} 1; __END__ --- Net-Patricia-1.014/libpatricia/patricia.c.orig 2005-12-07 12:55:39.000000000 -0800 +++ Net-Patricia-1.014/libpatricia/patricia.c 2009-01-25 18:05:40.000000000 -0800 @@ -639,7 +639,7 @@ patricia_search_best2 (patricia_tree_t * #endif /* PATRICIA_DEBUG */ if (comp_with_mask (prefix_tochar (node->prefix), prefix_tochar (prefix), - node->prefix->bitlen)) { + node->prefix->bitlen) && node->prefix->bitlen <= bitlen) { #ifdef PATRICIA_DEBUG fprintf (stderr, "patricia_search_best: found %s/%d\n", prefix_toa (node->prefix), node->prefix->bitlen); --- Net-Patricia-1.014/test.pl (revision 22) +++ Net-Patricia-1.014/test.pl (revision 25) @@ -6,7 +6,7 @@ # Change 1..1 below to 1..last_test_to_print . # (It may become useful if the test is moved to ./t subdirectory.) -BEGIN { $| = 1; $debug = 1; print "1..18\n"; } +BEGIN { $| = 1; $debug = 1; print "1..19\n"; } END {print "not ok 1\n" unless $loaded;} use Net::Patricia; $loaded = 1; @@ -128,6 +128,10 @@ print "not ok 18\n" } +$t->add_string('0/0'); + +print $t->match_string("10.0.0.1")?"ok 19\n":"not ok 19\n"; + undef $t; exit;