Имеется задача: необходимо проверить, принадлежит ли данный адрес указанной подсети. В данный момент делаю следующее:Создание массива адресов:
...
cl_subnets_len++;
if ((cl_subnets_new=realloc(cl_subnets, cl_subnets_len*sizeof(struct tcl_subnet))))
cl_subnets=cl_subnets_new;
else error(1,"get_client_cf: can't allocate memory at %s:%d!",__FILE__,__LINE__);
cl_subnets[cl_subnets_len-1].cl_id=i;
if ((cl_subnets[cl_subnets_len-1].subnet_len=inet_net_pton(AF_INET,
wrk_str,&(cl_subnets[cl_subnets_len-1].subnet),sizeof(struct in_addr))) == -1)
cl_subnets_len--;
...Потом проверка, принадлежит ли адрес одному из элементов массива:
int
get_cl_id(session_ip)
struct in_addr session_ip;
{
register int i;
if (!cl_subnets) return -1;
for (i=0;(i<cl_subnets_len);i++)
if (inet_netof(session_ip) == inet_netof(cl_subnets[i].subnet.s_addr))
break;
if (i==cl_subnets_len) return -1;
return cl_subnets[i].cl_id;
}Однако мучают меня сомнения, что это правильно, хотя бы потому, что struct in_addr не имеет в себе разграничителя сеть/хост (по крайней мере, я не нашел). По какому принципу отделяются сети от хостов?
Уверен, что какие-то функции реализуют необходимые мне действия. Только подскажите, какие именно. А надо мне, повторюсь, проверить принадлежность хоста сети.
PS: забыл, адреса в конфиге записаны в виде xxx.xxx.xxx.xxx/yy
Эти yy - это битовая маска, которая указывает на то, сколько бит из всего IP адреса используются для определения сети. Например:
192.168.0.0/24
Значит, что 192.168.0 - сеть (3 байта по 8 бит = 24 бита)
Последний байт адресует хост. В сети 256 машин
192.168.0.0/26
192.168.0 + еще 2 бита из последнего байта - сеть.
оставшиеся 6 бит - хост. Соответственно в 1 сети у нас 64 машины
192.168.0.0 - 192.168.0.63 - первая сеть
192.168.0.64 - 192.168.0.127 - вторая сеть и т.д.
Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких циклов не надо.
Как именно организуетс маска подсети, мне известно, но все равно спасибо за разъяснение :)
>Используя старый добрый оператор & можно быстро и эффективно решить проблему. Никаких
>циклов не надо.Во первых: на разных платформах порядок байтов в struct in_addr разный, а из манов я так и не вынес, какой надо юзать для обеспечения кроссплатформенности :(
Во-вторых: мне надо каждый раз создавать накладываемую маску разной длинны, как ее создать? воспользоваться потом оператором & проблемы не составит...
то есть, мне нужно на 192.168.21.15 наложить маску /21, а на 197.185.16.11 - /24. При помощи чего мне эти маски создавать?
ЗЫ: циклы использовались для создания массива сетей, а не определения маски :)
>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>из манов я так и не вынес, какой надо юзать для
>обеспечения кроссплатформенности :(http://www.opengroup.org/onlinepubs/009695399/basedefs/netin...
---cut---
The <netinet/in.h> header shall define the sockaddr_in structure that includes at least the following members:
sa_family_t sin_family AF_INET.
in_port_t sin_port Port number.
struct in_addr sin_addr IP address.The sin_port and sin_addr members shall be in network byte order.
---cut----> в сетевом порядке (что вполне логично). если же ваша пталформа это делает как-то иначе, это ее персональные сексуальные трудности :)
// wbr
>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>из манов я так и не вынес, какой надо юзать для
>обеспечения кроссплатформенности :(ps: маны в таком вопросе, как слендование стандарту, далеко не самый правильный источник информации.
// wbr
>>Во первых: на разных платформах порядок байтов в struct in_addr разный, а
>>из манов я так и не вынес, какой надо юзать для
>>обеспечения кроссплатформенности :(
>
>ps: маны в таком вопросе, как слендование стандарту, далеко не самый правильный
>источник информации.
>
>// wbrcut <man inet>
<...>
INTERNET ADDRESSES
Values specified using the `.' notation take one of the following forms:
a.b.c.d
a.b.c
a.b
a
When four parts are specified, each is interpreted as a byte of data and assigned, from left to right, to the four bytes of an Internet address. Note that when an Internet address is viewed as a 32-bit integer quantity on the VAX the bytes referred to above appear as ``d.c.b.a''. That is, VAX bytes are ordered from right to left.
<...>man`ам FreeBSD я все-таки доверяю. Да и где-то читал (чуть ли не в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.
Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски. Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц слева и остальными нулями справа?
>cut <man inet>
><...>
>INTERNET ADDRESSES
> Values specified using the `.' notation take
>one of the following forms:
> a.b.c.d
>
> a.b.c
>
> a.b
>
> a
>
> When four parts are specified, each is
>interpreted as a byte of data and assigned, from left to
>right, to the four bytes of an Internet address. Note that
>when an Internet address is viewed as a 32-bit integer quantity
>on the VAX the bytes referred to above appear as ``d.c.b.a''.
> That is, VAX bytes are ordered from right to left.
>
><...>
>
>man`ам FreeBSD я все-таки доверяю.а man для BSD и не противоречит сказанному :) сверху ничего не сказано о том, в каком тменно порядке передаются/возвращаются параметны в sockaddr_in.
> Да и где-то читал (чуть ли не
>в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.с их точки зрения может быть и так, не читал. с точки зрения стандарта - нет. если бы это было так, написание платформонезависимых приложений с исользоиванием сокетов превратилось бы в форменный кошмар.
>Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски.
>Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц
>слева и остальными нулями справа?термин "просто" более чем растяжимое понятне :) ну, например:
---cut---
#include <stdio.h>
#include <stdint.h>uint32_t
get_mask(int nbits)
{
uint32_t result = 0, mask = 0x80000000;while (nbits-- > 0) {
result |= mask;
mask >>= 1;
}return result;
}int
main()
{
int nbits = 0;while (nbits <= 32) {
printf("nbits %-2d mask %08Xh\n",
nbits, get_mask(nbits));
nbits++;
}return 0;
}
---cut---ps: ессно что в рабочей версии это нужно еще несколько подправить. внести проверки на nbits и пр.
// wbr
Скоростной метод:
Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом. Это даст очень высокую скорость. Вообще, по моему, если важна скорость, лучше всю функцию распознавания переписать на ассемблере. Этот язык идеально подходит для битовых операций.
>Скоростной метод:
>Тупо руками создаем 32 маски и заносим в массив под соответствующим индексом.как вариант. с учетом вполне конкретной постановки задачи, это вполне подойдет.
>Это даст очень высокую скорость. Вообще, по моему, если важна скорость,
>лучше всю функцию распознавания переписать на ассемблере. Этот язык идеально подходит
>для битовых операций.а вот этого делать видимо не стоит :) выигрыш по сравнению с таблицей такой подход даст нулевой, а вот геморою с сопровождением такого решения можно огрестить по полной программе, причем, на пустом месте.
// wbr
>>cut <man inet>
>><...>
>>INTERNET ADDRESSES
>> Values specified using the `.' notation take
>>one of the following forms:
>> a.b.c.d
>>
>> a.b.c
>>
>> a.b
>>
>> a
>>
>> When four parts are specified, each is
>>interpreted as a byte of data and assigned, from left to
>>right, to the four bytes of an Internet address. Note that
>>when an Internet address is viewed as a 32-bit integer quantity
>>on the VAX the bytes referred to above appear as ``d.c.b.a''.
>> That is, VAX bytes are ordered from right to left.
>>
>><...>
>>
>>man`ам FreeBSD я все-таки доверяю.
>
>а man для BSD и не противоречит сказанному :) сверху ничего не
>сказано о том, в каком тменно порядке передаются/возвращаются параметны в sockaddr_in.
>
>
>> Да и где-то читал (чуть ли не
>>в "Руководстве по технологиям объединенных сетей" КискоПресса), что это платформозависимый параметр.
>
>с их точки зрения может быть и так, не читал. с точки
>зрения стандарта - нет. если бы это было так, написание платформонезависимых
>приложений с исользоиванием сокетов превратилось бы в форменный кошмар.
>
>>Ладно, с этим разберусь, почитаю стандарты. Теперь все-таки вопрос с организацией маски.
>>Как ПРОСТО создать 4-х байтную переменную, состоящую из yy количества единиц
>>слева и остальными нулями справа?
>
>термин "просто" более чем растяжимое понятне :) ну, например:
>
>---cut---
>#include <stdio.h>
>#include <stdint.h>
>
>uint32_t
>get_mask(int nbits)
>{
> uint32_t result = 0,
>mask = 0x80000000;
>
> while (nbits-- > 0) {
>
> result |= mask;
> mask >>= 1;
> }
>
> return result;
>}
>
>int
>main()
>{
> int nbits = 0;
>
>
> while (nbits <= 32)
>{
>
> printf("nbits %-2d mask %08Xh\n",
>
>
> nbits, get_mask(nbits));
>
> nbits++;
> }
>
> return 0;
>}
>---cut---
>
>ps: ессно что в рабочей версии это нужно еще несколько подправить. внести
>проверки на nbits и пр.
>
>// wbr
видимо решаем схожие задачи :-)
Есть таблица с префиксами сетей ~5000 записей,
включает сети, некоторые подсети и отдельные хосты,
как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски (определение минимальной подсети) ?
Пока-что сделал в лоб, простым просмотром всего, но сразу для двух адресов. Но ведь есть алгоритмы оптимальнее...
Поделитесь ссылкой, или хотя-бы намёком :)
>Есть таблица с префиксами сетей ~5000 записей,
>включает сети, некоторые подсети и отдельные хосты,
>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>(определение минимальной подсети) ?ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу несколько подробнее :) что на входе, что на выходе.
// wbr
>>Есть таблица с префиксами сетей ~5000 записей,
>>включает сети, некоторые подсети и отдельные хосты,
>>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>>(определение минимальной подсети) ?
>
>ммм... не совсем понял, что же именно вы хотите сделать. опишите задачу
>несколько подробнее :) что на входе, что на выходе.
>
>// wbr
в терминах C (упрощенно)-
/** тут хранится информация о сетях/подсетях/хостах **/
struct net_info {
uint32 addr; // net oh host address
uint32 mask; // net (bit) mask
unsigned short mask_size; //
/* other info`s */
...
}net_tab[NET_TAB_SIZE];
/** функция поиска */
int net_resolve(struct net_info *table,
uint32 addr1,
struct netinfo **info1,
uint32 addr2,
struct netinfo **info2);
Ищет в таблице сразу два адреса (они и приходят по парам)..
Учитывая, что кол-во записей может быть велико(от 5000), меня этот алг. не совсем устраивает.Хочется алгоритм O(ln n) для поиска в этом(в net_tab).Причем находить надо минимальную подсеть, то если есть записи для 192.168.0.0/16 и 192.168.10.0/24 для 192.168.10.11 должен быть найден 192.168.10.0/24..
Допускаю что вместо массива надо использовать динамическую структуру (дерево множест?, что-то еще??)Если использовать просто бинарный поиск в массиве, то находится первое подходящее(например сеть с меньшей маской) и чтобы затем найти то что надо,требуется некоторое шаманство,
что не совсем красиво и скорости не прибавляет
>в терминах C (упрощенно)-
>/** тут хранится информация о сетях/подсетях/хостах **/
>struct net_info {
> uint32 addr; // net oh host address
> uint32 mask; // net (bit) mask
> unsigned short mask_size; //
> /* other info`s */
> ...
>}net_tab[NET_TAB_SIZE];
>/** функция поиска */
>int net_resolve(struct net_info *table,
> uint32 addr1,
> struct netinfo **info1,
> uint32 addr2,
> struct netinfo **info2);нет уж, пожалуйста, давайте ставить задачу в терминах русского языка :)
>Ищет в таблице сразу два адреса (они и приходят по парам)..
да хоть квадруплями. если я правильно понял проблему, это значения не имеет.
>Хочется алгоритм O(ln n) для поиска в этом(в net_tab).Причем находить надо минимальную
>подсеть, то если есть записи для 192.168.0.0/16 и 192.168.10.0/24 для 192.168.10.11
>должен быть найден 192.168.10.0/24..термины:
минимальная подсеть - подсеть с минимальной длиной в битах.
максимальная подсеть - подсеть с максимальной длиной в битах.
откуда: a.b.c.0/24 > a.b.0.0/16итого, на входе:
есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.требуется:
в множестве найти подсеть с максимальной длиной для заданного адреса.я правильно понял?
// wbr
>итого, на входе:
>есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.
>
>требуется:
>в множестве найти подсеть с максимальной длиной для заданного адреса.
>
>я правильно понял?
>
>// wbr
да
>>итого, на входе:
>>есть некоторое множество подсетей вида <адрес>/<длина>. множество допускает "перекрытие" элементов i.e. <a.b.0.0>/16 и <a.b.c.0>/24. дан входящий адрес.
>>
>>требуется:
>>в множестве найти подсеть с максимальной длиной для заданного адреса.
>>
>>я правильно понял?
>>
>>// wbr
>даподумайте в сторону организации множества сетей в виде дерева по принципу "от худшего к лучшему".
пример:
множество вида:
1.1.[1-254].0 /24
1.1.0.0 /16
1.2.[1-254].0 /24
1.2.0.0 /16
1.3.0.0 /16адрес 1.3.4.5
после сортировки массива по разрядности сети от большей к меньшей вы получите, что для поиска адреса вы пройдете весь массив. а если бы вы построили дерево вида:
1.1.0.0/16
1.1.[1-254].0/24
1.2.0.0/16
1.2.[1-254].0/24
1.3.0.0/16то первые два узла, вместе с дочерними, очевидно, отпали бы сразу.
"сперва ищите худшее подходящее, в неподходящем не ищите лучшего, в подходящем ищите лучшее".
// wbr
Честно говоря, не совсем понятно, что вам нужно. Можно поконкретнее обрисовать задачу?
>видимо решаем схожие задачи :-)
>Есть таблица с префиксами сетей ~5000 записей,
>включает сети, некоторые подсети и отдельные хосты,
>как в ней сделать быстрый поиск подходяшей записи с максимальной длинной маски
>(определение минимальной подсети) ?
>Пока-что сделал в лоб, простым просмотром всего, но сразу для двух адресов.
>Но ведь есть алгоритмы оптимальнее...
>Поделитесь ссылкой, или хотя-бы намёком :)Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится указанный хост, при чем надо выбрать запись с минимальной маской.
Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера маски (/32 - верхние элементы, /0 - нижние) и потом линейным поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного способа
Телепат !!
так оно и есть - так оно сейчас и сделанно,
с простейшим улучшением (ищется сразу два адреса, пока не будут найденны оба)
Собственно вопрос - возможно ли другое, более оптимальное по скорости решение ?
>Телепат !!
>так оно и есть - так оно сейчас и сделанно,
>с простейшим улучшением (ищется сразу два адреса, пока не будут найденны оба)
>
>Собственно вопрос - возможно ли другое, более оптимальное по скорости решение ?
>
Можно делать еще следующее: одномерный массив разбивается на 2-мерный с переменной длиной строки. Номер строки - количество значимых бит в маске. Каждая строка сортируется (либо по возрастанию, либо по убыванию). После этого бинарным поиском ищем необходимый элемент сначала в 32-й строке, не нашли? тогда в 31-й... и т.д.
>Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится
>указанный хост, при чем надо выбрать запись с минимальной маской.
>
>Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера
>маски (/32 - верхние элементы, /0 - нижние) и потом линейным
>поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного
>способа
Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным поиском - man bsearch
>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>поиском - man bsearch
к сожалению bsearch не помогает в этой задаче - практически наверняка
на первой же итерации он найдет ´подходящую´ запись 0.0.0.0/0 описывающую вообще всё множество сетей - а дальше как ?
А у Вас как определяется принадлежность хоста сети?
>А у Вас как определяется принадлежность хоста сети?может я конечно что-то не так понимаю, но а что, могут быть варианты?
ok = (host_addr & net_mask) == net_addr;
// wbr
>А у Вас как определяется принадлежность хоста сети?
опуская проверки, только для ip4, просто булевая функция,
все адреса и маски в сетевом представлении :
struct net_info {
uint32 addr;
uint32 mask;
...
};
int net_contain_host(struct net_info *net,uint32 host) {
...
if ((host & net->mask) == net->addr)
return 1;
return 0;
}
>>Попробую потелепатить: есть массив сетей, надо определить, к которой из них относится
>>указанный хост, при чем надо выбрать запись с минимальной маской.
>>
>>Если да, то простейший способ: сортируешь однократно этот массив по убыванию размера
>>маски (/32 - верхние элементы, /0 - нижние) и потом линейным
>>поиском по массиву до первого совпадения. Возможно, есть варианты улучшения данного
>>способа
>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>поиском - man bsearchНе пойдет, ключи сортировки и поиска не совпадают
>>Еще бы. Если массив отсортирован, то искать надо не линейным, а двоичным
>>поиском - man bsearch
>
>Не пойдет, ключи сортировки и поиска не совпадают
Если плясать от хоста - то да. Однако если нам известен хост, то можно было бы воспользоваться "алгоритмом связанности", который идеально решает задачу на принадлежность одного элемента множеству других. Я сейчас не помню все детали реализации, но, в общем, там нет ничего сложного. Алгоритм описан в книге "Фундаментальные алгоритмы на С/С++", которую я всем рекомендую.
>Поделитесь ссылкой, или хотя-бы намёком :)
http://www.cs.unc.edu/~geom/TEACH/COMP122/LEC/29.ppt>Но ведь есть алгоритмы оптимальнее...
http://netlab.cs.tsinghua.edu.cn/~lzy/Lookup/99/IP-address lookup using LC-tries_IEEE Journal on Selected Areas in Communications.pdf
>>Поделитесь ссылкой, или хотя-бы намёком :)
>http://www.cs.unc.edu/~geom/TEACH/COMP122/LEC/29.ppt
>
>>Но ведь есть алгоритмы оптимальнее...
>http://netlab.cs.tsinghua.edu.cn/~lzy/Lookup/99/IP-address lookup using LC-tries_IEEE Journal on Selected Areas in Communications.pdfСпасибо за ссылки, очень порадовали фотки
в стиле "их разыскивает милиция" во втором документе ;-)LC-tries конечно хорошо, но для моих целей пойдет и чего попроще ;-)
В результате размышлений пришёл к выводу, что вполне пойдет простое
сбалансированное дерево ;-) Сортируется по номерам сетей, ищется последний подходящий вариант - и вуаля - нужная сеть по хосту найденна !Еще раз спасибо, документы добавил в личную коллекцию...