totofugaのブログ

ネットワークとかc言語、perlの話。

Unboundのtarget_fetch_policy

DNS unbound

target-fetch-policyについて

マニュアルを見ても「ターゲット アドレスを日和見的に取ってくる」 となってよくわからなかったのでソースから調べてみた。

結果

設定値

デフォルトは”3 2 1 0 0" 数字の並びは左から深度に対応している 深度は委任レコードを返された時に外部名だった場合外部名をたどる回数となる 外部名探索中にさらに外部名が見つかった場合には深度２となり左から２番目の数値が参照される。

数字はいくつの外部名を同時に探すかに対応する。 Unboundでは複数の外部名があった場合同時に問い合わせを行い、レスポンスが速いものが使用される。

0と1の違い

外部名しか存在しない場合は0と１に違いはない 外部名と内部名が混在していた場合、0では内部名のアドレスに対して問い合わせるのと同時に 外部名に対しても１つ問い合わせを行う

-1

-1が指定されていた場合にはすべての外部名の探索が行われる

深度より多い問い合わせ

深度 -1以上の問い合わせは行わないようになっている 例えば”3 1”と指定された場合始めの外部名では３つに対して問い合わせを行うが さらに外部名に出会った時には処理を終了する。

何故-1なのかはわからなかった。

ソースコード

コンフィグから値の設定

iter_init
    iter_apply_cfg
        read_fetch_policy

max_dependency_depthとtarget_fetch_policyに使用している max_dependency_depthには設定した個数-1が入る

使用場所

processQueryTargets
    query_for_targets

processQueryTargetsの中はだいたい以下のようになっている

// 現在の深度の問い合わせ個数取得
tf_policy = ie->target_fetch_policy[iq->depth]; 
if(iq->caps_fallback) {
    // 0x20エンコードの時は強制的に全ての外部名をたどる
    query_for_targets(qstate, iq, ie, id, -1, &extra) 
    ....
} else if(tf_policy != 0) {
    // それ以外の場合には問い合わせ個数分取得
    query_for_targets(qstate, iq, ie, id, tf_policy, &extra); 
    ....
}
// すでにアドレスが分かっている問い合わせ先を取得(内部名やキャッシュされている場合ここで見つけられる)
target = iter_server_selection(...) 

if ( !target ) {
    // 問い合わせ先がなければ一つだけ問い合わせる 
    query_for_targets(qstate, iq, ie, id, 1, &extra); 
}

実験

unboundに付属しているtestboundで試すことができる

server:
    target-fetch-policy: "2 0"
    do-ip6: no

stub-zone:
    name: "."
    stub-addr: 0.0.0.1

CONFIG_END

SCENARIO_BEGIN my test

    RANGE_BEGIN 0 100
        ADDRESS 0.0.0.1

        ENTRY_BEGIN
            MATCH opcode qtype qname
            ADJUST copy_id
            REPLY QR NOERROR
            SECTION QUESTION
                . IN NS
            SECTION ANSWER
                . IN NS A.ROOTSERVERS.NET.
            SECTION ADDITIONAL
                A.ROOTSERVERS.NET. IN A 0.0.0.1
        ENTRY_END

        ENTRY_BEGIN
            MATCH opcode qtype qname
            ADJUST copy_id
            REPLY QR NOERROR
            SECTION QUESTION
                test.jp. IN A
            SECTION AUTHORITY
                jp. IN NS b.jp
                jp. IN NS a.jp
                jp. IN NS c.jp
                jp. IN NS d.jp
            SECTION ADDITIONAL
                d.jp IN A 1.1.1.1
        ENTRY_END
    RANGE_END

    STEP 1 QUERY
        ENTRY_BEGIN
            REPLY RD
            SECTION QUESTION
                test.jp. IN A
        ENTRY_END

    STEP 10 NOTHING

SCENARIO_END

実行結果の一部

[0] unbound[43053:0] info: pending msg;; ->>HEADER<<- opcode: QUERY, rcode: NOERROR, id: 0
;; flags: cd ; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 1 
;; QUESTION SECTION:
b.jp.   IN      A

;; ANSWER SECTION:

;; AUTHORITY SECTION:

;; ADDITIONAL SECTION:
; EDNS: version: 0; flags: do ; udp: 4096
;; MSG SIZE  rcvd: 33

[0] unbound[43053:0] debug: pending to 1.1.1.1 port 53
[0] unbound[43053:0] info: pending msg;; ->>HEADER<<- opcode: QUERY, rcode: NOERROR, id: 0
;; flags: cd ; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 1 
;; QUESTION SECTION:
a.jp.   IN      A

;; ANSWER SECTION:

;; AUTHORITY SECTION:

;; ADDITIONAL SECTION:
; EDNS: version: 0; flags: do ; udp: 4096
;; MSG SIZE  rcvd: 33

[0] unbound[43053:0] debug: pending to 1.1.1.1 port 53
[0] unbound[43053:0] info: pending msg;; ->>HEADER<<- opcode: QUERY, rcode: NOERROR, id: 0
;; flags: ; QUERY: 1, ANSWER: 0, AUTHORITY: 0, ADDITIONAL: 1 
;; QUESTION SECTION:
test.jp.        IN      A

;; ANSWER SECTION:

;; AUTHORITY SECTION:

;; ADDITIONAL SECTION:
; EDNS: version: 0; flags: do ; udp: 4096
;; MSG SIZE  rcvd: 36

設定が深度１の設定が２なので2件の外部名問い合わせと内部名のアドレス(1.1.1.1)に問い合わせているのが確認できる。

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

unbound c言語 DNS

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言語 DNS

処理内容

権威から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の３つには遅延を行いたいので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をつけることにより簡単に遅延が完了

例えばDNSのTCPフォールバックの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でファイル経由にするほうがよい。

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

論理ボリュームの縮小

linux

縮小

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

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

アンマウント

#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;
}