ToRapture's Blog

A Programmer

0%

Posted on Edited on Disqus:

Do some experiment about UDP by Python3 and netstat.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# coding: utf-8

import socket

from IPython import embed


def main():
    sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    embed()
    sock.close()


if __name__ == '__main__':
    main()

A and B start

A: 

1
2
3
4
5
6
7
8
9
10
11
$ python3 client.py
Python 3.5.2 (default, Oct  8 2019, 13:06:37)
Type "copyright", "credits" or "license" for more information.

IPython 2.4.1 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]:

B: 

1
2
3
4
5
6
7
8
9
10
11
$ python3 client.py
Python 3.5.2 (default, Oct  8 2019, 13:06:37)
Type "copyright", "credits" or "license" for more information.

IPython 2.4.1 -- An enhanced Interactive Python.
?         -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help      -> Python's own help system.
object?   -> Details about 'object', use 'object??' for extra details.

In [1]:
1
2
3
$ netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State

A bind

A: 

1
In [1]: sock.bind(('localhost', 10001))
1
2
3
4
$ netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
udp        0      0 localhost:10001         *:*

B send to A

B: 

1
2
In [1]: sock.sendto(b'hello world', ('localhost', 10001))
Out[1]: 11

A: 

1
2
In [2]: sock.recvfrom(1024)
Out[2]: (b'hello world', ('127.0.0.1', 42616))

1
2
3
4
5
$ netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
udp      768      0 localhost:10001         *:*
udp        0      0 *:42616                 *:*

A send to B

A: 

1
2
In [3]: sock.sendto(b'This is a response.', ('127.0.0.1', 42616))
Out[3]: 19

B: 

1
2
In [2]: sock.recvfrom(1024)
Out[2]: (b'This is a response.', ('127.0.0.1', 10001))

1
2
3
4
5
$ netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
udp        0      0 localhost:10001         *:*
udp        0      0 *:42616                 *:*

B connect to A

B: 

1
In [4]: sock.connect(('127.0.0.1', 10001))

1
2
3
4
5
$ netstat -au
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
udp        0      0 localhost:10001         *:*
udp        0      0 localhost:42616         localhost:10001         ESTABLISHED

A: 

1
2
In [4]: sock.sendto(b'This is another response.', ('127.0.0.1', 42616))
Out[4]: 25

B: 

1
2
In [5]: sock.recvfrom(1024)
Out[5]: (b'This is another response.', ('127.0.0.1', 10001))

C: 

1
2
3
4
In [1]: sock.bind(('127.0.0.1', 10010))

In [2]: sock.sendto(b'This is a response from C.', ('127.0.0.1', 42616))
Out[2]: 26

B: 

1
2
In [7]: sock.recvfrom(1024)
blocked
After B connected to A, B will not receive packets from any endpoint other than A.

Posted on Edited on Disqus:

Find max packet size

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# coding: utf-8

import socket


def find_max_udp_packet_size():
    sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    max_sz = 0
    l, r = 0, 65535 - 8 - 20
    while l <= r:
        mid = int((l + r) / 2)
        ok = True

        try:
            sock.sendto(b'A' * mid, ('localhost', 9))
        except socket.error:
            ok = False

        if ok:
            max_sz = mid
            l = mid + 1
        else:
            r = mid - 1

    return max_sz


def main():
    max_sz = find_max_udp_packet_size()
    print('max_sz = %s' % max_sz)


if __name__ == '__main__':
    main()

I used the code above to find the max size of a UDP packet size by default configuration. The result on my computer is: 

1
2
3
4
5
6
$ uname -v
Darwin Kernel Version 19.2.0: Sat Nov  9 03:47:04 PST 2019; root:xnu-6153.61.1~20/RELEASE_X86_64
$ python3 --version
Python 3.6.4
$ python3 udp_packet_size.py
max_sz = 9216

More test

Use the code below to test. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# coding: utf-8

import socket

from IPython import embed


def main():
    sock = socket.socket(socket.AF_INET, socket.SOCK_DGRAM)
    embed()
    sock.close()


if __name__ == '__main__':
    main()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
In [1]: sock.bind(('localhost', 10001))

In [2]: receiver = ('localhost', 10002)

In [3]: sock.sendto(b'01234567', receiver)
Out[3]: 8

In [4]: sock.sendto(b'01234567', receiver)
Out[4]: 8

In [5]: sock.sendto(b'01234567', receiver)
Out[5]: 8

In [6]: sock.sendto(b'01234567', receiver)
Out[6]: 8
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

In [1]: sock.bind(('localhost', 10002))

In [2]: receiver = ('localhost', 10001)

In [3]: print(sock.recvfrom(1024))
(b'01234567', ('127.0.0.1', 10001))

In [4]: print(sock.recvfrom(4))
(b'0123', ('127.0.0.1', 10001))

In [5]: print(sock.recvfrom(4))
(b'0123', ('127.0.0.1', 10001))

In [6]: print(sock.recvfrom(4))
(b'0123', ('127.0.0.1', 10001))

In [7]: print(sock.recvfrom(4))

We can see that if the bufsize is smaller the length of the packet received, will only read bufsize bytes of the received data, and the rest of that packet will not be returned in subsequent reads.

Posted on Edited on Disqus:

UDP headers

Headers for computing checksum

The checksum computation is similar to the Internet checksum computation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

unsigned short checksum(const vector<unsigned short> &v) {
    unsigned int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        sum += v[i];
    }
    while (sum > 0xFFFF) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }
    return ~sum;
}

