2015年5月30日
#
復(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;
}
在本實現(xiàn) 里面， 直接使用了最后一個元素作為基準(zhǔn)。
在選擇基準(zhǔn)時其實是有多種方式的。1）選第一個，不推薦。2）算最后一個，不推薦。3）選首、尾、中的中間值。4）隨機選擇。
選擇后將跑一趟比較，結(jié)果是左側(cè)為小的數(shù)，右側(cè)為大的數(shù)，原理是i,j 當(dāng)數(shù)小于基準(zhǔn)是則與左右的i 對換，這樣保證了i左側(cè)小于p i 到j(luò) 之間是大小p 的。
對于p 無需再排了。
需要特別注意的是partition 里面的元素位置與quicksort 分段是有關(guān)系的。 如果在partition 里面處理了last 那么 在分段時其實last 就不用了。
2015年5月16日
#
目的：重新梳理TCP，全局理解協(xié)議中的細(xì)節(jié)，知道是怎樣實現(xiàn)的，理解為什么要這樣做，了解可能會帶來什么問題。
PS:圖片有空了慢慢貼。
簡要介紹：
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)機制、重傳機制。
3） 首部的檢驗和。
4） 網(wǎng)絡(luò)層的IP數(shù)據(jù)報可能會失序，因此TCP需要將數(shù)據(jù)進(jìn)行重新排序。
5） 數(shù)據(jù)報可能會重復(fù)，必須恰當(dāng)?shù)膩G棄重復(fù)的數(shù)據(jù)報。
6） TCP提供流量控制，可根據(jù)另一端的緩沖區(qū)情況發(fā)送恰當(dāng)?shù)臄?shù)據(jù)（滑動窗口協(xié)議）。
7） TCP協(xié)議對字節(jié)流不作解釋。由應(yīng)用層對數(shù)據(jù)進(jìn)行語義上的解釋。
隨便抓個包：
IP數(shù)據(jù)頭
TCP數(shù)據(jù)頭
頭部中比較重要的數(shù)據(jù)結(jié)構(gòu)
源端口，目的端口，序號，確認(rèn)序號。 標(biāo)志位，窗口大小。
URG：緊急指針，一般用不上，忽略。
ACK：經(jīng)常用，接收端發(fā)給源端，確認(rèn)前一個包已收到。
PSH：個人沒怎么碰到過。
RST：可以理解為重置連接，普通情況下當(dāng)目標(biāo)端口未開放會發(fā)送此RST回來，此外，連接中間的防火墻等網(wǎng)絡(luò)設(shè)備也會發(fā)。
SYN：發(fā)起連接的標(biāo)志，SYN Flood是基于的一種DOS攻擊手法。
FIN：shutdown 時發(fā)送，告訴對方，我這邊完成了，要送掉連接了。
1、 TCP連接的建議，三步握手。
1） 源端發(fā)送SYN到服務(wù)器，表示喜娃懷與服務(wù)器的某個端口建立TCP連接，在TCP首部帶上初始的序號（client ISN）。此報文中設(shè)置SYN=1；
2） 服務(wù)器返回SYN包，帶上服務(wù)器的初始序號（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)隨時間變化，避免網(wǎng)絡(luò)中被延遲的分組被重新傳遞后導(dǎo)致的錯誤解釋。
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ā)送時，無需發(fā)放兩個包，可以在一個包里面同時設(shè)置FIN+ACK，也就是上面的截圖。2）當(dāng)僅一端調(diào)用shutdown，另一端還存在數(shù)據(jù)發(fā)送時，存在半關(guān)閉連接的情況。即第2步結(jié)束后，B端繼續(xù)發(fā)送數(shù)據(jù)，A端對這些數(shù)據(jù)仍然發(fā)送ACK，一直到B端發(fā)送FIN。
以下是一個簡單的client + server 測試代碼，通過簡單的Sleep可以看出， 當(dāng)收到FIN包時，緩沖區(qū)的數(shù)據(jù)仍然存在，僅在后面多了一個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()
2015年5月5日
#
《 程序員必讀的職業(yè)規(guī)劃書》
最開始好像是在微博上看到pdf版本，挺長挺有層次的一篇文章。
最近半年也是有點動的想法，但其實在規(guī)劃這件事情上做的不夠， 有個參考指南可以慢慢對比一下自身
2015年2月6日
#
因為某wall的原因，大家需要一個通道。
現(xiàn)在比較好的辦法是使用hk或其他地方的vps ，然后搭個ssh過去，再使用Sock代理。
putty 已自帶ssh通道的功能。但其不支持記住密碼。很煩。
網(wǎng)上傳的很多教程中使用了 myentunnel 。 結(jié)果下載后一下，這逗比工具使用的還是putty，既然如此，何必使用額外的工具。
putty雖然記住密碼不方便，但使用SSH自帶的證書功能，也是可以實現(xiàn)自動登錄的~
1、使用puttygen 生成密鑰對。 此處的 key passphrase 填寫后，最終的private key 使用需要密碼。。因此可以不填。
2、將public key 放入 /home/user/.ssh/authorized_keys中。此處需確保 .ssh authorized_keys 對其他用戶僅可讀。 如755，否則無法使用。
3、在putty的Connection -> ssh -> auth 處可以選擇private key .
4、在Connection -> Data 處可選填auto-login username。
5、為確保不會自動掉線，Connection keepalive 填上非0。如30
6、再save就行啦。 后面再使用就方便了。
不過此種方法因為需要使用私鑰文件，且對私鑰文件無passphrase保護，需保證私鑰的安全性，如放在私密的U盤中，僅使用時插上，離開時帶走。
2015年1月30日
#
為Linux下線程加個名字。同樣的Windows 也可以干。 chrome 的源碼中有使用到這個trick，raise 一個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)
{
}
}
2014年10月21日
#
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.
可見與實現(xiàn)有關(guān)。
書的內(nèi)容還是很全的，但作者的觀點略感覺不對。 服務(wù)器中用信號來通知的，或者說來做異步的，就我了解是幾乎沒有。 作者去花了很多篇幅去介紹。
讓人感覺完全是為了湊字?jǐn)?shù)啊。 書名里面的“高性能”要打個折扣了
今天和某同學(xué)聊到面試題，他提到被某投行打擊很深的一個reservoir sampling問題。
于是我翻了翻。 大致意思在網(wǎng)上很容易找到。
難是難理解其中的思維點： 怎么發(fā)現(xiàn)的這個解法。
也就是如何詮釋你的歸納法的出發(fā)點。
目前我的總結(jié)是，對于這種無限問題，先設(shè)定一個基礎(chǔ)的通解。 即在n的時候成立，再想辦法證明當(dāng)n = n+1的時候，結(jié)論也成立，或與原結(jié)論存在一定的對應(yīng)關(guān)系 。
這樣就可以推導(dǎo)出來了。
2014年10月19日
#
干活四年， 有近兩年在打醬油。 昨天與某前輩聊了聊，也發(fā)現(xiàn)確實荒廢太多。
近期
1、重點把書完整的看一看。
2、把現(xiàn)有知識梳理一下，知道的與了解的都列一列。
3、有代碼相關(guān)的多寫一寫，加強一下。
4、有設(shè)計相關(guān)的多想一想，不要“原來如此”，而要多“為什么不這樣”。
2014年9月22日
#
一、數(shù)據(jù)結(jié)構(gòu)與算法分析
二、算法導(dǎo)論
三、unix環(huán)境高級編程
四、設(shè)計模式
五、linux 設(shè)備驅(qū)動程序
六、數(shù)學(xué)之美
七、c和指針
八、boost程序庫完全開發(fā)指南
九、c++反匯編與逆向分析
十、python基礎(chǔ)教程
十一、編程珠璣
十二、程序員自我修養(yǎng)
十三、Linux 多線程服務(wù)端編程
十四、大規(guī)模分布式存儲系統(tǒng)（公司的）
十五、深入理解Linux內(nèi)核
十六、格蠹匯編
十七、深入Linux內(nèi)核架構(gòu)
十八、TCP/IP詳解
十九、UNIX網(wǎng)絡(luò)編程 套接字
二十、UNIX網(wǎng)絡(luò)編程 進(jìn)程間通信 （這兩本速度的看完扔了）
二十一、ddos攻擊與防范深度剖析
二十二、深入C++對象模型
二十三、Web前端黑客技術(shù)揭秘
2014年7月4日
#
今天碰到syslog 服務(wù) 過陣子就會dead的情況。 經(jīng)多次確認(rèn)，是打包的時候，腳本里面會執(zhí)行syslog reload 導(dǎo)致 。
而相同的配置文件restart 是OK的。
回來重新測試后，發(fā)現(xiàn)有個文件是不能讀取的。也就是 appArmor 的權(quán)限沒有配置。
經(jīng)再次回憶，是當(dāng)天晚上上線，本來應(yīng)該將snmp 的目錄 /var/log/* r , 寫到配置文件中，但由于認(rèn)為messages 同樣在這個目錄下，已經(jīng)可讀，就沒有配置。
最后導(dǎo)致syslog reload 就失敗。