星期六, 12月 27, 2014

Linux time

時間主要有三款:

  • CLOCK_REALTIME (wall clock,calendar):目前時間
    • 對 Epoch 時間 1970-01-01 00:00:00 +0000 (UTC) 開始算。
    • Epoch 時間大約是 UNIX 系統誕生的時陣。Epoch 意思是「出現新進步和大變革的時代」,UNIX 系統誕生家己講是大時代。
    • 紀錄 Epoch 開始的時間,其中「秒」存在資料類型 time_t 的變數,在 32-bit Linux 系統是 signed 32-bit,可計約 68 年,到 2038 年會有溢位問題
    • 有時需要調整,可能透過網路或 date 指令手動調整,所以有突然間跳較快跳較慢。
    • 會使搭配獨立的硬體時鐘,但不是必要的。硬體時鐘 (Real-Time Clock (RTC)、CMOS clock、BIOS clock),可能只有精確到秒,關機時會使靠電池繼續走,開機時電腦會使馬上取得目前時間。此外,它嘛也可能提供鬧鐘、喚醒等其它功能。只有適當的時機才會去存取硬體時間,例如開機時、或有所調整時,可透過系統管理指令 hwclock 或 /etc/rtcN 存取。
  • CLOCK_MONOTONIC 開機時間,對開機開始算,就是 uptime 顯示的時間,是一直增加的,不受調時間影響而有跳的問題。
  • CPU time:程式實際有用到 CPU 的時間片段總和,還可以細分成 user 及 system 兩部份,分別是在 user mode 花的時間,以及因此 process 執行 system call 在 kernel 的執行時間。指令 time 用來量測程式使用的 CPU time。程式內部可用系統呼叫 times() 及 getrusage(),或函式 clock() 量測 CPU time。

軟體上的任何計時,都是由 kernel 內部固定週期的 jiffy 中斷來驅動。目前時間可能透過網路調整,但驅動還是靠 jiffy。jiffy 週期精準度,會影響軟體計時的精準度,沒有網路校時,一段時間後,目前時間可能就不準了。

每次 jiffy 中斷,Kernel 系統變數 jiffies 就會加一。jiffy 中斷週期換著頻率,就是 Kernel 編譯設定值 HZ,在不同版本的 kernel 或處理器平台會有不同的值,一般在 100 ~ 1000 之間,也就是 jiffy 週期是在 0.01秒 ~ 0.001秒之間,決定了許多系統呼叫時間的精確度。例如 select() 跟 sigtimedwait() 的 timeout、getrusage() 的 CPU time 量測等。系統呼叫 times() 是個特例,回報的時間單位是 kernel 常數 USER_HZ,應用程式可使用sysconf(_SC_CLK_TCK) 得知 USER_HZ。

High-resolution timers (HRTs)
Linux 2.6.21 以前,系統時間最小單位是 jiffy,之後的 CONFIG_HIGH_RES_TIMERS 開始支援高解析度 timer,讓時間可以更精確,一般可達 microsecond (原理?)。可用系統呼叫 clock_getres() 或看 /proc/timer_list 的 resolution 查看 timer 解析度。

取得時間的系統呼叫

  • time_t // 回傳 Epoch 開始的秒數。-1 當 timep 有誤時。
    time(
        time_t *timep); // 非 NULL 時亦 回傳 Epoch 開始的秒數。
    一般使用 time(NULL),time() 實作可能是呼叫 gettimeofday()。
  • int // 0 成功,–1 錯誤
    gettimeofday(
        struct timeval *tv, // 提供空間回傳 Epoch 秒數和 µsec。
        struct timezone *tz); // 廢棄,需指定為 NULL。
    雖然 tv_usec 提供 microsecond precision,但實際 accuracy 由 architecture-dependent 實作決定。
  • clock_gettime():取得秒數和 nsec (struct timespec)。
    • CLOCK_REALTIME 從 Epoch 開始計數。
    • CLOCK_MONOTONIC 從開機開始計數。實際上開機多久是紀錄和 realtime (wall clock) 的時間差 (變數 wall_to_monotonic),如有調校 realtime 或 suspend,wall_to_monotonic 也會跟著一起調整。(為什麼不用 jiffies 轉換就好?)
    • 其它還有 CPU 時間等。

