logo标签列表

PHP：在子网列表（CIDR）中匹配IP

phpipcidr
3

我有一个CIDR列表，像这样：

192.168.0.1/24
10.0.0.1/32
etc...

列表正在增长。
为了检查一个IP是否适合这些CIDR之一，我使用下面的函数执行一个循环：
function cidr_match($ip, $range){
    list ($subnet, $bits) = explode('/', $range);
    $ip = ip2long($ip);
    $subnet = ip2long($subnet);
    $mask = -1 << (32 - $bits);
    $subnet &= $mask; // in case the supplied subnet was not correctly aligned
    return ($ip & $mask) == $subnet;
}

由于我的CIDR列表正在增长，我希望改进该函数以避免逐一测试每个CIDR行直到返回true。我想摆脱上面包围函数的for循环。
是否有一种方法可以对我即将检查的IP执行一种“预检查”，以便它不会按顺序运行完整个列表（从上到下）？
我想优化我的代码，使其行为方式为：将IP提供给函数-->函数对列表进行“排序”或“查找”最可能的CIDR-->对最可能的CIDR的IP运行检查-->尽快返回“true”。
将不胜感激地得到指导。
2个回答
2
说实话，除非你的CIDR范围很大并且在同一进程中检查了许多IP，否则你可能不会看到太多性能提升。然而，如果这是你要考虑的情况，那么你可以尝试通过预处理你的范围和IP来挤出一些性能，（执行一次ip2long()调用并将分离的掩码/子网存储以供比较）。
例如，我假设这是你目前的做法：
<?php
// Original style
$ranges = array(
  "192.168.0.1/32",
  "192.168.0.1/26",
  "192.168.0.1/24",
  "192.168.0.1/16",
  "127.0.0.1/24",
  "10.0.0.1/32",
  "10.0.0.1/24"
);


// Run the check
$start = microtime(true);
find_cidr("10.0.0.42", $ranges);
find_cidr("192.168.0.12", $ranges);
find_cidr("10.0.0.1", $ranges);
$end = microtime(true);
echo "Ran 3 find routines in " . ($end - $start) . " seconds!\n";

function find_cidr($ip, $ranges)
{
  foreach($ranges as $range)
  {
    if(cidr_match($ip, $range))
    {
      echo "IP {$ip} found in range {$range}!\n";
      break;
    }
  }  
}

function cidr_match($ip, $range){
    list ($subnet, $bits) = explode('/', $range);
    $ip = ip2long($ip);
    $subnet = ip2long($subnet);
    $mask = -1 << (32 - $bits);
    $subnet &= $mask; // in case the supplied subnet was not correctly aligned
    return ($ip & $mask) == $subnet;
}

在我的电脑上，检查三个IP地址与少量范围匹配大约需要0.0005-0.001秒的时间。

如果我编写了一些预处理范围的代码：

<?php
// Slightly-optimized style

$ranges = array(
  "192.168.0.1/32",
  "192.168.0.1/26",
  "192.168.0.1/24",
  "192.168.0.1/16",
  "127.0.0.1/24",
  "10.0.0.1/32",
  "10.0.0.1/24"
);

$matcher = new BulkCIDRMatch($ranges);
$start = microtime(true);
$matcher->FindCIDR("10.0.0.42");
$matcher->FindCIDR("192.168.0.12");
$matcher->FindCIDR("10.0.0.1");
$end = microtime(true);
echo "Ran 3 find routines in " . ($end - $start) . " seconds!\n";


class BulkCIDRMatch
{
  private $_preparedRanges = array();

  public function __construct($ranges)
  {
    foreach($ranges as $range)
    {
      list ($subnet, $bits) = explode('/', $range);
      $subnet = ip2long($subnet);
      $mask = -1 << (32 - $bits);
      $subnet &= $mask; // in case the supplied subnet was not correctly aligned

      $this->_preparedRanges[$range] = array($mask,$subnet);
    }
  }

  public function FindCIDR($ip)
  {
    $result = $this->_FindCIDR(ip2long($ip));
    if($result !== null)
    {
      echo "IP {$ip} found in range {$result}!\n";
    }
    return $result;
  }

  private function _FindCIDR($iplong)
  {
    foreach($this->_preparedRanges as $range => $details)
    {
      if(($iplong & $details[0]) == $details[1])
      {
        return $range;
      }
    }

    // No match
    return null;
  }
}

然后我看到快速的CHECKING，但是在类初始化时有稍微更多的开销，因为它会处理和存储所有的范围。所以如果我只用3个IP地址对一些范围进行整体运行时间测试，那么“优化”的方式实际上会慢一点。但是如果我使用1,000个IP地址对10,000个CIDR进行测试，“优化”的方式将比原始方式有更明显的改进（代价是使用额外的内存来存储预处理的范围数据）。
所以这完全取决于数量和你想要做什么。
话虽如此，如果你担心0.001秒的性能太慢，那么PHP可能不是用于检查的正确语言。或者至少你可能需要考虑编写一个自定义扩展，这样更多的处理就可以在C中完成。
编辑：为了回答关于在任何形式转换之前找到“可能”的范围的原始问题，这可能不是一个非常可靠的尝试。范围可以跨越其初始八位字节，因此如果您开始比较这些值（例如，“我正在查看192.168.1.0，因此我只会查看从192开始的范围”），您不仅会在每个条目上产生字符串比较的性能开销（这会减慢整体查找速度），而且您可能会错过一个有效的范围。
你提议按顺序读取“ip2longs”列表而不是“CIDRs”列表，这与同样的问题有关。关键词确实是“可能”。感谢您的帮助（和基准测试！） - Musa
你可以通过将范围按其起始长度分成不同的数组（例如0-10000000，10000001-20000000等），并对较短的数组列表进行第一次遍历，然后只需循环遍历在一般范围内的任何范围。但是再次强调，在这些速度下，体积必须巨大才能产生明显的差异，并且您必须进行调整以找到正确的权衡。 - jhilgeman
2
如果你真的关心性能，那么你应该将列表存储在类似结构的数据结构中，并以不需要查看每个条目直到找到匹配项的方式进行搜索。
在这种情况下，它是一个排序列表和二分搜索。
class CidrList {

    protected $ranges = [];

    public function addRanges($ranges) {
        foreach($ranges as $range) {
            $this->addRange($range);
        }
        $this->sortRanges();
    }

    public function findRangeByIP($ip) {
        return $this->_findRangeByIP(ip2long($ip));
    }

    // simple binary search
    protected function _findRangeByIP($ip, $start=NULL, $end=NULL) {
        if( $end < $start || $start > $end ) { return false; }

        if( is_null($start) ) { $start = 0; }
        if( is_null($end)   ) { $end = count($this->ranges) -1; }

        $mid = (int)floor(($end + $start) / 2);
        switch( $this->inRange($ip, $this->ranges[$mid]) ) {
            case 0:
                return $this->ranges[$mid][2];
            case -1:
                return $this->_findRangeByIP($ip, $start, $mid-1);
            case 1:
                return $this->_findRangeByIP($ip, $mid+1, $end);
        }
    }

    // add a single range, protected as the list must be sorted afterwards.
    protected function addRange($range) {
        list ($subnet, $bits) = explode('/', $range);
        $subnet = ip2long($subnet);
        $mask = -1 << (32 - $bits);
        $min = $subnet & $mask;
        $max = $subnet | ~$mask;
        $this->ranges[] = [$min, $max, $range];
    }

    // sort by start, then by end. aka from narrowest overlapping range to widest
    protected function sortRanges() {
        usort($this->ranges, function($a, $b) {
            $res = $a[0] - $b[0];
            switch($res) {
                case 0:
                    return $a[1] - $b[1];
                default:
                    return $res;
            }
        });
    }

    protected function inRange($ip, $range) {
        list($start, $end, $cidr) = $range;
        if( $ip < $start ) { return -1; }
        if( $ip > $end ) { return 1; }
        return 0;
    }
}

使用方法：

$l = new CidrList();
$l->addRanges(["192.168.0.1/16", "192.168.0.1/24", "127.0.0.1/24", "10.0.0.1/24"]);

var_dump(
    $l->findRangeByIP('192.168.0.10'),
    $l->findRangeByIP('192.168.1.10'),
    $l->findRangeByIP('1.2.3.4')
);

输出：

string(14) "192.168.0.1/24"
string(14) "192.168.0.1/16"
bool(false)

此外，您应该避免不断重新处理字符串，可以通过缓存整个CidrList对象或其内部范围集来实现。
那看起来更接近我想要实现的目标。非常感谢！您会推荐一种缓存对象的方法吗？我在考虑使用老式的文件缓存方式...（https://blog.graphiq.com/500x-faster-caching-than-redis-memcache-apc-in-php-hhvm-dcd26e8447ad） - Musa
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接