読者です 読者をやめる 読者になる 読者になる

totofugaのブログ

PerlとかC++のプログラム系の話

Unboundのmsgキャッシュについて

unbound c言語

f:id:totofuga:20170321232719j:plain

msgキャッシュとは

ユーザからのリクエストをkeyとしてレスポンスを保存するためのハッシュ

keyがquery_infoでvalueがreply_infoとなる。 ハッシュ構造とキーをまとめて管理できるように msgreply_entryという構造体にまとめられている。

reply_infoとub_packed_rrset_key

reply_infoが参照しているub_packed_rrset_keyは rrsetキャッシュ内にあるものを指している為、 rrsetキャッシュの容量がいっぱいになった場合に削除される可能性がある。

削除されるとポインタの参照先が無効領域になってしまい、 セグフォになってしまう為、一度確保したub_packed_rrset_keyは削除せずに 領域を再利用する構造になっている(util/alloc.hを参照)

領域が解放されるとub_packed_rrset_keyとrrset_refのidが違うものになる為解放されたことがわかる。 idを確認する為にはub_packed_rrset_keyのロックを取得してからidの確認を行う。 ロックはハッシュで使用しているものと同じものを使用する。

unboundのCNAME処理

unbound c言語

処理内容

権威からCNAMEが返ってきた場合、 キャッシュサーバーでは別名を引きに行かなくてはいけない。

仮に下記のような登録があった場合、キャッシュサーバーにて cname.jp.への問い合わせとanswer.jpへの問い合わせを行い、 それらのレコードを合成して結果を返す必要がある

[cname.jp]
cname.jp. CNAME IN answer.jp.
[answer.jp]
answer.jp. A IN 1.1.1.1
[クライアントに返す必要があるレスポンス]
cname.jp. CNAME IN answer.jp.
answer.jp. A IN 1.1.1.1

権威からのCNAME受信

process_response(権威サーバーからのメッセージをparse)
    processQueryResponse(レスポンス処理)
        iter_handle
            iter_dns_store(rrsetのみをキャッシュ)
            handle_name_response
                iter_add_prepend_answer(クライアントへのレスポンスで必要なのでストアしておく)
            iter_qstateのqchase入れ替えしてqstateを初期化
            next_state(iq, INIT_REQUEST_STATE)

CNAMEで返ってきたrrsetを iter_qstateのan_prepend_listに追加しておき、 qchaseをCNAMEから取り出した内容で置き換えて (元の問い合わせはmodule_qstateのqinfoに入っている) 再度リクエスト処理を行う。

INIT_REQUEST_STATEからリクエストを開始するので、 キャッシュがあれば通常通りキャッシュが使用される。

クライアントへのレスポンス

iter_handle
    processFinishded
        iter_prepend(an_prepend_listにストアしていたものを取り出し、dns_msgを作り直す)
        iter_dns_store(msgとrrset両方キャッシュする)

CNAME先の問い合わせとan_prepend_listにストアしていたものを 合成してレスポンスを作成する

合成したものをキャッシュにストアしておく。

まとめ

CNAMEでのリクエストがあった場合には Aレコードをストアしておき問い合わせ名を変えて再度リクエスト。 クライアントに返せる状態になってからAレコードを取り出し合成する。 合成した情報をキャッシュに入れて次回のリクエストに備えている。

おまけ

CNAMEの無限ループを抑えるため、MAX_RESTART_COUNT以上CNAMEを辿らないようになっている MAX_RESTART_COUNTは8となっている。

パケット遅延

ネットワーク linux

tcpのport 53 synパケットのみを3秒遅延したい等 特定のパケットのみに遅延を適用させる方法。

条件設定にはtcを使って行う方法とiptablesのMARK経由で行う方法がある。 今回は遅延以外にもdropやreject(impパケットを返す)も別途行いたかったので 条件をまとめられるようiptablesを使用した。

TCの設定

tcで下記のようなキューを作成する

  • キュー1 条件: MARK1 動作: 3秒遅延
  • キュー2 条件: MARK2 動作: 5秒遅延
  • キュー3 条件: MARK3 動作: 10秒遅延
  • キュー4 条件: デフォルト 動作: 遅延しない

prioキュー設定

まずprioキューを作成する

tc qdisc add dev eth0 root handle 1: prio bands 4 priomap 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
bands

振り分けを行うクラスの数で今回は4個のクラスを作成する。

priomap

ipヘッダのTOSを見てどのクラスに振り分けるかの指定する設定だが、 今回パケットはTOSに関係なく全て4に送りたいので3を指定する。 (priomapのインデックスは0スタートなので3はクラス4の意味になる)

遅延用のキューを作成

prioキューの設定を行うと1:1 1:2 1:3 1:4の4つのクラスが出来てデフォルトでこれらは、 fifo qdiscと繋がっている。1:1 1:2 1:3の3つには遅延を行いたいのでnetemキューに繋ぎ直す

