Появилась у меня задача быстро сгенерировать конфигурационный файл для гео модуля 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 минут. Из них полтары минуты данные загружаются из базы. Количество занимаемой памяти зависит от количества переданных сетей, сам алгоритм практически не использует память.
