Tag: parser

Ruby 3.3.0 的消息

也是有點奇特，年底的慣例長假反而釋出 Ruby 3.3.0：「Ruby 3.3.0 Released」。

整體看起來比較大的改變有兩組，一塊是 parser 相關的消息，包括了 GNU Bison 換成 Lrama，兩個都是 LALR parser，但後者是 Ruby 寫的。

另外一塊是 JIT 相關的消息，包括了 YJIT 的持續進步，以及 RJIT 的引入。

看起來有在用 Ruby 的大型站台都跳進去幫 YJIT 發展了，這邊應該是正循環，會有更多的 feedback 與實作進來改善 YJIT。

而 RJIT 看起來是個實驗性質的東西，目前只會在 x86-64 上生效，不知道目標會是什麼：

Introduced a pure-Ruby JIT compiler RJIT and replaced MJIT.

GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜，來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢，而有人一路 reverse engineering 找出問題並且解決：「How I cut GTA Online loading times by 70%」，對應的 Hacker News 討論有提到其他有趣的事情也可以看看：「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差，但光開啟 GTA Online 就需要六分鐘，網路上甚至有辦投票蒐集大家的等待時間，發現也有很多人反應類似的問題：

接下來就開始 reverse engineering 了，先觀察各種狀態後發現是卡在 CPU，而不是網路或 Disk I/O，然後就拿出 Luke Stackwalker 這個工具 profiling，不過因為沒有 debug symbol 幫忙 group，所以只能人工判斷後，可以看到兩個問題：

第一個問題發現效能是卡在 strlen()，而 call stack 可以看出來是從 sscanf() 一路打進去的：

反追發現是在處理 10MB 的 JSON 檔造成的，裡面 sscanf() 因為拉出 strlen()，於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB，掃到後面會愈來愈少，平均下來應該是 5MB)：

第二個問題產生的時間會在第一個問題跑完後，另外看問題的性質，應該跟第一個 JSON 處理有關，他會把 JSON 處理過的資料丟進 array，每個 entry 長這樣：

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的，但問題在於他需要判斷 entry 是否重複，卻沒有用 hash 或是 tree 的結構，而這邊大約有 63k 筆資料，用 array 實做就產生了 O(n^2) 的演算法：

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser，但這太複雜，所以他用 workaround 解：把 strlen() 包起來，針對長字串加上一層 cache：

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過，因為資料本身不重複：

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒，還是偏慢，但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束，有人一路去挖，發現其實 sscanf() 的效能地雷已經不是第一次了：YAML 的 Parser 也中過一樣的問題：「Parsing can become accidentally quadratic because of sscanf」，這篇也一樣上了 Hacker News：「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題：「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來，應該是大家把同樣的演算法拿來實做：

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

robots.txt 的標準化

雖然聽起來有點詭異，但 robots.txt 的確一直都只是業界慣用標準，而非正式標準，所以各家搜尋引擎加加減減都有一些自己的參數。

在經過這麼久以後，Google 決定推動 robots.txt 的標準化：「Formalizing the Robots Exclusion Protocol Specification」，同時 Google 也放出了他們解讀 robots.txt 的 parser：「Google's robots.txt Parser is Now Open Source」，在 GitHub 的 google/robotstxt 這邊可以取得。

目前的 draft 是 00 版，可以在 draft-rep-wg-topic-00 這邊看到，不知道其他搜尋引擎會給什麼樣的回饋...

Mercury Web Parser 開源

看到「Mercury Goes Open Source!」這篇，Postlight 的團隊開源了 Mercury Web Parser，程式碼在 GitHub 上的 postlight/mercury-parser 可以取得。

這個版本是用 Node.js 寫的，可以從範例看出用法以及結果：

import Mercury from '@postlight/mercury-parser';
Mercury.parse(url).then(result => console.log(result););
{
  "title": "Thunder (mascot)",
  "content": "<div><div><p>This is the content of the page!</div></div>",
  "author": "Wikipedia Contributors",
  "date_published": "2016-09-16T20:56:00.000Z",
  "lead_image_url": null,
  "dek": null,
  "next_page_url": null,
  "url": "https://en.wikipedia.org/wiki/Thunder_(mascot)",
  "domain": "en.wikipedia.org",
  "excerpt": "Thunder Thunder is the stage name for the horse who is the official live animal mascot for the Denver Broncos",
  "word_count": 4677,
  "direction": "ltr",
  "total_pages": 1,
  "rendered_pages": 1
}

先前其他的軟體與服務可以參考「Evaluating Text Extraction Algorithms」這篇的整理與比較，不過這篇連原網站都不見了... 只能從 Internet Archive 上翻出來。

這個主題有不少團隊都做過 (給一個 html 網頁，抓出實際的內容塊落)，但也死了不少團隊... 比較有印象的是 Readability，在 2016 年收掉了：「The Readability bookmarking service will shut down on September 30, 2016.」。

要撈資料可以拿來用...

GitHub Actions

GitHub 藉著 open source 函式庫，說明了目前還在 beta 的 GitHub Actions 是什麼：「An open source parser for GitHub Actions」。

GitHub Actions 是 GitHub 規劃將自動化設定包裝成設定檔的服務，以往是透過 GitHub 網站上設定，現在則是把這些設定放到 git repository 內。

重點在於 Actions 其實是透過 HCL (HashiCorp Configuration Language) 語法定義：

All Actions workflow files are valid HCL, but not all HCL files are valid workflows.

JSON 的 Object 裡 Key 重複的問題

tl;dr：不要亂來啦... 這是 UB (Undefined behavior) 的一種。

因為看到這則 tweet，所以去查一下 JSON 的資料：

首先是找標準是什麼。在維基百科的 JSON 條目裡提到了有兩份標準，一份是 RFC 7159，一份是 ECMA-404：

Douglas Crockford originally specified the JSON format in the early 2000s; two competing standards, RFC 7159 and ECMA-404, defined it in 2013. The ECMA standard describes only the allowed syntax, whereas the RFC covers some security and interoperability considerations.

ECMA-404 裡面就真的只講語法沒講其他東西，而在 RFC 7159 內的 Object 則是有提到 (重點我就用粗體標起來了)：

An object structure is represented as a pair of curly brackets surrounding zero or more name/value pairs (or members). A name is a string. A single colon comes after each name, separating the name from the value. A single comma separates a value from a following name. The names within an object SHOULD be unique.

   object = begin-object [ member *( value-separator member ) ]
            end-object

   member = string name-separator value

An object whose names are all unique is interoperable in the sense that all software implementations receiving that object will agree on the name-value mappings. When the names within an object are not unique, the behavior of software that receives such an object is unpredictable. Many implementations report the last name/value pair only. Other implementations report an error or fail to parse the object, and some implementations report all of the name/value pairs, including duplicates.

JSON parsing libraries have been observed to differ as to whether or not they make the ordering of object members visible to calling software. Implementations whose behavior does not depend on member ordering will be interoperable in the sense that they will not be affected by these differences.

粗體有描述唯一性，但尷尬的地方在於他用 SHOULD 而非 MUST，所以 library 理論上都要能接受。但後面提到如果不唯一時，行為無法預測 (會到 rm -rf / 嗎？XDDD 最像的應該還是 crash？)，所以還是不要亂來啦...

不過如果真的會 crash 的話，應該也會因為 DoS issue 而被發 CVE，所以實務上應該是不會 crash 啦...

Cloudbleed：Cloudflare 這次的安全問題

Cloudflare 把完整的時間軸與影響範圍都列出來了：「Incident report on memory leak caused by Cloudflare parser bug」。

出自於 2/18 時 Google 的 Tavis Ormandy 直接在 Twitter 上找 Cloudflare 的人：

Google 的 Project Zero 上的資料：「cloudflare: Cloudflare Reverse Proxies are Dumping Uninitialized Memory」。

起因在於 bug 造成有時候會送出不應該送的東西，可能包含了敏感資料：

It turned out that in some unusual circumstances, which I’ll detail below, our edge servers were running past the end of a buffer and returning memory that contained private information such as HTTP cookies, authentication tokens, HTTP POST bodies, and other sensitive data.

不過這邊不包括 SSL 的 key，主要是因為隔離開了：

For the avoidance of doubt, Cloudflare customer SSL private keys were not leaked. Cloudflare has always terminated SSL connections through an isolated instance of NGINX that was not affected by this bug.

不過由於這些敏感資料甚至還被 Google 收進 search engine，算是相當的嚴重，所以不只是 Cloudflare 得修好這個問題，還得跟眾多的 search engine 合作將這些資料移除：

Because of the seriousness of such a bug, a cross-functional team from software engineering, infosec and operations formed in San Francisco and London to fully understand the underlying cause, to understand the effect of the memory leakage, and to work with Google and other search engines to remove any cached HTTP responses.

bug 影響的時間從 2016/09/22 開始：

2016-09-22 Automatic HTTP Rewrites enabled
2017-01-30 Server-Side Excludes migrated to new parser
2017-02-13 Email Obfuscation partially migrated to new parser
2017-02-18 Google reports problem to Cloudflare and leak is stopped

而以 2/13 到 2/18 的流量反推估算，大約是 0.00003% 的 request 會可能產生這樣的問題：