tc qdisc add dev eth0 parent 1:1 handle 10: netem delay 3s  
tc qdisc add dev eth0 parent 1:2 handle 20: netem delay 5s  
tc qdisc add dev eth0 parent 1:3 handle 30: netem delay 10s  
handle

netemで作成したクラス名を指定。 下記のように連結される

  • root=>1: => 1:1 => 10:
  • root=>1: => 1:2 => 20:
  • root=>1: => 1:3 => 30:
  • root=>1: => 1:4 => デフォルトのfifo disc
delay

遅延させる秒数で3秒、5秒、10秒を選択

遅延用のキューに振り分けるフィルターの作成

遅延用のキューが作成できたのでそれらに振り分けるための条件を作成する

tc filter add dev eth0 parent 1: prio 1 handle 1 fw flowid 1:1
tc filter add dev eth0 parent 1: prio 1 handle 2 fw flowid 1:2
tc filter add dev eth0 parent 1: prio 1 handle 3 fw flowid 1:3
prio

優先度の設定でフィルターは優先度の高いものを上から順に実行していくが、 今回はMARK指定のみで複数の条件が同時に当てはまることがないので全てに1を指定

handle

MARK番号の指定でMARK1, 2, 3を使用する (netemの時指定したhandleではクラス指定だったがこちらはMARK番号となることに注意)

iptablesの設定

TCの設定ができたのであとはiptablesで条件を指定してMARKをつけることにより簡単に遅延が完了

例えばDNSTCPフォールバックの3ウェイハンドシェイクのSYN,ACK応答のみ5秒遅延させたい場合は

iptables -A OUTPUT -p tcp --tcp-flags SYN,ACK SYN,ACK --sport 53 -j MARK --set-mark 2

テスト等で遅延させる秒数や条件が複数あり切り替えたい場合はユーザ定義チェインを作っておいて切り替えたり、 iptables-save&iptables-restoreでファイル経由にするほうがよい。

参考にさせていただいたサイト

論理ボリュームの縮小

縮小

アンマウント ↓ ファイルシステムの縮小 ↓ 論理ボリュームの縮小 ↓ マウント

という手順を取る必要がある

アンマウント

#lvdisplay
  --- Logical volume ---
  LV Name                /dev/VolGroup00/mylv
  VG Name                VolGroup00
  LV UUID                lK6lM3-lZ1X-0vtK-HaPd-xkMj-e403-zeTRHc
  LV Write Access        read/write
  LV Status              available
  # open                 1
  LV Size                2.91 GB
  Current LE             93
  Segments               1
  Allocation             inherit
  Read ahead sectors     auto
  - currently set to     256
  Block device           253:2

このボリュームを2GBに縮小する

umount

umount /mnt/test/

/mnt/testにマウントしていたので単純にumountでマウントを解除する

ファイルシステムの縮小

# resize2fs /dev/VolGroup00/mylv 2G
resize2fs 1.39 (29-May-2006)
Please run 'e2fsck -f /dev/VolGroup00/mylv' first.

resizeしようとするとe2fsckしてからにしてくれと言われるので まずチェックを行う

# e2fsck -f /dev/VolGroup00/mylv
# resize2fs /dev/VolGroup00/mylv 2G

ファイルシステム上は縮小されたので この状態でmountを行うと

/dev/mapper/VolGroup00-mylv
                      2.0G   69M  1.9G   4% /mnt/test

2Gになっているが

  Free  PE / Size       0 / 0 

ボリュームグループ上はサイズが増えていない

論理ボリュームの縮小

拡張を行うには lvextend 縮小を行うには lvreduce を使用する

# lvreduce -L 2G /dev/VolGroup00/mylv 
  WARNING: Reducing active logical volume to 2.00 GB
  THIS MAY DESTROY YOUR DATA (filesystem etc.)
Do you really want to reduce mylv? [y/n]: y
  Reducing logical volume mylv to 2.00 GB
  Logical volume mylv successfully resized

これでVolumeGroupの使用領域が解放されます。

# vgdisplay
Free  PE / Size       29 / 928.00 MB

gauss-jordan法

perl アルゴリズム
#!/usr/bin/perl
use strict;
use warnings;
use Data::Dumper;

my $a = [
    [1, -1, 1],
    [2, 1, -3],
    [3, 2, -1],
];

my $b = [
    [-5],
    [19],
    [16],
];

gauss_jordan($a, $b);

print Dumper($a);
print Dumper($b);