int main(int argc, char **argv) {
    vector<unsigned short> vec{
            // UDP pseudo-header
            0x0a01, 0xbf44, // source IP address
            0x0a02, 0x0002, // destination IP address
            0x0011 /* 1 byte zero and 1 byte protocol number */, 0x0023, // UDP length

            // UDP header
            0xc183, 0x0035, // source port number and destination port number
            0x0000, 0x0023, // checksum and UDP length

            // data
            0x06b0, 0x0100,
            0x0001, 0x0000,
            0x0000, 0x0000,
            0x0562, 0x6169,
            0x6475, 0x0363,
            0x6f6d, 0x0000,
            0x0100, 0x0100, // the length of this UDP packet is odd and the last short is 0x01, so we should pad 1 byte zero.

    };
    unsigned short sum = checksum(vec);

    printf("checksum = 0x%X\n", sum);
    assert(sum == 0x22E4);

    vec[8] = sum;

    sum = checksum(vec);
    assert(sum == 0);
    printf("0x%X\n", sum);

    return 0;
}

Posted on Edited on Disqus:

Command

https://linux.die.net/man/8/traceroute

This program attempts to trace the route an IP packet would follow to some internet host by launching probe packets with a small ttl (time to live) then listening for an ICMP "time exceeded" reply from a gateway. We start our probes with a ttl of one and increase by one until we get an ICMP "port unreachable" (or TCP reset), which means we got to the "host", or hit a max (which defaults to 30 hops). Three probes (by default) are sent at each ttl setting and a line is printed showing the ttl, address of the gateway and round trip time of each probe. The address can be followed by additional information when requested. If the probe answers come from different gateways, the address of each responding system will be printed. If there is no response within a 5.0 seconds (default), an "*" (asterisk) is printed for that probe.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
$ traceroute iqiyi.com
traceroute to iqiyi.com (111.206.13.64), 30 hops max, 60 byte packets
 1  * * *
 2  11.220.36.9 (11.220.36.9)  6.906 ms 11.220.37.73 (11.220.37.73)  5.219 ms 11.220.36.9 (11.220.36.9)  7.193 ms
 3  * * *
 4  10.54.136.253 (10.54.136.253)  0.419 ms 11.217.38.218 (11.217.38.218)  0.366 ms 10.54.137.5 (10.54.137.5)  7.548 ms
 5  119.38.215.78 (119.38.215.78)  1.215 ms 42.120.253.1 (42.120.253.1)  1.148 ms 117.49.35.198 (117.49.35.198)  1.040 ms
 6  116.251.113.145 (116.251.113.145)  1.798 ms 42.120.239.249 (42.120.239.249)  2.112 ms 116.251.113.149 (116.251.113.149)  2.287 ms
 7  157.255.237.149 (157.255.237.149)  5.927 ms  5.809 ms  5.758 ms
 8  120.80.99.17 (120.80.99.17)  5.375 ms 120.80.98.177 (120.80.98.177)  4.409 ms 120.80.98.181 (120.80.98.181)  6.039 ms
 9  221.4.0.181 (221.4.0.181)  9.088 ms  8.350 ms  8.086 ms
10  219.158.7.21 (219.158.7.21)  35.774 ms  35.622 ms 219.158.7.17 (219.158.7.17)  39.304 ms
11  124.65.194.34 (124.65.194.34)  41.728 ms 202.96.12.26 (202.96.12.26)  40.799 ms 125.33.186.50 (125.33.186.50)  38.370 ms
12  202.106.34.98 (202.106.34.98)  72.417 ms  67.925 ms  66.970 ms
13  bt-211-070.bta.net.cn (202.106.211.70)  39.312 ms * *
14  111.206.13.64 (111.206.13.64)  39.598 ms  36.527 ms  39.293 ms

Simulate by ping

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
$ ping -c2 -W 1.5 -t 1 iqiyi.com
PING iqiyi.com (111.206.13.64) 56(84) bytes of data.

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, 100% packet loss, time 1007ms

$ ping -c2 -W 1.5 -t 2 iqiyi.com
PING iqiyi.com (111.206.13.63) 56(84) bytes of data.
From 11.220.36.73 icmp_seq=1 Time to live exceeded
From 11.220.36.73 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 3 iqiyi.com
PING iqiyi.com (111.206.13.61) 56(84) bytes of data.
From 11.220.37.130 icmp_seq=1 Time to live exceeded
From 11.220.37.130 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 4 iqiyi.com
PING iqiyi.com (111.206.13.64) 56(84) bytes of data.
From 10.54.140.5 icmp_seq=1 Time to live exceeded
From 10.54.140.5 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 5 iqiyi.com
PING iqiyi.com (111.206.13.63) 56(84) bytes of data.
From 117.49.35.62 icmp_seq=1 Time to live exceeded
From 117.49.35.62 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 6 iqiyi.com
PING iqiyi.com (111.206.13.65) 56(84) bytes of data.
From 42.120.242.229 icmp_seq=1 Time to live exceeded
From 42.120.242.229 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1000ms

--------

$ ping -c2 -W 1.5 -t 12 iqiyi.com
PING iqiyi.com (111.206.13.66) 56(84) bytes of data.
From 123.126.0.46 icmp_seq=1 Time to live exceeded
From 123.126.0.46 icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 13 iqiyi.com
PING iqiyi.com (111.206.13.62) 56(84) bytes of data.
From bt-211-042.bta.net.cn (202.106.211.42) icmp_seq=1 Time to live exceeded
From bt-211-042.bta.net.cn (202.106.211.42) icmp_seq=2 Time to live exceeded

--- iqiyi.com ping statistics ---
2 packets transmitted, 0 received, +2 errors, 100% packet loss, time 1001ms

$ ping -c2 -W 1.5 -t 14 iqiyi.com
PING iqiyi.com (111.206.13.61) 56(84) bytes of data.
64 bytes from 111.206.13.61: icmp_seq=1 ttl=52 time=36.7 ms
64 bytes from 111.206.13.61: icmp_seq=2 ttl=52 time=36.7 ms

--- iqiyi.com ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 1000ms
rtt min/avg/max/mdev = 36.726/36.737/36.748/0.011 ms

Posted on Edited on Disqus:

