Shaper tables: Использование хеш-таблиц для уменьшания числа правил шейпера

Шейпера и таблицы

Давно собирадся написать заметку про использование хеш-таблиц в шейперах.

Итак, для того чот бы избежать кучи последовательных проверок, применяется следующая конструкция:

Заголовки, и прочяя ерунда

#!/bin/bash

. func.tc 
tc=/sbin/tc
debug=1
DEV=eth3.1800
MTU=1500
QUANTUM=1600
RATE=1000000 #1GBit           

Традиционно - очистить то что было, и строить заново

$tc q d dev $DEV root &>/dev/null 

#корневая дисциплина               
cmd="$tc qdisc add dev $DEV root handle 1:0 htb default 3"

Конструкция вида

echo $cmd;$cmd;                   

используется для дебага - и вывести команду на экран и выполнить ее.

cmd="$tc filter add dev $DEV parent 1:0 protocol ip u32" 
echo $cmd;$cmd;                   

1. корневой класс

class_add $DEV 1: 1:0 "htb rate ${RATE}kbit ceil ${RATE}kbit burst 10k" 1 $QUANTUM $MTU

HTHDL=257
# Конструкции ниже абсолютно эквивалентны - перевод числа в хекс
#HTHDLhex=`printf %X$HTHDL`
printf -v HTHDLhex %X $HTHDL
#HTHDLhex=${hex[HTHDL]}                        

#хеш-таблица для подсетей, 256 элементов
cmd="$tc filter add dev $DEV parent 1:0 handle $HTHDLhex: protocol ip u32 divisor 256"
echo $cmd;$cmd;                   

#разбиваем по подсетям           
# Это правило следует читать так:
# Для любого адреса источника из сети  94.154.32.0/21
# по смещению 12 байт  наложить маску. Т.е. наложить маску на сам адрес источника.
# В результате (см маску) - будет выделен 3-й октет (в пример он может принимать значения 32-39)
# и этот октет будет использован как указатель, т.е. пакет перенаправлен в правило $HTHDLhex:Номер_Подсети
#
cmd="$tc filter add dev $DEV protocol ip parent 1:0 u32 ht 800:: match ip src 94.154.32.0/21 hashkey mask 0x0000ff00 at 12 link $HTHDLhex:"
echo $cmd;$cmd;

1

Для каждой из подсетей создаем свою хеш-таблицу полностью аналогичную таблице выше

for i in `seq 32 39`;do        
    printf -v ihex %X $i  
    let l=i+1                
    printf -v lhex %X $l  

# хеш-таблица для подсети $i
# она создается предварительно, и к одному из се элементов пакет будет передан следующим правилом
# 
    cmd="$tc filter add dev $DEV parent 1:0 handle $lhex: protocol ip u32 divisor 256"
    echo $cmd;$cmd;

# Это собственно элементы таблицы и пакет будет направлен сразу в одно из 4( в моем приемере) правил
# $ihex - это и есть номер подсети, о котором написано выше.
# разбиваем внутри подсети $i 
# А тут аналогично подсети но используется уже другой  последний элемент. В результате пакет уйдет в правило под номером совпадающее
# с последней цифрой IP  адреса таблицы lhex. lhex -  номер таблички в хексе, т.к. не модет быть равен нулю то отсюда +1. Замечу сто пример более общий - маска может быть шире.
#
    cmd="$tc filter add dev $DEV protocol ip parent 1:0 u32 ht $HTHDLhex:$ihex match ip src 94.154.$i.0/24 hashkey mask 0x000000ff at 12 link $lhex:" 
    echo $cmd;$cmd;

# аналогично - для IP  адресов.
    for j in `seq 0 255`;do 
        printf -v jhex %X $j
        let k=i*256+j+1;
        printf -v khex %X $k

        let kk=k+1
        if [ $kk -ge 65536 ];then 
            break fi
        #kkhex=`printf %X $kk`
        printf -v kkhex %X $kk
        #kkhex=${hex[kk]}
        #фильтры внутри подсети для заворота в нужный класс 
#Вычисляем номер IFB  что бы однозначно сопоставить ip  и номер IFB  куда  делать редирект
# -32 - что бы вести счет от 0, итого получаем возможные значения от 0 до 2047 - что и соответствует числу IP  адресов.
        let IFB=(i-32)*256+j 
# Это собственно конечный элемент таблицы, куда будет перенаправлен пакет таблица lhex (напомню, их у нас в примере 4), номер правила  совпадает с последней цифрой адреса.
        cmd="/sbin/tc filter add dev $DEV parent 1: prio 1 protocol ip u32 ht $lhex:$jhex match ip src 94.154.$i.$j action mirred egress redirect dev ifb${IFB}" 
        echo $cmd;$cmd; 
    done;
done