#
復(fù)習(xí) 快排
int buf[1024] = {0};
int partition(int first, int last)
{
int stand = buf[last];
int i =0, j=0;
//int e = last -1;
for (;j < last ; j++ )
{
if (buf[j] <= stand )
{
int temp = buf[j];
buf[j] = buf[i];
buf[i] = temp;
i++;
}
}
int temp = buf[last];
buf[last] = buf[i];
buf[i] = temp;
return i;
}
void myQuickSort(int begin, int end)
{
if (begin < end)
{
int pivot ;
pivot = partition(begin, end);
myQuickSort(begin, pivot -1 );
myQuickSort(pivot+1, end);
}
}
int main()
{
srand(time(0));
for (int i = 0; i < 1000; i++)
{
buf[i] = rand() * 2342111134 % 6589453 ;
}
myQuickSort(0,1023);
return 0;
}
在本實(shí)現(xiàn) 里面， 直接使用了最后一個(gè)元素作為基準(zhǔn)。
在選擇基準(zhǔn)時(shí)其實(shí)是有多種方式的。1）選第一個(gè)，不推薦。2）算最后一個(gè)，不推薦。3）選首、尾、中的中間值。4）隨機(jī)選擇。
選擇后將跑一趟比較，結(jié)果是左側(cè)為小的數(shù)，右側(cè)為大的數(shù)，原理是i,j 當(dāng)數(shù)小于基準(zhǔn)是則與左右的i 對(duì)換，這樣保證了i左側(cè)小于p i 到j(luò) 之間是大小p 的。
對(duì)于p 無需再排了。
需要特別注意的是partition 里面的元素位置與quicksort 分段是有關(guān)系的。 如果在partition 里面處理了last 那么 在分段時(shí)其實(shí)last 就不用了。
目的：重新梳理TCP，全局理解協(xié)議中的細(xì)節(jié)，知道是怎樣實(shí)現(xiàn)的，理解為什么要這樣做，了解可能會(huì)帶來什么問題。
PS:圖片有空了慢慢貼。
簡(jiǎn)要介紹：
TCP協(xié)議是基于網(wǎng)絡(luò)層IP協(xié)議的傳輸層協(xié)議，提供一種面向連接的，可靠的字節(jié)流服務(wù)(byte stream service )。在TCP連接中， 僅支持兩方進(jìn)行彼此通信。
TCP的可靠性由以下方式 來提供：
1） 恰當(dāng)?shù)臄?shù)據(jù)分段。即將字節(jié)流根據(jù)MSS來封包發(fā)送。
2） 確認(rèn)機(jī)制、重傳機(jī)制。
3） 首部的檢驗(yàn)和。
4） 網(wǎng)絡(luò)層的IP數(shù)據(jù)報(bào)可能會(huì)失序，因此TCP需要將數(shù)據(jù)進(jìn)行重新排序。
5） 數(shù)據(jù)報(bào)可能會(huì)重復(fù)，必須恰當(dāng)?shù)膩G棄重復(fù)的數(shù)據(jù)報(bào)。
6） TCP提供流量控制，可根據(jù)另一端的緩沖區(qū)情況發(fā)送恰當(dāng)?shù)臄?shù)據(jù)（滑動(dòng)窗口協(xié)議）。
7） TCP協(xié)議對(duì)字節(jié)流不作解釋。由應(yīng)用層對(duì)數(shù)據(jù)進(jìn)行語義上的解釋。
隨便抓個(gè)包：
IP數(shù)據(jù)頭
TCP數(shù)據(jù)頭
頭部中比較重要的數(shù)據(jù)結(jié)構(gòu)
源端口，目的端口，序號(hào)，確認(rèn)序號(hào)。 標(biāo)志位，窗口大小。
URG：緊急指針，一般用不上，忽略。
ACK：經(jīng)常用，接收端發(fā)給源端，確認(rèn)前一個(gè)包已收到。
PSH：個(gè)人沒怎么碰到過。
RST：可以理解為重置連接，普通情況下當(dāng)目標(biāo)端口未開放會(huì)發(fā)送此RST回來，此外，連接中間的防火墻等網(wǎng)絡(luò)設(shè)備也會(huì)發(fā)。
SYN：發(fā)起連接的標(biāo)志，SYN Flood是基于的一種DOS攻擊手法。
FIN：shutdown 時(shí)發(fā)送，告訴對(duì)方，我這邊完成了，要送掉連接了。
1、 TCP連接的建議，三步握手。
1） 源端發(fā)送SYN到服務(wù)器，表示喜娃懷與服務(wù)器的某個(gè)端口建立TCP連接，在TCP首部帶上初始的序號(hào)（client ISN）。此報(bào)文中設(shè)置SYN=1；
2） 服務(wù)器返回SYN包，帶上服務(wù)器的初始序號(hào)（server ISN），并且ACK=client ISN+1設(shè)置SYN=1,ACK=1；
3） 源端返回服務(wù)器ACK包， ack = server ISN+1;
PS:這邊的Seq居然從0開始，之前都沒注意過~~
關(guān)于ISN的選擇，根據(jù)文獻(xiàn)內(nèi)容，應(yīng)當(dāng)隨時(shí)間變化，避免網(wǎng)絡(luò)中被延遲的分組被重新傳遞后導(dǎo)致的錯(cuò)誤解釋。
2、 TCP連接的終止，四步握手。
1） 首先關(guān)閉的一方（A）發(fā)送FIN包。FIN在應(yīng)用層、開發(fā)者面前就是socket.read 將返回EOF。
2） 接受端（B）返回FIN的ACK包。
3） B關(guān)閉連接，發(fā)送FIN。
4） A發(fā)送ACK。
關(guān)閉階段存在另外兩衍生的流程。1） 2與3 兩步可以合并， 當(dāng)B端無數(shù)據(jù)發(fā)送時(shí)，無需發(fā)放兩個(gè)包，可以在一個(gè)包里面同時(shí)設(shè)置FIN+ACK，也就是上面的截圖。2）當(dāng)僅一端調(diào)用shutdown，另一端還存在數(shù)據(jù)發(fā)送時(shí)，存在半關(guān)閉連接的情況。即第2步結(jié)束后，B端繼續(xù)發(fā)送數(shù)據(jù)，A端對(duì)這些數(shù)據(jù)仍然發(fā)送ACK，一直到B端發(fā)送FIN。
以下是一個(gè)簡(jiǎn)單的client + server 測(cè)試代碼，通過簡(jiǎn)單的Sleep可以看出， 當(dāng)收到FIN包時(shí)，緩沖區(qū)的數(shù)據(jù)仍然存在，僅在后面多了一個(gè)EOF而已。
1 #!/usr/bin/env python
2 import socket
3 import time
4
5 host="192.168.5.106"
6 port=10000
7 s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
8 s.bind((host,port))
9 s.listen(5)
10 sock,addr=s.accept()
11 print "got connection form ",sock.getpeername()
12 while 1:
13 data=sock.recv(1)
14 time.sleep(0.1)
15 if not data:
16 print("~~~~~")
17 break
18 else:
19 print data
20
1 #!/usr/bin/env python
2 import socket
3 host="192.168.5.106"
4 port=10000
5 s=socket.socket(socket.AF_INET,socket.SOCK_STREAM)
6 s.connect((host,port))
7 s.send("hello from client")
8 s.close()
《 程序員必讀的職業(yè)規(guī)劃書》
最開始好像是在微博上看到pdf版本，挺長(zhǎng)挺有層次的一篇文章。
最近半年也是有點(diǎn)動(dòng)的想法，但其實(shí)在規(guī)劃這件事情上做的不夠， 有個(gè)參考指南可以慢慢對(duì)比一下自身
因?yàn)槟硍all的原因，大家需要一個(gè)通道。
現(xiàn)在比較好的辦法是使用hk或其他地方的vps ，然后搭個(gè)ssh過去，再使用Sock代理。
putty 已自帶ssh通道的功能。但其不支持記住密碼。很煩。
網(wǎng)上傳的很多教程中使用了 myentunnel 。 結(jié)果下載后一下，這逗比工具使用的還是putty，既然如此，何必使用額外的工具。
putty雖然記住密碼不方便，但使用SSH自帶的證書功能，也是可以實(shí)現(xiàn)自動(dòng)登錄的~
1、使用puttygen 生成密鑰對(duì)。 此處的 key passphrase 填寫后，最終的private key 使用需要密碼。。因此可以不填。
2、將public key 放入 /home/user/.ssh/authorized_keys中。此處需確保 .ssh authorized_keys 對(duì)其他用戶僅可讀。 如755，否則無法使用。
3、在putty的Connection -> ssh -> auth 處可以選擇private key .
4、在Connection -> Data 處可選填auto-login username。
5、為確保不會(huì)自動(dòng)掉線，Connection keepalive 填上非0。如30
6、再save就行啦。 后面再使用就方便了。
不過此種方法因?yàn)樾枰褂盟借€文件，且對(duì)私鑰文件無passphrase保護(hù)，需保證私鑰的安全性，如放在私密的U盤中，僅使用時(shí)插上，離開時(shí)帶走。
為L(zhǎng)inux下線程加個(gè)名字。同樣的Windows 也可以干。 chrome 的源碼中有使用到這個(gè)trick，raise 一個(gè)Exception.
1 #include <sys/prctl.h>
2 void set_thread_name(const char *prefix)
3 {
4 static int index = 0;
5 char thname[16];
6 snprintf(thname, sizeof(thname), "%s%d", prefix, __sync_fetch_and_add(&index, 1));
7 prctl(PR_SET_NAME, (usigned long)thname, 0, 0, 0); //~ refer to `man prctl`
8 }
9
windows 版本 原文見:http://msdn.microsoft.com/en-us/library/xcb2z8hs(VS.90).aspx
//
// Usage: SetThreadName (-1, "MainThread");
//
#include <windows.h>
const DWORD MS_VC_EXCEPTION=0x406D1388;
#pragma pack(push,8)
typedef struct tagTHREADNAME_INFO
{
DWORD dwType; // Must be 0x1000.
LPCSTR szName; // Pointer to name (in user addr space).
DWORD dwThreadID; // Thread ID (-1=caller thread).
DWORD dwFlags; // Reserved for future use, must be zero.
} THREADNAME_INFO;
#pragma pack(pop)
void SetThreadName( DWORD dwThreadID, char* threadName)
{
THREADNAME_INFO info;
info.dwType = 0x1000;
info.szName = threadName;
info.dwThreadID = dwThreadID;
info.dwFlags = 0;
__try
{
RaiseException( MS_VC_EXCEPTION, 0, sizeof(info)/sizeof(ULONG_PTR), (ULONG_PTR*)&info );
}
__except(EXCEPTION_EXECUTE_HANDLER)
{
}
}
Page 76 . 5.4 監(jiān)聽socket
此處作者說法不完整。
通過Google "man listen " http://linux.die.net/man/2/listen
listen() marks the socket referred to by sockfd as a passive socket, that is, as a socket that will be used to accept incoming connection requests using accept(2).The sockfd argument is a file descriptor that refers to a socket of type SOCK_STREAM or SOCK_SEQPACKET.
The backlog argument defines the maximum length to which the queue of pending connections for sockfd may grow. If a connection request arrives when the queue is full, the client may receive an error with an indication of ECONNREFUSED or, if the underlying protocol supports retransmission, the request may be ignored so that a later reattempt at connection succeeds.
可見與實(shí)現(xiàn)有關(guān)。
書的內(nèi)容還是很全的，但作者的觀點(diǎn)略感覺不對(duì)。 服務(wù)器中用信號(hào)來通知的，或者說來做異步的，就我了解是幾乎沒有。 作者去花了很多篇幅去介紹。
讓人感覺完全是為了湊字?jǐn)?shù)啊。 書名里面的“高性能”要打個(gè)折扣了
今天和某同學(xué)聊到面試題，他提到被某投行打擊很深的一個(gè)reservoir sampling問題。
于是我翻了翻。 大致意思在網(wǎng)上很容易找到。
難是難理解其中的思維點(diǎn)： 怎么發(fā)現(xiàn)的這個(gè)解法。
也就是如何詮釋你的歸納法的出發(fā)點(diǎn)。
目前我的總結(jié)是，對(duì)于這種無限問題，先設(shè)定一個(gè)基礎(chǔ)的通解。 即在n的時(shí)候成立，再想辦法證明當(dāng)n = n+1的時(shí)候，結(jié)論也成立，或與原結(jié)論存在一定的對(duì)應(yīng)關(guān)系 。
這樣就可以推導(dǎo)出來了。
干活四年， 有近兩年在打醬油。 昨天與某前輩聊了聊，也發(fā)現(xiàn)確實(shí)荒廢太多。
近期
1、重點(diǎn)把書完整的看一看。
2、把現(xiàn)有知識(shí)梳理一下，知道的與了解的都列一列。
3、有代碼相關(guān)的多寫一寫，加強(qiáng)一下。
4、有設(shè)計(jì)相關(guān)的多想一想，不要“原來如此”，而要多“為什么不這樣”。
一、數(shù)據(jù)結(jié)構(gòu)與算法分析
二、算法導(dǎo)論
三、unix環(huán)境高級(jí)編程
四、設(shè)計(jì)模式
五、linux 設(shè)備驅(qū)動(dòng)程序
六、數(shù)學(xué)之美
七、c和指針
八、boost程序庫完全開發(fā)指南
九、c++反匯編與逆向分析
十、python基礎(chǔ)教程
十一、編程珠璣
十二、程序員自我修養(yǎng)
十三、Linux 多線程服務(wù)端編程
十四、大規(guī)模分布式存儲(chǔ)系統(tǒng)（公司的）
十五、深入理解Linux內(nèi)核
十六、格蠹匯編
十七、深入Linux內(nèi)核架構(gòu)
十八、TCP/IP詳解
十九、UNIX網(wǎng)絡(luò)編程 套接字
二十、UNIX網(wǎng)絡(luò)編程 進(jìn)程間通信 （這兩本速度的看完扔了）
二十一、ddos攻擊與防范深度剖析
二十二、深入C++對(duì)象模型
二十三、Web前端黑客技術(shù)揭秘
今天碰到syslog 服務(wù) 過陣子就會(huì)dead的情況。 經(jīng)多次確認(rèn)，是打包的時(shí)候，腳本里面會(huì)執(zhí)行syslog reload 導(dǎo)致 。
而相同的配置文件restart 是OK的。
回來重新測(cè)試后，發(fā)現(xiàn)有個(gè)文件是不能讀取的。也就是 appArmor 的權(quán)限沒有配置。
經(jīng)再次回憶，是當(dāng)天晚上上線，本來應(yīng)該將snmp 的目錄 /var/log/* r , 寫到配置文件中，但由于認(rèn)為messages 同樣在這個(gè)目錄下，已經(jīng)可讀，就沒有配置。
最后導(dǎo)致syslog reload 就失敗。