From: TCP/IP Illustrated, Volume 1: The Protocols.

IHL

The Internet Header Length (IHL) field is the number of 32-bit words in the IPv4 header, including any options. Because this is also a 4-bit field, the IPv4 header is limited to a maximum of fifteen 32-bit words or 60 bytes. ### Total Length The Total Length field is the total length of the IPv4 datagram in bytes. ### Protocol The Protocol field in the IPv4 header contains a number indicating the type of data found in the payload portion of the datagram. The most common values are 17 (for UDP) and 6 (for TCP).

Posted on Edited on Disqus:

ifconfig

https://linux.die.net/man/8/ifconfig

Ifconfig is used to configure the kernel-resident network interfaces. It is used at boot time to set up interfaces as necessary. After that, it is usually only needed when debugging or when system tuning is needed.

If no arguments are given, ifconfig displays the status of the currently active interfaces. If a single interface argument is given, it displays the status of the given interface only; if a single -a argument is given, it displays the status of all interfaces, even those that are down. Otherwise, it configures an interface.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
$ ifconfig
eth0      Link encap:Ethernet  HWaddr 00:16:3e:10:27:9e
          inet addr:172.16.62.130  Bcast:172.16.63.255  Mask:255.255.192.0
          UP BROADCAST RUNNING MULTICAST  MTU:1500  Metric:1
          RX packets:10188512 errors:0 dropped:0 overruns:0 frame:0
          TX packets:10123903 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1000
          RX bytes:1554718007 (1.5 GB)  TX bytes:15002653955 (15.0 GB)

lo        Link encap:Local Loopback
          inet addr:127.0.0.1  Mask:255.0.0.0
          UP LOOPBACK RUNNING  MTU:65536  Metric:1
          RX packets:5561316 errors:0 dropped:0 overruns:0 frame:0
          TX packets:5561316 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:1
          RX bytes:720550645 (720.5 MB)  TX bytes:720550645 (720.5 MB)

$ ifconfig <interface> up
$ ifconfig <interface> down

route

https://linux.die.net/man/8/route

Route manipulates the kernel's IP routing tables. Its primary use is to set up static routes to specific hosts or networks via an interface after it has been configured with the ifconfig(8) program.

When the add or del options are used, route modifies the routing tables. Without these options, route displays the current contents of the routing tables.

https://superuser.com/a/580674

The Gateway column identifies the defined gateway for the specified network. An asterisk (*) appears in this column if no forwarding gateway is needed for the network.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
$ route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.16.63.253   0.0.0.0         UG    0      0        0 eth0
172.16.0.0      *               255.255.192.0   U     0      0        0 eth0

$ host baidu.com
baidu.com has address 220.181.38.148
baidu.com has address 39.156.69.79
baidu.com mail is handled by 15 mx.n.shifen.com.
baidu.com mail is handled by 20 mx50.baidu.com.
baidu.com mail is handled by 10 mx.maillb.baidu.com.
baidu.com mail is handled by 20 jpmx.baidu.com.
baidu.com mail is handled by 20 mx1.baidu.com.

$ ip route get 220.181.38.148
220.181.38.148 via 172.16.63.253 dev eth0  src 172.16.62.130
    cache

$ ping -c1 220.181.38.148
PING 220.181.38.148 (220.181.38.148) 56(84) bytes of data.
64 bytes from 220.181.38.148: icmp_seq=1 ttl=49 time=36.6 ms

--- 220.181.38.148 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 36.620/36.620/36.620/0.000 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
$ sudo route add 220.181.38.148 eth0

$ route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.16.63.253   0.0.0.0         UG    0      0        0 eth0
172.16.0.0      *               255.255.192.0   U     0      0        0 eth0
220.181.38.148  *               255.255.255.255 UH    0      0        0 eth0

$ ip route get 220.181.38.148
220.181.38.148 dev eth0  src 172.16.62.130
    cache

$ ping -c1 220.181.38.148
PING 220.181.38.148 (220.181.38.148) 56(84) bytes of data.
From 172.16.62.130 icmp_seq=1 Destination Host Unreachable

--- 220.181.38.148 ping statistics ---
1 packets transmitted, 0 received, +1 errors, 100% packet loss, time 0ms

$ sudo route del 220.181.38.148

$ route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.16.63.253   0.0.0.0         UG    0      0        0 eth0
172.16.0.0      *               255.255.192.0   U     0      0        0 eth0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
$ sudo route add 220.181.38.148 gw 172.16.63.253

$ route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.16.63.253   0.0.0.0         UG    0      0        0 eth0
172.16.0.0      *               255.255.192.0   U     0      0        0 eth0
220.181.38.148  172.16.63.253   255.255.255.255 UGH   0      0        0 eth0

$ ip route get 220.181.38.148
220.181.38.148 via 172.16.63.253 dev eth0  src 172.16.62.130
    cache

$ ping -c1 220.181.38.148
PING 220.181.38.148 (220.181.38.148) 56(84) bytes of data.
64 bytes from 220.181.38.148: icmp_seq=1 ttl=49 time=36.5 ms

--- 220.181.38.148 ping statistics ---
1 packets transmitted, 1 received, 0% packet loss, time 0ms
rtt min/avg/max/mdev = 36.538/36.538/36.538/0.000 ms

$ sudo route del 220.181.38.148

$ route
Kernel IP routing table
Destination     Gateway         Genmask         Flags Metric Ref    Use Iface
default         172.16.63.253   0.0.0.0         UG    0      0        0 eth0
172.16.0.0      *               255.255.192.0   U     0      0        0 eth0

iptables

https://linux.die.net/man/8/iptables

iptables - administration tool for IPv4 packet filtering and NAT

default

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
root@nenuoj$ iptables -L -v --line-numbers
Chain INPUT (policy ACCEPT 290 packets, 18937 bytes)
num   pkts bytes target     prot opt in     out     source               destination

Chain FORWARD (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination

Chain OUTPUT (policy ACCEPT 202 packets, 41678 bytes)
num   pkts bytes target     prot opt in     out     source               destination

torapture@rapture$ ping -c4 D.D.D.D
PING D.D.D.D (D.D.D.D) 56(84) bytes of data.
64 bytes from D.D.D.D: icmp_seq=1 ttl=45 time=192 ms
64 bytes from D.D.D.D: icmp_seq=2 ttl=45 time=180 ms
64 bytes from D.D.D.D: icmp_seq=3 ttl=45 time=194 ms
64 bytes from D.D.D.D: icmp_seq=4 ttl=45 time=180 ms

--- D.D.D.D ping statistics ---
4 packets transmitted, 4 received, 0% packet loss, time 2998ms
rtt min/avg/max/mdev = 180.029/186.853/194.475/6.724 ms

drop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
root@nenuoj$ iptables -A INPUT -s S.S.S.S -j DROP

torapture@rapture$ ping -c4 D.D.D.D
PING D.D.D.D (D.D.D.D) 56(84) bytes of data.

--- D.D.D.D ping statistics ---
4 packets transmitted, 0 received, 100% packet loss, time 3024ms

root@nenuoj$ iptables -L -v --line-numbers
Chain INPUT (policy ACCEPT 54 packets, 3339 bytes)
num   pkts bytes target     prot opt in     out     source               destination
1        4   336 DROP       all  --  any    any     S.S.S.S       anywhere

Chain FORWARD (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination

Chain OUTPUT (policy ACCEPT 44 packets, 13276 bytes)
num   pkts bytes target     prot opt in     out     source               destination

reject tcp:80

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root@nenuoj$ iptables -A INPUT -s S.S.S.S -p tcp --destination-port 80 -j REJECT

torapture@rapture$ curl D.D.D.D
curl: (7) Failed to connect to D.D.D.D port 80: Connection refused

root@nenuoj$ iptables -L -v --line-numbers
Chain INPUT (policy ACCEPT 91 packets, 5449 bytes)
num   pkts bytes target     prot opt in     out     source               destination
1        1    60 REJECT     tcp  --  any    any     S.S.S.S       anywhere             tcp dpt:http reject-with icmp-port-unreachable

Chain FORWARD (policy ACCEPT 0 packets, 0 bytes)
num   pkts bytes target     prot opt in     out     source               destination

Chain OUTPUT (policy ACCEPT 70 packets, 14548 bytes)
num   pkts bytes target     prot opt in     out     source               destination

ip

https://linux.die.net/man/8/ip

ip - show / manipulate routing, devices, policy routing and tunnels

address

1
2
3
4
5
6
7
8
9
root@nenuoj$ ip addr
1: lo: <LOOPBACK,UP,LOWER_UP> mtu 65536 qdisc noqueue state UNKNOWN group default qlen 1
    link/loopback 00:00:00:00:00:00 brd 00:00:00:00:00:00
    inet 127.0.0.1/8 scope host lo
       valid_lft forever preferred_lft forever
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP group default qlen 1000
    link/ether 00:16:3e:10:27:9e brd ff:ff:ff:ff:ff:ff
    inet 172.16.62.130/18 brd 172.16.63.255 scope global eth0
       valid_lft forever preferred_lft forever
1
2
3
root@nenuoj$ ip link show eth0
2: eth0: <BROADCAST,MULTICAST,UP,LOWER_UP> mtu 1500 qdisc pfifo_fast state UP mode DEFAULT group default qlen 1000
    link/ether 00:11:22:33:44:55 brd ff:ff:ff:ff:ff:ff

route

1
2
3
root@nenuoj$ ip route
default via 172.16.63.253 dev eth0
172.16.0.0/18 dev eth0  proto kernel  scope link  src 172.16.62.130

netstat

https://linux.die.net/man/8/netstat

netstat - Print network connections, routing tables, interface statistics, masquerade connections, and multicast memberships

List all tcp listening ports

1
2
3
4
5
6
7
8
9
10
11
12
13
root@nenuoj$ netstat -tl
Active Internet connections (only servers)
Proto Recv-Q Send-Q Local Address           Foreign Address         State
tcp        0      0 localhost:32000         *:*                     LISTEN
tcp        0      0 *:27015                 *:*                     LISTEN
tcp        0      0 localhost:mysql         *:*                     LISTEN
tcp        0      0 localhost:11211         *:*                     LISTEN
tcp        0      0 localhost:6379          *:*                     LISTEN
tcp        0      0 *:http                  *:*                     LISTEN
tcp        0      0 *:ssh                   *:*                     LISTEN
tcp        0      0 *:https                 *:*                     LISTEN
tcp        0      0 localhost:1087          *:*                     LISTEN
tcp6       0      0 [::]:http               [::]:*                  LISTEN

List all tcp connections with pid and numericals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
root@nenuoj$ netstat -atnp
Active Internet connections (servers and established)
Proto Recv-Q Send-Q Local Address           Foreign Address         State       PID/Program name
tcp        0      0 127.0.0.1:32000         0.0.0.0:*               LISTEN      972/java
tcp        0      0 0.0.0.0:27015           0.0.0.0:*               LISTEN      1323/Judger
tcp        0      0 127.0.0.1:3306          0.0.0.0:*               LISTEN      1203/mysqld
tcp        0      0 127.0.0.1:11211         0.0.0.0:*               LISTEN      1278/memcached
tcp        0      0 127.0.0.1:6379          0.0.0.0:*               LISTEN      808/redis-server 12
tcp        0      0 0.0.0.0:80              0.0.0.0:*               LISTEN      1270/nginx -g daemo
tcp        0      0 0.0.0.0:22              0.0.0.0:*               LISTEN      1044/sshd
tcp        0      0 0.0.0.0:443             0.0.0.0:*               LISTEN      1270/nginx -g daemo
tcp        0      0 127.0.0.1:1087          0.0.0.0:*               LISTEN      430/privoxy
tcp        0      0 172.16.62.130:38632     100.100.30.25:80        ESTABLISHED 1403/AliYunDun
tcp        0      0 172.16.62.130:80        182.122.161.236:52680   FIN_WAIT2   -
tcp        0      0 172.16.62.130:80        182.122.161.236:52669   FIN_WAIT2   -
tcp        0      0 172.16.62.130:80        182.122.161.236:52686   FIN_WAIT2   -
tcp        0      0 127.0.0.1:32000         127.0.0.1:31000         ESTABLISHED 933/wrapper
tcp        0      0 172.16.62.130:80        182.122.161.236:52681   FIN_WAIT2   -
tcp        0      0 172.16.62.130:80        182.122.161.236:52679   FIN_WAIT2   -
tcp        0      0 127.0.0.1:31000         127.0.0.1:32000         ESTABLISHED 972/java
tcp        0    560 172.16.62.130:22        120.52.147.54:49840     ESTABLISHED 4232/1
tcp        0      0 172.16.62.130:80        182.122.161.236:52682   FIN_WAIT2   -
tcp        0      0 172.16.62.130:80        182.122.161.236:52668   FIN_WAIT2   -
tcp6       0      0 :::80                   :::*                    LISTEN      1270/nginx -g daemo

Display routing

1
2
3
4
5
root@nenuoj$ netstat -r
Kernel IP routing table
Destination     Gateway         Genmask         Flags   MSS Window  irtt Iface
default         172.16.63.253   0.0.0.0         UG        0 0          0 eth0
172.16.0.0      *               255.255.192.0   U         0 0          0 eth0

Show interface infomation

1
2
3
4
5
root@nenuoj$ netstat -i
Kernel Interface table
Iface   MTU Met   RX-OK RX-ERR RX-DRP RX-OVR    TX-OK TX-ERR TX-DRP TX-OVR Flg
eth0       1500 0     40465      0      0 0         33318      0      0      0 BMRU
lo        65536 0     10406      0      0 0         10406      0      0      0 LRU

Posted on Edited on Disqus:

To do an experiment, first capture an IP packet, as we can see the checksum is 0xCAD7. Then we set the checksum field to 0, and calculate the checksum, then we will get 0xCAD7. Set 0xCAD7 to the checksum field and calculate the checksum again, we will get 0 then. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

unsigned short ip_checksum(const vector<unsigned short> &v) {
    unsigned int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        sum += v[i];
    }
    while (sum > 0xFFFF) {
        sum = (sum & 0xFFFF) + (sum >> 16);
    }
    return ~sum;
}

int main(int argc, char **argv) {

    vector<unsigned short> vec{0x4500, 0x0235, 0x0000, 0x4000, 0x4006, 0x0000, 0x0a01, 0xbf44, 0x8ba2, 0x1904};
    unsigned short sum = ip_checksum(vec);
    assert(sum == 0xcad7);
    printf("checksum = 0x%X\n", sum);

    vec[5] = sum;

    sum = ip_checksum(vec);
    assert(sum == 0);
    printf("%X\n", sum);
    return 0;
}

Posted on Edited on Disqus:

Definitions

https://morsmachine.dk/go-scheduler

An OS thread, which is the thread of execution managed by the OS and works pretty much like your standard POSIX thread. In the runtime code, it's called M for machine.

A goroutine, which includes the stack, the instruction pointer and other information important for scheduling goroutines, like any channel it might be blocked on. In the runtime code, it's called a G.

A context for scheduling, which you can look at as a localized version of the scheduler which runs Go code on a single thread. It's the important part that lets us go from a N:1 scheduler to a M:N scheduler. In the runtime code, it's called P for processor.

Codes

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package main

import (
    "fmt"
    "math/rand"
    "net/http"
    "os"
    "sync"
    "time"

    logger "github.com/sirupsen/logrus"
    "github.com/x-cray/logrus-prefixed-formatter"
)

func init() {
    logger.SetFormatter(&prefixed.TextFormatter{
        TimestampFormat: "2006-01-02 15:04:05",
        FullTimestamp:   true,
        ForceFormatting: true,
        DisableColors:   true,
    })
    logger.SetOutput(os.Stdout)
    logger.SetLevel(logger.DebugLevel)
}

func calculate() {
    x := rand.Int()
    for i := 0; i < 1000000; i++ {
        x ^= rand.Int()
        x |= rand.Int()
        x &= rand.Int()
    }
}

func cpuIntenseTask() {
    logger.Infof("[cpuIntenseTask] started")

    wg := sync.WaitGroup{}
    for i := 0; i < 16; i++ {
        go func() {
            wg.Add(1)
            calculate()
            wg.Done()
        }()
    }
    wg.Wait()

    logger.Infof("[cpuIntenseTask] finished")
}

func sleepTask() {
    logger.Infof("[sleepTask] started")

    wg := sync.WaitGroup{}
    for i := 0; i < 64; i++ {
        go func() {
            wg.Add(1)
            time.Sleep(1500 * time.Millisecond)
            wg.Done()
        }()
    }
    wg.Wait()

    logger.Infof("[sleepTask] finished")
}

func httpGet() {
    resp, err := http.Get("https://google.com")
    if err != nil {
        fmt.Printf("httpGet error: %v\n", err)
        return
    }
    logger.Infof("httpGet status: %v", resp.StatusCode)
}

func netTask() {
    logger.Infof("[netTask] started")

    wg := sync.WaitGroup{}
    for i := 0; i < 31200; i++ {
        go func() {
            wg.Add(1)
            httpGet()
            wg.Done()
        }()
    }
    wg.Wait()

    logger.Infof("[netTask] finished")
}

func main() {
    cpuIntenseTask()
    sleepTask()
    netTask()
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
$ go build
$ GODEBUG=schedtrace=1000 ./go-learn 1>learn.out 2>&1
$ cat learn.out | grep -v "error"
SCHED 0ms: gomaxprocs=4 idleprocs=2 threads=4 spinningthreads=1 idlethreads=0 runqueue=0 [1 0 0 0]
[2020-04-17 15:40:53]  INFO cpuIntenseTask: started
[2020-04-17 15:40:53]  INFO cpuIntenseTask: finished
[2020-04-17 15:40:53]  INFO sleepTask: started
[2020-04-17 15:40:53]  INFO sleepTask: finished
[2020-04-17 15:40:53]  INFO netTask: started
SCHED 100ms: gomaxprocs=4 idleprocs=0 threads=10 spinningthreads=0 idlethreads=1 runqueue=19587 [128 25 0 0]
SCHED 204ms: gomaxprocs=4 idleprocs=0 threads=10 spinningthreads=0 idlethreads=1 runqueue=23291 [30 74 33 1]
SCHED 313ms: gomaxprocs=4 idleprocs=0 threads=10 spinningthreads=0 idlethreads=1 runqueue=14978 [77 41 108 125]
SCHED 421ms: gomaxprocs=4 idleprocs=0 threads=11 spinningthreads=0 idlethreads=0 runqueue=6388 [97 74 34 109]
SCHED 529ms: gomaxprocs=4 idleprocs=0 threads=12 spinningthreads=0 idlethreads=1 runqueue=0 [3 6 2 1]
SCHED 638ms: gomaxprocs=4 idleprocs=0 threads=12 spinningthreads=0 idlethreads=1 runqueue=4 [3 0 1 9]
SCHED 743ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=3 runqueue=0 [1 0 1 4]
SCHED 853ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=0 [2 7 1 2]
SCHED 960ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=160 [0 1 39 11]
SCHED 1070ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=129 [0 1 3 6]
SCHED 1179ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=93 [20 3 24 14]
SCHED 1286ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=1549 [0 1 74 114]
SCHED 1396ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=1597 [0 0 26 88]
SCHED 1503ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=426 [96 1 44 69]
 112 4]
SCHED 1716ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=41 [9 2 69 6]
SCHED 1821ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=62 [12 0 5 1]
SCHED 1929ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=51 [9 0 6 1]
SCHED 2036ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=45 [15 0 9 1]
SCHED 2139ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=88 [1 10 7 6]
SCHED 2243ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=135 [1 1 13 11]
SCHED 2349ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=51 [1 10 4 5]
SCHED 2456ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=44 [1 7 11 0]
SCHED 2563ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=63 [1 6 10 0]
SCHED 2670ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=3 runqueue=95 [1 6 10 0]
SCHED 2770ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=83 [1 7 9 0]
SCHED 2877ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=1 [1 12 155 1]
SCHED 2981ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=105 [11 11 13 1]
SCHED 3087ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=140 [7 11 1 1]
SCHED 3195ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=73 [1 0 8 0]
SCHED 3303ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=138 [46 0 4 1]
SCHED 3413ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=147 [22 0 0 1]
SCHED 3514ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=3 runqueue=157 [5 19 51 1]
1957 [5 86 124 1]
SCHED 3728ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=133 [3 38 38 0]
SCHED 3834ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=141 [40 31 14 0]
SCHED 3937ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=37 [1 2 8 2]
SCHED 4041ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=74 [0 1 9 0]
SCHED 4147ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=60 [0 1 14 9]
SCHED 4251ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=71 [0 0 9 41]
SCHED 4357ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=5 [0 1 0 0]
SCHED 4460ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=4 [0 2 0 1]
SCHED 4567ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=202 [21 1 0 11]
SCHED 4677ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=6 runqueue=79 [7 1 8 5]
4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=46 [4 1 1 2]
SCHED 4887ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=8 [0 0 0 0]
SCHED 4996ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=18 [0 0 1 3]
SCHED 5102ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=76 [15 0 1 11]
SCHED 5209ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=109 [70 1 1 1]
SCHED 5314ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=87 [12 1 1 4]
SCHED 5419ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=14 [0 0 1 1]
SCHED 5522ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=8 [0 0 1 1]
SCHED 5622ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=3 runqueue=90 [140 1 22 0]
SCHED 5725ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=85 [91 1 9 21]
SCHED 5830ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=71 [1 1 21 2]
SCHED 5936ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=8 [1 1 0 0]
SCHED 6038ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=99 [11 2 1 0]
SCHED 6143ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=14 [97 1 4 2]
SCHED 6249ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=55 [1 62 123 33]
SCHED 6355ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=78 [1 6 4 17]
SCHED 6458ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=485 [1 100 101 111]
SCHED 6563ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=101 [1 15 5 13]
SCHED 6667ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=40 [1 2 74 0]
SCHED 6775ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=85 [1 6 8 98]
SCHED 6879ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=71 [1 14 1 1]
 8 108 0]
SCHED 7088ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=613 [14 102 43 100]
SCHED 7196ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=155 [1 101 7 13]
SCHED 7297ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=95 [1 18 7 100]
SCHED 7402ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=27 [1 2 2 4]
SCHED 7507ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=12 [119 0 0 1]
SCHED 7612ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=44 [2 8 14 1]
SCHED 7720ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=14 [4 1 2 2]
SCHED 7825ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=0 [164 0 1 0]
SCHED 7931ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=3 runqueue=36 [4 0 0 1]
SCHED 8041ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=42 [5 2 2 1]
SCHED 8143ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=62 [0 2 7 1]
SCHED 8243ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=2 runqueue=132 [1 239 26 23]
SCHED 8346ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=68 [2 4 3 4]
SCHED 8451ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=39 [6 1 1 0]
SCHED 8560ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=151 [146 0 1 9]
SCHED 8665ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=100 [1 8 0 25]
SCHED 8771ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=38 [2 1 1 1]
SCHED 8878ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=0 [1 0 0 115]
SCHED 8987ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=89 [6 17 5 3]
SCHED 9088ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=5 runqueue=901 [99 195 80 116]
SCHED 9193ms: gomaxprocs=4 idleprocs=0 threads=15 spinningthreads=0 idlethreads=4 runqueue=0 [0 0 0 0]
SCHED 9301ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9404ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9508ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9615ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9717ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9817ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 9926ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10027ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10139ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10241ms: gomaxprocs=4 idleprocs=3 threads=15 spinningthreads=0 idlethreads=8 runqueue=0 [0 0 0 0]
SCHED 10341ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10443ms: gomaxprocs=4 idleprocs=3 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10547ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10653ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 10753ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 10865ms: gomaxprocs=4 idleprocs=3 threads=15 spinningthreads=0 idlethreads=8 runqueue=0 [0 0 0 0]
SCHED 10975ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=8 runqueue=0 [0 0 0 0]
SCHED 11087ms: gomaxprocs=4 idleprocs=3 threads=15 spinningthreads=0 idlethreads=8 runqueue=0 [0 0 0 0]
SCHED 11189ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 11291ms: gomaxprocs=4 idleprocs=2 threads=15 spinningthreads=1 idlethreads=7 runqueue=0 [0 0 0 0]
SCHED 11391ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 11501ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 11604ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 11713ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 11821ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 11930ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12041ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12141ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12247ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12354ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12456ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12558ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12666ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12769ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12878ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 12983ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13083ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13186ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13290ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13395ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13504ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13605ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13706ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
SCHED 13808ms: gomaxprocs=4 idleprocs=4 threads=15 spinningthreads=0 idlethreads=9 runqueue=0 [0 0 0 0]
[2020-04-17 15:41:07]  INFO netTask: finished
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package main