註:Epoch 的 time()、gettimeofday()、和 CLOCK_REALTIME 都是 __get_realtime_clock_ts(),而 CLOCK_MONOTONIC 是用 ktime_get_ts()。

設定或調校目前時間

在這段,設定和調校意思不同,設定跳躍式調整,調校是逐漸調整。

  • 設定時間
    • settimeofday()
    • clock_settime():使用 settimeofday() 設定日期時間,限 realtime。
    • stime():使用 settimeofday() 設定秒數。glibc 2.31 以後移除,該改用 clock_settime()。
  • 調校時間

日期 (calendar) 時間

struct timeval {
    time_t      tv_sec;     // Epoch 開始的秒數
    suseconds_t tv_usec;    // 額外 microseconds (long int)
};

時間轉換函數

time_t 和其它格式間轉換,包括 struct tm、固定或使用者定義的列印格式,內含時區、日光節約時間、和 localization 轉換的處理。

函數庫函數將 Epoch 秒數 (time_t) 轉成年月日時分秒等分別紀錄的 struct tm 格式

  • gmtime(): 轉成 struct tm
  • gmtime_r():gmtime() 的 reentry 版本,存在使用者提供的 struct tm。
  • localtime():轉成 struct tm,考量時區和日光節約時間,同時做 tzset() 的動作。
  • localtime_r():同 localtime(),但存在使用者提供的資料結構,不設 tzname, timezone, daylight。

tm_sec 欄位在閏秒時會到 60。

struct tm 轉成字串

  • asctime(), asctime_r():轉成標準的列印格式
  • strftime():轉成自訂的列印格式

ctime(t):相當於 asctime(localtime(t)),自動考量時區和日光節約時間。ctime_r()

反過來轉換的有
strptime():字串轉成 struct tm
mktime()、timegm()、timelocal():struct tm 轉成 time_t

mktime() 忽略 tm_wday 和 tm_yday 原本的值並修正,其它值超出範圍或負數也會調整。會考量時區。tm_isdst 決定是否使用 DST 設定,0 忽略 DST、正值不管日期總是調整 DST、負值依據日期調整 DST,最後有調整 tm_isdst 設為正值、否則設為 0。

timezone
幾乎所有時間計數不需要考慮 timezone,只有顯示時需要轉換成本地時間。少數,例如 vfat 檔案系統,如果 kernel 的 timezone 不對,檔案的時戳會設錯。hwclock --hctosys 依據 TZ 或 /usr/share/zoneinfo 設定 kernel timezone。

TZ 有兩種格式

  • <dst>[offset],start[/time],end[/time]]
  • <std><offset>[<dst>]
    • <std> 是時區名稱,至少有三個英文字母
    • <offset> 加上本地時間可以得到 UTC 時間,在子午線東方會是負的。格式是 [-]hh[:mm[:ss]],可以包括時分秒。
    • <dst> 有用到日光節約時間 (datlight saving time) 才有,說明一年中的哪些日子改用不同的 <offset>,格式是 dst[offset],start[/time],end[/time]
      • dst 是日光節約時間的名稱
      • offset 格式跟上述 <offset> 一樣,是日光節約日用的 <offset>,如省略則預設提早一個小時
      • start 跟 end 說明使用日光節約時間開始跟結束的日子,有三種格式
        • Jnn 為 1 ~ 365 的 Julian day,不計 Leap days,所以二月二十九日不能表示,三月一日是 60。
        • nn 為 0 ~ 365 的 Julian day,閏年加上二月二十九日。
        • Mm.w.d:月、周、日
      • time 表示切換日光節約時間是在本地時間幾點切換,如省略則是 02:00:00。
    • 範例:NZST-12:00:00NZDT-13:00:00,M10.1.0,M3.3.0
  • :[filespec]
timer (expires  at some  point  in  the  future, and optionally at repeated intervals):見系統呼叫 alarm()、getitimer()、timerfd_create()、timer_create()。

Timer slack
從 Linux 2.6.28 開始,可以控制 thread 的 "timer  slack"  值,延遲喚醒 certain 系統呼叫 that  block  with a timeout,讓 kernel 合併 (coalesce) 一些喚醒事件,來減少喚醒次數並節省電源。細節請見系統呼叫 prctl() 的 PR_SET_TIMERSLACK 描述。

參考

  1. man 7 time
  2. man hwclock
  3. man ctime
  4. man strftime
  5. man strptime
  6. man timezone
  7. https://lirobo.blogspot.com/2015/08/busybox-ntpd.html
  8. TLPI chap. 10 和 chap 26
