Linux mlocate源碼分析：updatedb
在Linux的文件查找命令中，mlocate提供的locate命令在單純進行路徑名名查找時有著顯著的效率優勢，因為mlocate預先對磁碟文件進行掃描並存儲到一個資料庫文件中，查找時只需要檢索資料庫而即可。本文主要對mlocate工具資料庫的更新（updatedb）進行分析。
基礎知識
locate命令需要安裝mlocate來獲得
locate命令基礎用法：點此鏈接
mlocate的配置：點此鏈接。這裡特別說一下 PURNE_BIND_MOUNTS，大部分文章只說這是限制搜索，沒說具體意思，其實PURNE_BIND_MOUNTS=yes會跳過bind mount，至於什麼是bind mount，使用過docker的同學應該知道一個容器通常會產生一個掛載卷，在df -h中可以看到，通常如下圖
這就是一個bind mount，它是對本地目錄的重複掛載，沒有必要多索引一次，所以 PURNE_BIND_MOUNTS 保留yes就好。
updatedb的執行策略
mlocate是通過執行updatedb命令來建立/更新資料庫的，除了手動執行外，作業系統會每日進行更新，但在各用戶的crontab里是看不到的，因為updatedb的定時執行使用了anacron實現。
anacron介紹參見這裡，updatedb的執行定義在/etc/cron.daily/mlocate里：
# vim /etc/cron.daily/mlocate #! /bin/bash set -e [ -x /usr/bin/updatedb.mlocate ] || exit 0 if which on_ac_power >/dev/null 2>&1; then ON_BATTERY=0 on_ac_power >/dev/null 2>&1 || ON_BATTERY=$? if [ "$ON_BATTERY" -eq 1 ]; then exit 0 fi fi # See ionice(1) if [ -x /usr/bin/ionice ] && /usr/bin/ionice -c3 true 2>/dev/null; then IONICE="/usr/bin/ionice -c3" fi # See nocache(1) NOCACHE= if [ -x /usr/bin/nocache ]; then NOCACHE="/usr/bin/nocache" fi flock --nonblock /run/mlocate.daily.lock $NOCACHE $IONICE nice /usr/bin/updatedb.mlocate
即在updatedb命令沒有運行，且插入電源的情況下，首先設定了io優先順序（-c3表示只在其他程式無磁碟io時執行），然後以默認優先順序執行updatedb命令。
updatedb過程分析
mlocate相較於前輩slocate實現了增量更新。總的來說，mlocate基於對目錄的mtime和ctime是否發生了變更的判斷，來決定是否要進入目錄內進一步索引內容，流程圖如下：
下面結合源碼說明，從main函數開始（部分程式碼）：
unlink_init (); new_db_open (); dir_state_init (&scan_dir_state); if (chdir (conf_scan_root) != 0) error (EXIT_FAILURE, errno, _("can not change directory to `%s'"), conf_scan_root); if (lstat (".", &st) != 0) error (EXIT_FAILURE, errno, _("can not stat () `%s'"), conf_scan_root); cwd_fd = -1; scan (conf_scan_root, &cwd_fd, &st, ".");
main函數在進行了一系列初始化和檢測後，就進入了scan函數；全部程式碼太長，這裡只截取必要的部分：
1 /* "relative" may now become a symlink to somewhere else. So we use it only 2 in safe_chdir (). */ 3 entries_mark = obstack_alloc (&scan_dir_state.data_obstack, 0); 4 dir.path = path; 5 time_get_ctime (&dir.time, &st); 6 time_get_mtime (&mtime, &st); 7 if (time_compare (&dir.time, &mtime) < 0) 8 dir.time = mtime; 9 while (old_dir.path != NULL && (cmp = dir_path_cmp (old_dir.path, path)) < 0) 10 { 11 old_dir_skip (); 12 old_dir_next_header (); 13 } 14 did_chdir = false; 15 have_subdir = false; 16 if (old_dir.path != NULL && cmp == 0 17 && time_compare (&dir.time, &old_dir.time) == 0 18 && (dir.time.sec != 0 || dir.time.nsec != 0)) 19 { 20 res = copy_old_dir (&dir); 21 if (res != -1) 22 { 23 have_subdir = res; 24 old_dir_next_header (); 25 goto have_dir; 26 } 27 } 28 if (time_is_current (&dir.time)) 29 { 30 /* The directory might be changing right now and we can't be sure the 31 timestamp will be changed again if more changes happen very soon, mark 32 the timestamp as invalid to force rescanning the directory next time 33 updatedb is run. */ 34 dir.time.sec = 0; 35 dir.time.nsec = 0; 36 } 37 did_chdir = true; 38 if (safe_chdir (cwd_fd, relative, &st) != 0) 39 goto err_chdir; 40 res = scan_cwd (&dir); 41 if (res == -1) 42 goto err_chdir; 43 have_subdir = res; 44 have_dir: 45 write_directory (&dir); 46 if (have_subdir != false) 47 { 48 if (did_chdir == false) 49 { 50 did_chdir = true; 51 if (safe_chdir (cwd_fd, relative, &st) != 0) 52 goto err_entries; 53 } 54 scan_subdirs (&dir, &st); 55 }
這裡涉及到了dir，它是一個directory類型，其定義如下：
/* A directory in memory, using storage in obstacks */ struct directory { struct time time; void **entries; /* Pointers to struct entry */ size_t num_entries; char *path; /* Absolute path */ };
由此可見，directory中記錄了該path下含有哪些子目錄/文件（entries），以及包含的總數（num_entries），以及最重要的path本身。基本滿足了locate命令查詢時所需的必要資訊。
回到scan函數，它傳入了一個path參數，函數首先獲取這個path的ctime和mtime，取其中最大者為directory結構體的time，因為這可以反映該path最後一次被修改的時間，而後它將old_dir.path和path進行了一個對比。
old_dir來自於old_db，它的數據結構是Obstack，本質是一個棧，在項目中發揮的作用類似一個記憶體資料庫，儲存著上次磁碟掃描的結果。簡要地理解，整個磁碟的路徑字元串以深度遍歷的順序依次存儲在其中，old_dir.path就是old_db的游標當前指向的路徑，而path為此次掃描程式正在讀取的當前路徑。兩個路徑比較結果小於0則把old_db游標指向下一個路徑；比較函數為dir_path_cmp，這個函數定義在lib.c中：
/* Initialize dir_path_cmp_table */ void dir_path_cmp_init (void) { size_t i; unsigned char val; dir_path_cmp_table[0] = 0; dir_path_cmp_table['/'] = 1; val = (unsigned char)2; for (i = 1; i < ARRAY_SIZE (dir_path_cmp_table); i++) { if (i != '/') { dir_path_cmp_table[i] = val; val++; } } assert (val == 0); } /* Compare two path names using the database directory order. This is not exactly strcmp () order: "a" < "a.b", so "a/z" < "a.b". */ int dir_path_cmp (const char *a, const char *b) { while (*a == *b && *a != 0) { a++; b++; } { verify (sizeof (int) > sizeof (unsigned char)); /* To rule out overflow */ } return ((int)dir_path_cmp_table[(unsigned char)*a] - (int)dir_path_cmp_table[(unsigned char)*b]); }
可以看出，dir_path_cmp返回負值的條件是，path的ascii字典序大於old_dir.path（’/’字典序被定義為1），這包含了兩種情況：
- path是old_dir.path的一個子目錄
- path與old_dir.path不存在上下級關係（同級或不同級），且path的字典序大於old_dir.path，比如/a和/b這種
由於scan的路徑掃描是深度優先的（後面會講到），所以當scan掃到了path時，其父目錄一定被掃描過了，因而old_dir.path可以跳過；對於情況2，由於old資料庫中的路徑是嚴格按照字典序排列的，那這種情況的出現只可能由兩種原因導致：
- 舊資料庫中的游標滯後了，所以需要跳過來趕上當前掃描的進度（情況1就是它的一個情境）
- 舊資料庫中的path已經不存在了（刪除或改名），自然可以跳過
繼續往後走，對於old_db中存在的路徑，用time_compare比較了下最後修改時間（綜合了mtime和ctime，上面有說明），如果時間也一致就不對這個目錄內的文件進一步掃描了，直接copy_old_dir把old_db里上次記錄的資訊拿過來，這使得mlocate極大的減少了updatedb時的時間開銷；但子目錄還要遵照正常的深度優先順序遍歷（25行goto have_dir），因為子目錄里的修改並不會反映在父目錄的ctime和mtime上。
對於old_db中不存在的路徑，即是上次掃描後新增（廣義）的文件/目錄，於是scan_cwd (&dir)掃一遍目錄裡面，然後同樣走到have_dir，have_dir這裡先write_directory (&dir)把已獲得的路徑資訊（不管是掃描得到的還是從舊資料庫拷貝來的）寫入一個新資料庫里，如果有子目錄的話，則要scan_subdirs (&dir, &st)進入掃描，基本是上述過程的重複；而scan_subdirs是一個遞歸函數（嚴格來說是scan_subdirs調用了scan，算間接遞歸），這裡就理解了為什麼說掃描是一個深度優先的過程。
總結
本文分析了mlocate工具中的updatedb。一言以蔽之，updatedb就是按acsii字元序深度優先遍歷整個磁碟，建立了一個順序表，並定時更新。與直覺不同的是，updatedb不是在舊資料庫的基礎上更新，而是重建資料庫，只是對於未修改目錄利用舊資料庫里的資訊節省了部分磁碟掃描時間。另外值得注意的是，updatedb的掃描並不會影響文件和目錄的atime，因為其對文件使用了C函數lstat，對目錄實現了opendir_noatime。
有機會的話，下篇文章會講講mlocate的檢索（locate）原理。
附：一個locate命令使用技巧
當你想查找路徑包含”ponny”的目錄/文件時，locate ponny可以滿足你要求，但一旦關鍵字里混進了空格，比如”James Lee”，你會發現即便是locate “James Lee”也找不出想要的結果。此時，在關鍵字前後各加一個’*’，即locate “*James Lee*”即可。
