3.30.2010

從 select.h 學 bit mask

最近在寫的程式需要同時開很多檔案以便做 N-way merge。為了記錄已經 open 了哪些 file descriptors,就必須要有一個資料結構可以儲存這些開開關關的資訊。
對於處理這種「不是 on,就是 off」狀態的資訊,最直覺的做法就是用 bit mask。 在 FreeBSD amd64 中,一個 long 型態的變數是 8 bytes, 64 bits,所以一個 long 就有 64 個 bit flags 可以用,也就是可以記錄由 0 ~ 63 的 fd 編號:
        long fd_mask;
        /* set on bit no.64 */
        fd_mask |= 1 << 63;
        /* set on bit no.1 */
        fd_mask |= 1 << 0;

假如需要記錄的 fd 個數超過 64 個,那就必須另外宣告一個 long 型態的變數來使用。而把相同功能的變數放在一起最直覺的方式就是用陣列,現在要記錄的是 1024 個 fds(0~1023),那就宣告一個 16 個 long 的陣列:
        long fd_setsize = 1024;
        /* 1024 / 64 = 16 */
        long fd_mask[16];

接著遇到的問題是,對於一個 fd(0~1023),我怎麼知道要把它定位在「哪一個 longlayer)的哪一個 bit(position)」?透過除法取餘數可以分別解決這兩個定位的問題,所以:
        long fd_setsize = 1024;
        long fd_mask[16];

        int x;
        int layer = x / 64;
        int position = x % 64;

有這樣的知識後,我們就可以產生一個設定 bit mask 的函式:
        long fd_setsize = 1024;
        long fd_mask[16];
        void fd_set(fd, long *fd_set) {
                fd_set[fd_setsize / 64] |= (1 << (x % 64));
        }
        /* will set 1 on layer 0, bit no.1 */
        fd_set(0, fd_mask);
        /* will set 1 on layer 15, bit no.64 */
        fd_set(1023, fd_mask);

這也是在 select.h 中,FD_SET 巨集的概念,其它的 FD_ZEROFD_ISSETFD_CLR 也都採用相同的定位方式。
還有一個問題在於:如何宣告一開始的 long array 要多大?
如果要處理的 fd 個數可以有 1024 個,那麼由 1024 / 64 得到的值,就會是剛好的大小;但是如果要處理的 fd 個數是 1025 個,那麼除出來的值(沒有小數),會跟上面一樣,因此得到錯誤的結果(需要 17 而不是 16)。
        #define how_big(x) (x) / 64
        long fd_mask[how_big(x)];
        /* x = 64, fd: 0 ~ 63 */
        => long fd_mask[1];
        /* x = 65, fd: 0 ~ 64 */
        => long fd_mask[1]; /* wrong, we need 2 layers. */

如果把純的除法改成這樣,那問題就解決了:
        #define how_big(x) ((x) + 64 - 1) / 64
        long fd_mask[how_big(x)];
        /* x = 64, fd: 0 ~ 63 */
        => long fd_mask[1];
        /* x = 65, fd: 0 ~ 64 */
        => long fd_mask[2];

實際上,這樣的函數是一個 ceiling function,剛好符合這個問是的特性:
        z = (x + (y - 1)) / y,  y = 64
        x = 0, z => 0
        x = 1~64, z => 1
        x = 65~128, z => 2

以上,是從 select.h 裡面學到的技巧…。

沒有留言: