[分享] .BRH 檔案格式與推文未讀標記問題

sony.tfcis.org-itoc-1629.txt

 作者  lantw44 ([#################])                        看板  itoc
 標題  [分享] .BRH 檔案格式與推文未讀標記問題
 時間  2017/11/04 Sat 21:35:59


在 sony.tfcis.org 上有個經常發生、也很多人回報過的 bug 是：
「當板上有多篇文章未讀，如果看了其中一篇，其他篇也會變已讀。」

因此一直以來都很好奇 Maple 的看板閱讀紀錄是怎麼實作的，為什麼會有辦法發生這種
問題。但是以前只知道會發生，不知道如何重現，也沒有嘗試 debug 過。

直到最近在某個看板按 v 設定所有文章 (W)前已讀後未讀 時才又注意到這個問題。我
發現選了這項以後，在游標前的某些文章也一起變成未讀了，猜測可能是推文未讀功能
造成的。我在網路上沒找到關於 Maple 的看板閱讀紀錄如何實作的文章，所以才決定直
接翻程式碼來看。又因為這段程式寫得不太容易看懂，才會想到要把看到的東西寫下來。

--------------------------------------1---------------------------------------

Maple 把看板閱讀紀錄存在個人資料夾下一個取名 .BRH 的檔案，從註解中可以得知 BRH
代表的是 board reading history。程式碼位在 maple/board.c，相關的函式和全域變數
都取名 brh_*，而巨集則都取名 BRH_*。

BRH 檔案是個 int32_t 的陣列，這是因為執行 Maple 的環境通常滿足這個條件：

    sizeof (time_t) 等於 sizeof (int) 等於 sizeof (int32_t) 等於 4

如果在沒有這個條件的環境下（例如 x86_64）則很可能會發生錯誤。程式中充分利用
time_t 和 int 大小相同的特性來存取 .BRH 這個 int32_t 陣列，也就是說可能會用
指向 int 的指標操作 time_t 格式的資料，或是把 time_t 的資料存入 int 變數中。

再來我們要知道在 Maple 裡，用來唯一識別看板的欄位是看板建立時間 (bstamp)，這
代表著整個站上不能有兩個看板是在同一秒鐘建立的。在看板閱讀紀錄中，用於識別文
章的也是時間標記 (chrono)。

接著我們還要知道 zap 是什麼意思。從線上說明文件中可以看出來，對應到 z 鍵的 zap
功能指的就是反訂閱某個看板。如果你 zap 了某個看板，就代表這個看板在預設情況下
不會出現在看板列表，看板閱讀紀錄也不會儲存，每次重新上站進到被 zap 掉的看板，
就會像是沒來過一樣，所有期限內的文章都被標記為未讀。

我們可以從看板屬性表中發現有個叫做「不可 zap」的屬性，這代表著設定了這個屬性的
看板無法被反訂閱，使用者一定會在看板列表中看到它，閱讀紀錄也一定會儲存。目前看
到有使用這個屬性的看板主要是全站公告的 0announce 板，可能是因為使用者上站後會
被要求要看完公告才能離開吧。

--------------------------------------2---------------------------------------

BRH 檔儲存多個看板閱讀紀錄的方法是將每個看板的閱讀紀錄直接接在一起，其中每個
看板的閱讀紀錄都是個 int32_t 陣列，因此整個 .BRH 檔也是個 int32_t 陣列。

有翻過 maple/board.c 的人應該會發現，程式中定義了一個幾乎沒有用到的 struct 叫
做 BRH。由於它存在的功能幾乎就只有當成註解來看，而且有些註解很容易被誤解，所以
這裡就不使用原始碼中的定義方式了。

已被 zap 掉的看板的閱讀紀錄長這個樣子：

typedef struct {
    int32_t    bstamp;      // 看板建立時間，用於唯一識別看板，sign bit 必為 1
} BRH_zapped;

未被 zap 掉的看板的閱讀紀錄長這個樣子：

typedef struct {
    int32_t    bstamp;      // 看板建立時間，用於唯一識別看板，sign bit 必為 0
    int32_t    bvisit;      // 上次閱讀時間
    int32_t    bcount;      // 已閱讀文章的時間區間資料長度，以 int32_t 為單位
    BRH_chrono intervals[]; // 已閱讀文章的時間區間列表，按照數值大小遞減排列
} BRH_unzapped;

typedef struct {
    int32_t    final;       // 區間結尾
    int32_t    begin;       // 區間開頭
} BRH_chrono;

這裡的區間都是閉區間，也就是 [ begin, final ]，頭尾都包含的意思。

由於一個區間必定包含頭尾兩個數字，所以看了上面的定義可能會以為 bcount 永遠是
偶數。事實上只有使用者目前正在閱讀的看板的 bcount 一定會是偶數，其他未在使用
中的看板則有可能是奇數。這是因為當 final 和 begin 相同時，會省去 begin 並把
final 的 sign bit 設定為 1 作為標記以節省空間。

假設原本的 bcount 和 intervals 是：

       6      40      37      20      20      12       9

代表時間在 [9, 12]、[20, 20]、[37, 40] 的文章都已經看過了。只要文章時間是 9、
10、11、12、20、37、38、39、40 就會被標記成已讀。

進入別的看板以後這個列表就會被處理成：

       5      40      37     *20      12       4

其中 * 記號表示 sign bit 被用位元運算設定成 1。這也代表著把區間簡單寫成兩個數
字並不完全正確，因為有些時候數字不會成對。

上面所列的 struct 中的變數名稱在程式中幾乎不會出現，因為通常都是直接對指標做
加減法。假設 head 這個 int* 變數指向某個看板閱讀紀錄的開頭，那麼 *head 就是取
bstamp 的值，list = head + 2 然後 *list 就表示取 bcount 的值，有時候也可能是
連續很多次 *head++ 或 *++head 這樣。

--------------------------------------3---------------------------------------

再來開始解釋各個全域變數和函式的功能和簡單的實作細節，巨集我想就不用講了，旁邊
有註解，BRH_MASK 就是 INT32_MAX 同時也可以拿來做 and 運算去掉 sign bit，而下面
的 BRH_SIGN 很明顯就是操作 bstamp 和 final 的 sign bit 用的。

底下的「資料類型」都是我自己改過的，原本的程式一下子 time_t 一下子 int，但很多
地方是只要不是 int32_t 就會壞掉，所以直接改寫成 int32_t。別問我為什麼陣列索引
值是用 int 不是 size_t，我也不知道，它就這樣寫的……

先列全域變數，不重要的就跳過了：

Linkage     資料類型    名稱
internal    int32_t*    brh_base
internal    int32_t*    brh_tail
internal    int         brh_size

假設這是我們用來把 .BRH 檔讀進來使用的 buffer，總長度是 brh_size：

brh_base                                         brh_tail
↓                    其他看板的紀錄                 ↓     目前正在讀的看板
├───────────────────────────────────────────────────┼───────────────────────┤

其中「其他看板的紀錄」的時間區間是經過 final sign bit 壓縮的。
而「目前正在讀的看板」的時間區間是沒有壓縮的，可以保證 bcount 是偶數。

再列函式，一樣也是不重要的就跳過：

Linkage     回傳值類型  名稱        參數
internal    void        brh_load    (void)
external    void        brh_save    (void)
internal    void        brh_put     (void)
external    void        brh_get     (int32_t 看板建立時間, int 看板索引值)
external    bool        brh_unread  (int32_t 文章時間)
external    void        brh_visit   (int32_t 全部已讀 或 全部未讀 或 文章時間)
external    void        brh_add     (int32_t 前篇, int32_t 這篇, int32_t 後篇)

最前面兩個 brh_load 和 brh_save 我想名稱已經說明一切了，就是從 .BRH 檔案讀取看
板閱讀紀錄，或是把看板閱讀紀錄寫回 .BRH 檔用的。

brh_put 的功能是把「目前正在讀的看板」做 final sign bit 壓縮，然後塞回「其他看
板的紀錄」的位置。它會在 brh_save 存檔和 brh_get 切換看板時被呼叫。

brh_get 的功能是從「其他看板的紀錄」中找出準備要讀的看板，解開 final sign bit
壓縮再放到最後的「目前正在讀的看板」位置。

brh_unread 的功能是判斷目前看板上的某篇文章是否已經讀過，作法是檢查文章時間是
否落在已閱讀的時間區間中。因為只處理目前正在讀的看板，所以它假設所有 sign bit
壓縮都已經解開。

brh_visit 就是在看板按 v 設定已讀未讀狀態的實作，傳入的參數可能有：
    0 表示全部已讀，就是清除所有時間區間再把 [ 0, 現在時間 ] 加進去。
    1 表示全部未讀，就是清除所有時間區間再把 [ 0, 1 ] 加進去。
    其他表示將參數解讀為時間，之前已讀之後未讀，實作同上。

brh_add 是設定某一篇文章為已讀。為了節省空間，把多個區間盡可能壓成一個，所以除
了目前這篇的時間以外，還要傳入前一篇和後一篇的時間。為了做到這點，brh_add 會假
設目前的看板上在「目前這篇和前一篇」以及「目前這篇和後一篇」之間都是沒有其他文
章的。這也代表前一篇和後一篇不能亂填，必須是「時間上前後緊鄰」的兩篇文章。

目前的實作在閱讀文章時傳入的參數是「位置上的前後一篇」，也就是說假設你準備要看
第 321 篇文，那傳入 brh_add 的三個參數分別就是第 320、321、322 篇文章的時間。
這在沒有推文未讀標記的功能以前是沒有問題的，因為文章只能從最後面加入，不能插在
中間（原本 itoc 版本的 Maple 沒有移動文章的功能，即使有平常也不該拿出來用）。

從以前留下的修改紀錄來看，sony.tfcis.org 大概在 11 年前加入推文未讀標記功能，
使得這樣的做法可能出錯。因為未讀標記的實作方法是重建一篇文章，而這篇文章會用
hard link 連結到原本的文章，文章的時間更新為推文時的時間。這代表著看板中文章
的先後順序不再符合時間順序，但 post_history 仍然用原本的方式，固定找位置上的
前後一篇傳入 brh_add，於是就很有可能出錯了。

目前 brh_add 的實作方式考慮了以下幾種狀況：

1
                        後一篇  目前這篇           前一篇
                          ↓       ↓                  ↓
────────────┼─────────┼─────────────────────────┼─────────┼───────→ 時間遞減
         final 區間一 begin                  final 區間二 begin

那就變成
                        後一篇  目前這篇           前一篇
                          ↓       ↓                  ↓
────────────┼─────────┼───────────┼───────────────────────┼───────→ 時間遞減
         final 區間一 begin       final     區間二     begin

直接把後面的往前移，區間總數不變。

2
               後一篇           目前這篇           前一篇
                 ↓                ↓                  ↓
────────────┼─────────┼─────────────────────────┼─────────┼───────→ 時間遞減
         final 區間一 begin                  final 區間二 begin

那就變成

               後一篇           目前這篇           前一篇
                 ↓                ↓                  ↓
────────────┼─────────────────────────────────────────────┼───────→ 時間遞減
         final                   區間一                   begin

兩個區間合併，區間總數 -1。

3
               後一篇           目前這篇  前一篇
                 ↓                ↓         ↓
────────────┼─────────┼─────────────────────────┼─────────┼───────→ 時間遞減
         final 區間一 begin                  final 區間二 begin

那就變成

               後一篇           目前這篇  前一篇
                 ↓                ↓         ↓
────────────┼─────────────────────┼─────────────┼─────────┼───────→ 時間遞減
            final    區間一    begin         final 區間二 begin

直接把前面的往後移，區間總數不變。

4
                        後一篇  目前這篇  前一篇
                          ↓       ↓         ↓
────────────┼─────────┼─────────────────────────┼─────────┼───────→ 時間遞減
         final 區間一 begin                  final 區間二 begin

那就變成

                        後一篇  目前這篇  前一篇
                          ↓       ↓         ↓
────────────┼─────────┼───────────┼─────────────┼─────────┼───────→ 時間遞減
         final 區間一 begin     區間二       final 區間三 begin
                                final
                                begin

插入一個頭尾相同的區間，區間總數 +1。

--------------------------------------4--------------------------------------

所以說如果文章順序不等於時間順序呢？這裡有個簡單的例子。

假設看板上有連續三篇文章還沒看過，除了這三篇以外的其他文章都已經看過了。依照
文章在看板上的先後順序，把它取名 1、2、3，數字越小表示越早發文。

這三篇文章的時間先後順序是：

       2               3               1
       ↓               ↓               ↓
────────────────────────────────────────────────┼───────────┼─────→ 時間遞減
                                             final 其他區間 begin

我們先看 2 號文，前後篇都不在區間內，屬於狀況 4，插入一個區間：

       2               3               1
       ↓               ↓               ↓
───────┼────────────────────────────────────────┼───────────┼─────→ 時間遞減
   新的區間                                  final 其他區間 begin
     final
     begin

接著再看 1 號文，前篇在區間內，後篇也在區間內，屬於狀況 2，合併前後兩個區間：

       2               3               1
       ↓               ↓               ↓
───────┼────────────────────────────────────────────────────┼─────→ 時間遞減
     final                  合併後的區間                  begin

結果 3 號文雖然沒有看過，但在看完 1 號文後，未讀標記就消失了。

於是這個問題有解決方法嗎？我還沒測試過其他使用 Maple 3.10 itoc 的 BBS 站是否也
有相同的問題，但有發現 itoc 看板精華區裡的「尚未收錄進標準版的功能」有提到類似
問題，解法是每次推文都掃過整個看板的文章索引，找出真正時間相鄰的文章。

這解法聽起來在有大量文章的看板上效能會很慘，那篇文章結尾也寫著：拼 I/O 啊。

我想可能比較好的解法是取消狀況 1、2、3 的判斷，只留下狀況 4，這樣實際上就不再
是區間，而是記錄個別文章的時間了。但另外一個問題是要怎麼把已經消失的文章時間刪
掉？或許就延遲到下站的時候再掃過看板文章索引來檢查吧，這樣至少是每次登入只做一
次，而不是每次推文都做。

--
               ─┼───╮                  ╭──────────────╮
                │   │台南一中．索尼小站∣sony.TFcis.org│  │
                    ╰──────────────────╯              ╰──┼─
               by lantw44 from  172.20.7.2 (tinc: lantw44)