World Maker

Появилась у меня задача быстро сгенерировать конфигурационный файл для гео модуля nginx. Ниже вариант решения.

Немного о сетях.

Internet Protocol или IP (англ. internet protocol — межсетевой протокол) — маршрутизируемый сетевой протокол, протокол сетевого уровня семейства («стека») TCP/IP.  В современной сети Интернет используется IP четвёртой версии, также известный как IPv4. В протоколе IP этой версии каждому узлу сети ставится в соответствие IP-адрес длиной 4 октета (4 байта). При этом компьютеры в подсетях объединяются общими начальными битами адреса. Количество этих бит, общее для данной подсети, называется маской подсети (ранее использовалось деление пространства адресов по классам — A, B, C; класс сети определялся диапазоном значений старшего октета и определял число адресуемых узлов в данной сети, сейчас используется бесклассовая адресация). На вход мы получаем массив из двух элементов: сеть (например 192.168.1.0/31) и идентификатор. © Wikipedia

Требования на входе:

• Данными могут быть только подсети в правильном cidr формате.
• Отсортированы в порядке возрастания (при использовании базы данных это не сложно).

Требования на выходе: отсортированный список непересекающихся диапазонов в файле минимального размера. Формат: начальный адрес подсети – конечный адрес идентификатор (192.168.1.1-192.168.1.126 336).

nginx ищет соответствие определенного ip адреса и диапазонов из файла. Возвращает идентификатор.

Для начала загружаем массив сетей из базы:

my $in = $dbh->selectall_arrayref('select net, geo from locations order by net'));

Так же не забываем в начале объявить переменные:

my $last;

И открыть файл для записи.

open TARGET_BIG, ">", $file_name;

Отдаем все функции перебора сетей:

sub main_stack {
  my $IN = shift;
  my $S = [];
  my $item;
  my $LB = 0; # Крайняя левая граница
  for my $item ( @$IN ) {
    unless ( $item->[2] ) {
      my ( $ip, $mask ) = split /\//, $item->[0];
      my $st = str2dw( $ip ) & ( ( 2**$mask - 1 ) << ( 32 - $mask ) );
      $item->[2] = [ $st, $st + 2**( 32-$mask ) - 1 ];
    }
    while ( @$S ) {
      $S->[0][2][0] = $LB;
      my $c = split_ip( $S->[0], $item );
      # нет правой части.
      unless ( $c->[2] ) {
        shift @$S;
      }
      # Эта часть для сохранения в файл
      if ( $c->[0] ) {
        save_range( $c->[0] );
        $LB = $c->[0][2][1] + 1;
      }
      if ( $c->[1] ) {
        unshift @$S, $c->[1];
        last;
      }
    }
    unless ( @$S > 0 ) {
      unshift @$S, $item;
      $LB = $item->[2][0];
    }
  }
  # Ограничиваем слева оставшиеся данные из стэка
  # Дописываем содержимое стэка
  while (my $item = shift @$S) {
    save_range( [ undef, $item->[1], [ $LB, $item->[2][1] ] ] );
    $LB = $item->[2][1] + 1;
  }
  # Досохраняем последний элемент
  save_range( [ undef,0, [0, 0] ] );
}

Эта функция сохраняет диапазон

sub save_range {
  # Если пришел соседний диапазон с тем же id, то просто суммируем
  if ( $last ) {
    if ( $last->[1] eq $_[0]->[1] && $last->[2][1] + 1 == $_[0]->[2][0] ) {
      $last->[2][1] = $_[0]->[2][1];
    }
    print TARGET_BIG dw2str( $last->[2][0] ) . '-' . dw2str( $last->[2][1] ),
      "\t", $last->[1], ";\n" if $last->[1];
  }
  $last = [ undef, $_[0]->[1], [ $_[0]->[2][0], $_[0]->[2][1] ] ];
}

Для разбиения переданного диапазона используем следующий алгоритм

sub split_ip {
  my $c = [];
  if ( $_[1]->[2][0] > $_[0]->[2][1] ) {
    $c->[0] = [ undef, $_[0]->[1], $_[0]->[2] ];
  } else {
    $c->[0] = [ undef, $_[0]->[1], [ $_[0]->[2][0], $_[1]->[2][0] - 1 ] ]
      if $_[1]->[2][0] > $_[0]->[2][0];
    $c->[1] = [ undef, $_[1]->[1], $_[1]->[2] ];
    $c->[2] = [ undef, $_[0]->[1], [ $_[1]->[2][1] + 1, $_[0]->[2][1] ] ]
      if $_[1]->[2][1] < $_[0]->[2][1];
  }
  return $c;
}

Вспомогательные функции конвертирования ip

sub str2dw {
  return unpack 'N',pack( 'C4',split /\./, shift );
}

sub dw2str {
  return join '.', unpack 'C4', pack 'N',shift;
}

На вход подаю 10 000 000 диапазонов. Скрипт отрабатывает около 5 минут. Из них полтары минуты данные загружаются из базы. Количество занимаемой памяти зависит от количества переданных сетей, сам алгоритм практически не использует память.