延伸閱讀
  • man rtc
  • Documentation/rtc.txt
  • man adjtimex
  • userspance 延遲用 sleep、kernel 延遲用 mdelay
  • sched_yield、pthread_delay_np
  •  [轉載整理]Linux系統時間
  • 使用 realtime 的呼叫
    * 顯示日期時間
    * 檔案時間用 timeval:utimes()
    * select(), pselect()
    * sem_timedwait() semtimedwait()

    和 realtime 無關的呼叫
    * timeval 運算:timercmp(), timersub()

    使用 int 表示 msec
    * int32_t 範圍是 -2147483648 ~ 2147483647 約 24 天,uint32_t 的話約 49 天。

星期三, 12月 10, 2014

packet socket

收送 L2 封包要用 packet socket,使用
socket(AF_PACKET, SOCK_RAW, protocol) 或
socket(AF_PACKET, SOCK_DGRAM, protocol)
建立一個通訊端點後回傳 file descriptor。SOCK_RAW 是收送整個 L2 封包,SOCK_DGRAM 則不包括 L2 header。protocol 是指定要收的 Ether Type (需轉成 network endian),如果所有 Ether Type 都收的話用 htons(ETH_P_ALL)。

預設所有網路界面都收,可用 bind() 綁定界面。收的封包包括 unicast 及 broadcast,用 setsockopt(<fd>, SOL_PACKET, <optname>, <optval>, <optlen>) 修改是否接收其它 MAC 位址的封包。
  • PACKET_ADD_MEMBERSHIP, PACKET_DROP_MEMBERSHIP:
    • PACKET_MR_PROMISC:不做 MAC address 過濾
    • PACKET_MR_MULTICAST:增減 multicast 位址
    • PACKET_MR_ALLMULTI:接收所有 multicast
網路界面預設只收 boardcast 及符合介面 MAC 位址的 unicast,但設為 promiscous 模式時所有封包都會進來,要做進一步過濾可以用 socket filter 過濾目的 MAC 位址

int da_filter(int sk, const unsigned char *mac)
{
         struct sock_filter code[] = {
                /* tcpdump -dd ether dst 12:34:56:78:9a:bc or broadcast
                 * (000) ld       [2]
                 * (001) jeq      #0x56789abc      jt 2 jf 4
                 * (002) ldh      [0]
                 * (003) jeq      #0x1234          jt 7 jf 8
                 * (004) jeq      #0xffffffff      jt 5 jf 8
                 * (005) ldh      [0]
                 * (006) jeq      #0xffff          jt 7 jf 8
                 * (007) ret      #65535
                 * (008) ret      #0
                 */
                { 0x20, 0, 0, 0x00000002 },
                { 0x15, 0, 2, 0x56789abc },
                { 0x28, 0, 0, 0x00000000 },
                { 0x15, 3, 4, 0x00001234 },
                { 0x15, 0, 3, 0xffffffff },
                { 0x28, 0, 0, 0x00000000 },
                { 0x15, 0, 1, 0x0000ffff },
                { 0x6, 0, 0, 0x0000ffff },
                { 0x6, 0, 0, 0x00000000 },
        };
        code[3].k = (mac[0]<<8)+mac[1];
        code[1].k = (mac[2]<<24)+(mac[3]<<16)+(mac[4]<<8)+mac[5];
        struct sock_fprog bpf = {
                .len = sizeof(code)/sizeof(code[0]),
                .filter = code,
        };
        if ((ret = setsockopt(sk, SOL_SOCKET, SO_ATTACH_FILTER, &bpf, sizeof(bpf))))
                printf("setsockopt error: %s\n", strerror(errno));
 return ret;
}
透過 SO_DETACH_FILTER 或 socket 關閉時移除。改變需要先移除舊的,如果新的加入失敗會沿用舊的。SO_LOCK_FILTER 選項鎖定 attached 的過濾碼,不能移除或改變。

收封包送封包
read(fd, buf, len)write(fd, buf, len)
recv(fd, buf, len, flags)send(fd, buf, len, flags)
recvfrom(fd, buf, len, flags, addr, addrlen)sendto(fd, buf, len, flags, addr, addrlen)
recvmsg(fd, msg, flags)sendmsg(fd, msg, flags)