import (
    "fmt"
    "os"

    logger "github.com/sirupsen/logrus"
    "github.com/x-cray/logrus-prefixed-formatter"
)

func init() {
    logger.SetFormatter(&prefixed.TextFormatter{
        TimestampFormat: "2006-01-02 15:04:05",
        FullTimestamp:   true,
        ForceFormatting: true,
        DisableColors:   true,
    })
    logger.SetOutput(os.Stdout)
    logger.SetLevel(logger.DebugLevel)
}

func main() {
    ch := make(chan string)

    go func() {
        var s string
        fmt.Scanln(&s)
        ch <- s
    }()

    s := <-ch
    logger.Infof("input is: %v", s)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
$ GODEBUG=schedtrace=500,scheddetail=1 ./go-learn 1>learn.out 2>&1
$ cat learn.out
SCHED 0ms: gomaxprocs=4 idleprocs=2 threads=3 spinningthreads=1 idlethreads=0 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=1 schedtick=0 syscalltick=0 m=0 runqsize=0 gfreecnt=0
  P1: status=1 schedtick=0 syscalltick=0 m=2 runqsize=0 gfreecnt=0
  P2: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P3: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  M2: p=1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M0: p=0 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=1
  G1: status=1() m=-1 lockedm=0
  G2: status=1() m=-1 lockedm=-1
SCHED 500ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=0 schedtick=2 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P1: status=0 schedtick=3 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P2: status=0 schedtick=2 syscalltick=6 m=-1 runqsize=0 gfreecnt=0
  P3: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  M4: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M3: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M2: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M0: p=-1 curg=34 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=false lockedg=-1
  G1: status=4(chan receive) m=-1 lockedm=-1
  G2: status=4(force gc (idle)) m=-1 lockedm=-1
  G17: status=4(GC sweep wait) m=-1 lockedm=-1
  G18: status=4(GC scavenge wait) m=-1 lockedm=-1
  G33: status=4(finalizer wait) m=-1 lockedm=-1
  G34: status=3() m=0 lockedm=-1
SCHED 1010ms: gomaxprocs=4 idleprocs=4 threads=5 spinningthreads=0 idlethreads=3 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=0 schedtick=2 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P1: status=0 schedtick=3 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  P2: status=0 schedtick=2 syscalltick=6 m=-1 runqsize=0 gfreecnt=0
  P3: status=0 schedtick=0 syscalltick=0 m=-1 runqsize=0 gfreecnt=0
  M4: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M3: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M2: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=true lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 spinning=false blocked=false lockedg=-1
  M0: p=-1 curg=34 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 spinning=false blocked=false lockedg=-1
  G1: status=4(chan receive) m=-1 lockedm=-1
  G2: status=4(force gc (idle)) m=-1 lockedm=-1
  G17: status=4(GC sweep wait) m=-1 lockedm=-1
  G18: status=4(GC scavenge wait) m=-1 lockedm=-1
  G33: status=4(finalizer wait) m=-1 lockedm=-1
  G34: status=3() m=0 lockedm=-1
[2020-04-17 15:55:36]  INFO input is: hello

Posted on Edited on Disqus:

Official document

Using Redis as an LRU cache

Eviction policies

There are total 6 evicition policies so far:

  • noeviction
  • allkeys-lru
  • allkeys-random
  • volatile-lru
  • volatile-random
  • volatile-ttl

allkeys for all keys, while volatile means among keys that have an expire set. lru means evict keys by trying to remove the less recently used (LRU) keys first, random means evict keys randomly, ttl means try to evict keys with a shorter time to live (TTL) first.

The range of the keys to be evicted: Only the keys that have a expire set are in both the dict and expires two dicts, others are in dict only. 

1
2
3
4
5
6
7
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
    server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM)
{
    dict = server.db[j].dict;
} else {
    dict = server.db[j].expires;
}

