2017-01-14

パケット遅延

ネットワーク 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でファイル経由にするほうがよい。

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

2015-06-28

論理ボリュームの縮小

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

2015-04-06

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には逆行列が返る。

2015-01-13

内部探索(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;
}

2014-12-17

グラフ

アルゴリズム 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;
    }
}

2014-12-17

ヒープ木

アルゴリズム perl

順位キューで挿入と探索をlogNで行いたいときに使う

二分ヒープ - Wikipedia

挿入のときは最下層の一番左に挿入して補正取り出すときは一番上から取得 => 最下層の一番左にあったものを上に付けて補正

を行うので常に完全バランスが取れて、左からノードが埋まっていく。

perlでのheap実装

# heap木

my @a = (7,  2, 3);
foreach ( @a ) {
    heap_insert($_);
}

my $ret;

while ( $ret = heap_remove() ) {
    print $ret. "\n";
}

my @heap;

sub heap_remove {

    return unless ( @heap );

    if ( @heap == 1 ) {
        return pop @heap;
    }

    my $top = $heap[0];
    $heap[0] = pop @heap;
    top_down(0);

    return $top;
}

sub heap_insert {
    my ($data) = @_;
    my $n = scalar @heap;
    $heap[$n] = $data;

    bottom_up($n);
}

sub bottom_up {
    my ($index) = @_;

    return if ( $index == 0 );

    my $parent_index = int ( ( $index + 1 ) / 2 ) - 1;
     if ( $heap[$index] > $heap[$parent_index] ) {

         @heap[$index, $parent_index] = @heap[$parent_index, $index]; # swap
         bottom_up($parent_index);
     }
 }

 sub top_down {
     my ($index) = @_;

     my $n = scalar @heap;

     my $l = ($index + 1) * 2 - 1;
     my $r = $l + 1;

     if ( $l < $n && $heap[$l] > $heap[$index] ) {
         @heap[$l, $index] = @heap[$index, $l];
         top_down($l);
     } elsif ( $r < $n && $heap[$r] > $heap[$index] ) {
         @heap[$r, $index] = @heap[$index, $r];
         top_down($r);
     }
 }

データは配列として格納する。一つ上のノードにアクセスする場合は /2 一つ下のノードにアクセスする場合は *2 をする。

2014-10-05

アセンブラからELF

アセンブラ

64bitに以降したら

nasm -f elf test.asm
ld test.o

としていたアセンブラから実行ファイルへの変換が動かなくなっていた

could not read symbols: File in wrong format

の様なエラーが出る。どうやら-m elf_i386を指定しないといけないらしい。

#!/bin/sh

if [ ! $# -eq 1 ]; then
        echo "please set asmfile"
        exit 1
fi

if [ ! -f $1 ]; then
        echo "file not fount" 1>&2
        exit 1
fi

BASE_NAME=${1%.*}

nasm -f elf ${1} -o ${BASE_NAME}.o
ld -e main -m elf_i386 -o ${BASE_NAME} ${BASE_NAME}.o

rm -rf ${BASE_NAME}.o

こんな感じに修正した。

totofugaのブログ

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

パケット遅延

TCの設定

prioキュー設定

bands

priomap

遅延用のキューを作成

handle

delay

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

prio

handle

iptablesの設定

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

論理ボリュームの縮小

縮小

アンマウント

umount

ファイルシステムの縮小

論理ボリュームの縮小

gauss-jordan法

内部探索(interpolation search)

グラフ

ヒープ木

perlでのheap実装

アセンブラからELF