如果要用 write 或 send 送封包,需要先綁定網路界面,不然不知道要從哪個界面送。


bindsendreceive
familyvv?
protocolv-?
ifindexvv?
hatype--v
pktype--v
halen-v?
addr[8]-v?

註:

參考來源
  1. man packet
  2. man socket
  3. http://yusufonlinux.blogspot.tw/2010/11/data-link-access-and-zero-copy.html
  4. http://www.scs.stanford.edu/histar/src/lind/os-Linux/drivers/rawsock_user.c
  5. https://www.kernel.org/doc/Documentation/networking/filter.txt

程式註解的標籤

標籤有助於索引問題,常見的有:
  • FIXME:需要修正
  • XXX:該刪除
  • TODO:打算要實作。久了之後可能會累積很多,建議加上日期及名子。
  • NOTE:說明程式碼內部運作方式及可能的陷阱。

參考來源
  1. wikipedia: Comment (computer_programming)#Tags

TSO, GSO, LRO, GRO

在 10G Ethernet,每個封包 1500 bytes 的話,每秒可超過 800000 個封包,對封包收送是個考驗。jumbo frames 可讓一個封包有 9K bytes,可減少每秒封包數目,在 local 使用還可以,在遠距由於 MTU,無法維持大封包。

TCP segmentation offload (TSO):可送 64K bytes 的 TCP 封包,由網卡協助 segmentation

Generic segmentation offload (GSO):不限於 TCP,在驅動程式模擬硬體 segmentation,但只能用在傳。

Large receive offload (LRO):在網卡或驅動程式合併進來的封包,減少每秒要處理的封包數,但有缺陷。

Generic receive offload (GRO):加強能合併的限制,且不限於用在 TCP/IPv4

參考來源
  1. JLS2009: Generic receive offload

netif_receive_skb

網路界面驅動程式使用 NAPI 的方式接收封包會呼叫 netif_receive_skb(skb),將 sk_buff 結構的封包傳給上層 (實際上是 __netif_receive_skb()):
  1. 呼叫 netpoll_rx() 來支援 Netpoll API。netpoll 在 kernel 裡實作 UDP clients 及 servers,應用在 netdump, remote syslog, netlog/netconsole, kgdb 等,即使 kernel crash 也可以送收封包。
  2. 如果有 VLAN tag,則做標記,並做 untag 動作,更新 sk_buff 相關欄位。
  3. 呼叫接收任何 Ether Type 的封包處理函數 (ptype_all 部份,用在 tcpdump 等)
  4. 呼叫 handle_ing() 作為 ingress queueing
  5. 如果原本有 VLAN tag,封包的 net_device 換成此 VLAN ,從 2 再開始。
  6. 呼叫 net_device 的 rx_handler (用於 bridged 的界面),結果可能是 
    • RX_HANDLER_CONSUMED:已經完成處理,結束。
    • RX_HANDLER_ANOTHER:從 2 再開始下一回合。
    • RX_HANDLER_EXACT:接下來需符合 sk_buff 指定的 net_device
    • RX_HANDLER_PASS:接下來可以符合不指定 net_device
  7. 呼叫特定 Ether Type 的封包處理函數:例如 VLAN 的 vlan_skb_recv()、ARP 的 arp_rcv()、IPv4 的 ip_rcv()、IPv6 的 ipv6_rcv()、PPPoE 的 pppoe_rcv() 跟 pppoe_disc_rcv() 等。

註:
  • 針對 Ether Type 的封包處理函數紀錄在 ptype_all 跟 ptype_ base[],透過 dev_add_pack() 登記 ether type 及處理的函數 (struct packet_type)相反動作是呼叫 dev_remove_pack() 來移除。
  • L2 socket 如果要收的 Ether Type 是 VLAN,應該會收不到
  • pfmemalloc 只用在 ARP, IP, VLAN 等 Ether Type,不做 任何 Ether Type 的封包處理
  • vlan_skb_recv() 移除 VLAN header 後,透過 netif_rx() 放到 input_pkt_queue,再 poll 取出呼叫 netif_receive_skb()。

參考來源:
  1. net/core/dev.c 及相關 source code
  2. http://www.linuxfoundation.org/collaborate/workgroups/networking/kernel_flow#Receive_flow
  3. http://www.cs.columbia.edu/~nahum/w6998/lectures/device-layer.ppt
延伸閱讀