sub gauss_jordan {
    my ($a, $b) = @_;

    my $n = scalar @$a;
    my $m = scalar @{$b->[0]};

    my @check;
    my @switch;
    for my $i ( 0.. $n - 1 ) {

        # まだ使用していない行の最大値を取得する
        my $max_row;
        my $max_col;

        for my $j ( 0.. $n - 1 ) { # 行

            if ( $check[$j] ) { next };
            for my $k ( 0.. $n - 1 ) { # 列

                if ( $check[$k] ) { next };

                if ( !defined $max_row  || abs($a->[$max_row][$max_col]) < abs($a->[$j][$k]) ) {
                    $max_row = $j;
                    $max_col = $k;
                }
            }
        }

        $check[$max_col] = 1;

        if ( $max_row != $max_col ) {
            # 行入れ替え
            ($a->[$max_col], $a->[$max_row]) = ($a->[$max_row], $a->[$max_col]);
            ($b->[$max_col], $b->[$max_row]) = ($b->[$max_row], $b->[$max_col]);
            push @switch, [$max_col, $max_row];
        }

        # 対象行の処理
        my $pivnv = 1 / $a->[$max_col][$max_col];

        $a->[$max_col][$max_col] = 1;

        foreach ( @{$a->[$max_col]} ) {
            $_ *= $pivnv;
        }

        foreach ( @{$b->[$max_col]} ) {
            $_ *= $pivnv;
        }

        # 対象以外の行
        foreach my $l ( 0.. $n - 1 ) {
            next if ( $l == $max_col );

            my $dum = $a->[$l][$max_col]; # $a->[$l][$max_col] / 1

            $a->[$l][$max_col] = 0;

            foreach my $p ( 0.. $n - 1 ) {
                $a->[$l][$p] -= $a->[$max_col][$p] * $dum;
            }

            foreach my $p ( 0.. $m - 1 ) {
                $b->[$l][$p] -= $b->[$max_col][$p] * $dum;
            }
        }
    }
    for my $c (@switch) {
        foreach my $i (0.. $n - 1) {
            my $tmp = $a->[$i][$c->[0]];
            $a->[$i][$c->[0]] = $a->[$i][$c->[1]];
            $a->[$i][$c->[1]] = $tmp;
        }
    }
}

NUMERICAL RECIPED in Cのをperlで書き直してみた。 中学とかで習う連立方程式を解くやり方をそのままプログラムにした方法

bには結果が返り、 計算に必要なくなった列を単位行列として変換していくためaには逆行列が返る。

内部探索(interpolation search)

perl アルゴリズム

データが均等なランダムの場合loglogNの速度になるため、 binary searchより効率がよくなるが、 一つの計算時間は増えるため、データがかなり大きい場合にのみ有効。

やってることは、binary searchのメディアンの選び方を現在のデータから 有効そうな位置を取得してるだけ。

http://en.wikipedia.org/wiki/Interpolation_search

perlの実装

my @a = map { int (rand() * 100) } 0..99;
@a = sort { $a <=> $b } @a;
my $i = find(\@a, 50);

if ( $i ) {
    print "============find===============\n";
    print "index: $i\n";
    print "value: $a[$i]\n";
    print "===============================\n";
} else {
    print "============not find===============\n";
}



# interpolation search
# 内挿探索

sub find {
    my ($a, $v) = @_;

    my $l = 0;
    my $r = $#$a;

    while ( $a[$l] <= $v && $a[$r] >= $v ) {
        my $mid = int($l + ($v - $a[$l]) *  ($r - $l) / ( $a->[$r] - $a->[$l] ));

        if ( $a[$mid] > $v ) {
            $r = $mid - 1;
        }elsif ( $a[$mid] < $v ) {
            $l = $mid + 1;
        }else{
            return $mid;
        }
        print $l. ":". $r. "\n";
    }

    return undef;
}

グラフ

アルゴリズム perl

グラフの内部表現で通常c言語だと エッジの数によって隣接行列か隣接リストのどっちかで表すが、

メモリと速度をあまり気にしない場合perlだと ハッシュを使った下記のような形で作るのが簡単。

my $adj;

sub add_connect {
    my ($a, $b) = @_;

    $adj->{$a}->{$b} = 1;
}

sub del_connect {
    my ($a, $b) = @_;

    $adj->{$a}->{$b} = 0;
}

sub to_connects {
    my ($node) = @_;
    return grep { $adj->{$node}->{$_} } keys %{$adj->{$node}};
}

sub from_connects {
     my ($node) = @_;
     return grep { $adj->{$_}->{$node} } keys %$adj;
}

dfsとbfsだとこんな感じ。

# dfs(深さ優先探索)
my %mark;
sub dfs_search {
    my ($node) = @_;
    return 0 if $mark{$node}++;

    print $node. "|";

    foreach my $next_node ( to_connects($node) ) {
        dfs_search($next_node);
    }
    return 1;
}
# bfs(幅優先探索)
my %mark;
while (@a) {
    my $node = shift @a;

    next if ( $mark{$node}++ );
    print $node. "|";

    foreach my $next_node ( to_connects($node) ) {
        push @a, $next_node;
    }
}