The greatest period of impact was from February 13 and February 18 with around 1 in every 3,300,000 HTTP requests through Cloudflare potentially resulting in memory leakage (that’s about 0.00003% of requests).

不過不得不說 Tavis Ormandy 真的很硬，在沒有 source code 以及 Cloudflare 幫助的情況下直接打出可重製的步驟：

I worked with cloudflare over the weekend to help clean up where I could. I've verified that the original reproduction steps I sent cloudflare no longer work.

事發後完整的時間軸：

2017-02-18 0011 Tweet from Tavis Ormandy asking for Cloudflare contact information
2017-02-18 0032 Cloudflare receives details of bug from Google
2017-02-18 0040 Cross functional team assembles in San Francisco
2017-02-18 0119 Email Obfuscation disabled worldwide
2017-02-18 0122 London team joins
2017-02-18 0424 Automatic HTTPS Rewrites disabled worldwide
2017-02-18 0722 Patch implementing kill switch for cf-html parser deployed worldwide
2017-02-20 2159 SAFE_CHAR fix deployed globally
2017-02-21 1803 Automatic HTTPS Rewrites, Server-Side Excludes and Email Obfuscation re-enabled worldwide

另外在「List of Sites possibly affected by Cloudflare's #Cloudbleed HTTPS Traffic Leak」這邊有人整理出受影響的大站台有哪些 (小站台就沒列上去了)。

GNU GPLv2 的判例

在 OSNews 上看到 GNU GPLv2 在美國的判例：「The GNU GPL to be tested in court」。

引用的報導在「GPLv2 goes to court: More decisions from the Versata tarpit」這篇，裡面有幾個角色：

  • Ximpleware：撰寫了一套 XML parser，同時以 GPLv2 與商用版權釋出。
  • Versata：在自家產品 DCM software 使用了 Ximpleware 的 XML parser，依照後面的訴訟，看起來是沒有付錢買商用版本。而 DCM software 裡面沒有引用 GPLv2 條款，同時也當然沒有公開程式碼。
  • Ameriprise：付錢給 Versata 購買 DCM software 使用權的公司，另外取得 Versata 的授權，可以找外包商修改 Versata 的 DCM software。
  • Infosys：Ameriprise 的外包商。

起因在於 Versata 不爽 Infosys 拿他們的軟體開發同性質的軟體，結果告下去後這件事情牽扯到 GPLv2 的授權問題。

然後 Ximpleware 也跳出來告了所有人，還因為專利關係，告了 Versata 的其他客戶。

問題分成兩塊討論，一塊是 copyright，另外一塊是 patent。看了一下文章的說明，案子似乎還沒結束，但已經有些結論出來了。

在 copyright 的部份，法院要求明年二月底前必須上 patch 修正問題。也就是 GPLv2 的感染力是有效的，如果你不打算服從就要賠錢，然後把 GPLv2 程式碼拔乾淨。

而 patent 的部份有點複雜啊... Ximpleware 的控訴都不成立，不過理由沒有看懂 @_@

等有更多時間再來看其他的說明研究...

資料結構、RDBMS、ORM

欠了很久的雜記。既然是雜記，只是把一些事情記錄下來，許多句子的主題會跳來跳去，請多見諒。

先解釋標題的三個詞彙。這邊要講的是三種存取資料的方式：

  • 資料結構：直接操作最底層的資料結構。
  • RDBMS (Relational Database Management System，關聯式資料庫)：透過 RDBMS 存取資料的方式，在 open source 領域比較常遇到 MySQL 與 PostgreSQL。由於與下面的 ORM 比較，這一條指的是透過 SQL query 去存取資料。
  • ORM (Object-Relational Mapping)：透過程式語言的 object 以及 object 之間的關聯性存取資料。

彈性最高、效能也最好的是直接的資料存取，但寫起來也最複雜；而 ORM 大致上就是反過來。

現代的 RDBMS 大多都有實做 ACID，在自己操作資料結構時考慮這塊會比較辛苦。兩個層級之間有一些 library 試著解決這個問題 (像是 BerkeleyDB 或是 LevelDB)，不過這篇文章暫時跳過。

MySQL 與其他的 RDBMS 比較起來欠了許多東西，但 High Availability 的成熟度以及效能而成為 open source 的第一選項。而也因為許多人使用，大家都知道 MySQL 的先天限制，也有許多 workaround 出現，所以大多數的狀況下這不是問題。

MySQL 的 InnoDB 其實寫的相當不錯，但 MySQL 的 SQL parser 一直都是 MySQL 的痛處，所以許多人使用 MySQL 時會儘量使用 simple query，而 ORM 的特性剛好可以搭上風。

使用 ORM 時最常見要避免的是 N+1 的問題，其他常見到的問題大多都不是 ORM 專有的。

先整理到這邊。