Getting a paricular key by using random: 

1
2
3
4
5
6
7
/* volatile-random and allkeys-random policy */
if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_RANDOM ||
    server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_RANDOM)
{
    de = dictGetRandomKey(dict);
    bestkey = dictGetKey(de);
}

Getting a particular key by using LRU: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
    server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
    struct evictionPoolEntry *pool = db->eviction_pool;

    while(bestkey == NULL) {
        evictionPoolPopulate(dict, db->dict, db->eviction_pool);
        /* Go backward from best to worst element to evict. */
        for (k = REDIS_EVICTION_POOL_SIZE-1; k >= 0; k--) {
            if (pool[k].key == NULL) continue;
            de = dictFind(dict,pool[k].key);

            /* Remove the entry from the pool. */
            sdsfree(pool[k].key);
            /* Shift all elements on its right to left. */
            memmove(pool+k,pool+k+1,
                sizeof(pool[0])*(REDIS_EVICTION_POOL_SIZE-k-1));
            /* Clear the element on the right which is empty
             * since we shifted one position to the left.  */
            pool[REDIS_EVICTION_POOL_SIZE-1].key = NULL;
            pool[REDIS_EVICTION_POOL_SIZE-1].idle = 0;

            /* If the key exists, is our pick. Otherwise it is
             * a ghost and we need to try the next element. */
            if (de) {
                bestkey = dictGetKey(de);
                break;
            } else {
                /* Ghost... */
                continue;
            }
        }
    }
}

Getting a particular key by using TTL: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* volatile-ttl */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_TTL) {
    for (k = 0; k < server.maxmemory_samples; k++) {
        sds thiskey;
        long thisval;
        de = dictGetRandomKey(dict);
        thiskey = dictGetKey(de);
        thisval = (long) dictGetVal(de);
        /* Expire sooner (minor expire unix timestamp) is better
         * candidate for deletion */
        if (bestkey == NULL || thisval < bestval) {
            bestkey = thiskey;
            bestval = thisval;
        }
    }
}

Posted on Edited on Disqus:

https://www.renfei.org/blog/bipartite-matching.html https://en.wikipedia.org/wiki/Matching_(graph_theory)

Hungarian Algorithm

Given a matching M,

  • an alternating path is a path that begins with an unmatched vertex and whose edges belong alternately to the matching and not to the matching.
  • an augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.

Traverse all the points on the left, for each point \(u\) if we can find a augmenting path \(\vec{p}\) starting from \(u\), then we use the edges of \(\vec{p}\) to update the matches of each point on \(\vec{p}\).

Problems

HDU 1068 Girls and Boys

This problem is to figure out the number of maximum independent set of bipartite graph.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 1024;

vector<int> g[MAXN];
int match[MAXN];
bool vis[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        g[i].clear();
    }
    fill(match, match + n, -1);
}

bool dfs(int u) {
    for (auto v : g[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }

    return false;
}

int hungary(int n) {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        fill(vis, vis + n, false);
        if (dfs(i)) ans++;
    }
    return ans / 2;
}

int main(int argc, char **argv) {
    int n;
    while (scanf("%d", &n) != EOF) {
        init(n);
        for (int i = 0; i < n; i++) {
            int u, cnt;
            scanf("%d: (%d) ", &u, &cnt);
            for (int j = 0; j < cnt; j++) {
                int v;
                scanf("%d", &v);
                g[u].push_back(v);
            }
        }
        printf("%d\n", n - hungary(n));
    }
    return 0;
}

HDU 1179 Ollivanders: Makers of Fine Wands since 382 BC.

There are 3 ways to solve the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 128;
vector<int> g[MAXN];
int match[MAXN];
bool vis[MAXN];

void init(int n, int m) {
    for (int i = 1; i <= m; i++) {
        g[i].clear();
    }
    fill(match + 1, match + 1 + n, -1);
}

void add(int u, int v) {
    g[u].push_back(v);
}

bool dfs(int u) {
    for (auto v : g[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungary(int n, int m) {
    int ans = 0;
    for (int i = 1; i <= m; i++) {
        fill(vis + 1, vis + 1 + n, false);
        if (dfs(i)) ans++;
    }
    return ans;
}

int main(int argc, char **argv) {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        init(n, m);
        for (int i = 1; i <= m; i++) {
            int c;
            scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int v;
                scanf("%d", &v);
                add(i, v);
            }
        }
        printf("%d\n", hungary(n, m));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 128 * 2;

vector<int> g[MAXN];
int match[MAXN];
bool vis[MAXN];

void add(int u, int v) {
    g[u].push_back(v);
}

void init(int n, int m) {
    for (int i = 1; i <= n + m; i++) {
        g[i].clear();
    }
    fill(match + 1, match + 1 + n, -1);
}

bool dfs(int u) {
    for (auto v : g[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int n, int m) {
    int ans = 0;
    for (int u = n + 1; u <= n + m; u++) {
        fill(vis + 1, vis + 1 + n, false);
        if (dfs(u)) ans++;
    }
    return ans;
}

int main(int argc, char **argv) {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        init(n, m);
        for (int u = n + 1; u <= n + m; u++) {
            int c;
            scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int v;
                scanf("%d", &v);
                add(u, v);
                add(v, u);
            }
        }
        printf("%d\n", hungarian(n, m));
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
#define DBG(x) cerr << #x << " = " << x << endl

using namespace std;
typedef long long LL;

const int MAXN = 128 * 2;

vector<int> g[MAXN];
int match[MAXN];
bool vis[MAXN];

void init(int n, int m) {
    for (int i = 1; i <= n + m; i++) {
        g[i].clear();
    }
    fill(match + 1, match + 1 + n + m, -1);
}

bool dfs(int u) {
    for (auto v : g[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        if (match[v] == -1 || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian(int n, int m) {
    int ans = 0;
    for (int u = 1; u <= n + m; u++) {
        fill(vis + 1, vis + 1 + n + m, false);
        if (dfs(u)) ans++;
    }
    return ans / 2;
}

void add(int u, int v) {
    g[u].push_back(v);
}

int main(int argc, char **argv) {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        init(n, m);
        for (int u = n + 1; u <= n + m; u++) {
            int c;
            scanf("%d", &c);
            for (int j = 0; j < c; j++) {
                int v;
                scanf("%d", &v);
                add(u, v);
                add(v, u);
            }
        }
        printf("%d\n", hungarian(n, m));
    }
    return 0;
}