瀏覽器裡同一個節點上 JavaScript 的事件觸發順序

瀏覽器裡 JavaScript 的事件觸發順序是先 capture 再 bubble,這個在「Event order」這邊就有一些歷史解釋,IE8 以前只有 capture 模式,到了 IE9+ 才支援,在「Event API: bubbles」這邊也可以看到。

但如果是同一個節點上面的事件觸發順序 (假設同樣是 capture 或是同樣是 bubble),在「Are event handlers in JavaScript called in order?」這邊有些整理資料。

2000 年的「Document Object Model (DOM) Level 2 Events Specification」這邊提到沒有定義順序:

When the event reaches the target, any event listeners registered on the EventTarget are triggered. Although all EventListeners on the EventTarget are guaranteed to be triggered by any event which is received by that EventTarget, no specification is made as to the order in which they will receive the event with regards to the other EventListeners on the EventTarget.

在早期的 draft「Document Object Model (DOM) Level 3 Events Specification」裡面可以看到:

Next, the implementation must determine the current target's candidate event listeners. This must be the list of all event listeners that have been registered on the current target in their order of registration. [HTML5] defines the ordering of listeners registered through event handler attributes.

但在最新的「UI Events」(要注意這還是 draft,在 2016 年更新的) 則是拿掉了這段。

所以在設計架構時,正常還是得保守的假設沒有保證執行順序...

GNU Make 在 4.4 引入的 --shuffle

Hacker News 首頁上看到的,作者送了一個提案到 GNU Make,後來被採用,在 4.4 版引入了 --shuffle 指令:「New make --shuffle mode」。

這個功能主要是想要找出在 Makefile 裡面沒有被定義好,平常是因為 side effect 而沒有出錯的地方。

像是作者就發現 libgfortran 沒有把 libquadmath 放到 dependency 的問題:

For example gcc’s libgfortran is missing a libquadmath build dependency. It is natural not to encounter it in real world as libquadmath is usually built along with other small runtimes way before g++ or gfortran is ready.

他的基本想法是把 target 的順序打亂掉,也就是在有指定 --shuffle 時,不一定會照 a -> b -> c 的順序往下遞迴,而可能會是 c -> b -> a 或是其他的順序:

all: a b c

這樣對於抓那些在 -j 平行編譯時會出包的套件也很有幫助,不需要在 -j 開很大的情況下才能重製問題,而是平常就有機會在 CI 環境下被抓出來。

Python 3.7+ 保證 dict 內容的順序

在「Dicts are now ordered, get used to it」這邊看到的,因為 Python 官方 (也就是 CPython) 實做 dict 的方式改變,然後決定把這個特性當作是 social contract,而不是當作 side effect 的特性 (也就是不保證之後版本會有相同特性)。

Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6.

作者裡面的兩張圖清楚表示出來以前的版本怎麼實做,與 3.7+ 的版本怎麼實做:

這樣就很好理解了。

不過考慮到還是有些系統用 Python 3.5 (像是 Ubuntu 16.04 內建的 python3) 與 Python 3.6 (Ubuntu 18.04 內建的 python3,雖然沒問題,但當時還沒有寫出來),也許還是先不要依賴這個行為會比較好。

不過以插入的順序列出好像不是很常用到...

GrabFood 用定位資料修正餐廳的資訊

Grab 的「How we harnessed the wisdom of crowds to improve restaurant location accuracy」這篇是他們的 data team 整理出來,如何使用既有的資料快速的修正餐廳資訊。裡面提到的方法不需要用到 machine learning,光是一些簡單的統計算法就可以快速修正現有的架構。

這些資訊其實是透過司機用的 driver app 蒐集來的,在 driver app 上有大量的資訊傳回伺服器 (像是定時回報的 GPS 位置,以及取餐狀態),而這些司機因為地緣關係,腦袋裡的資訊比地圖會準不少:

One of the biggest advantages we have is the huge driver-partner fleet we have on the ground in cities across Southeast Asia. They know the roads and cities like the back of their hand, and they are resourceful. As a result, they are often able to find the restaurants and complete orders even if the location was registered incorrectly.

所以透過這些資訊他們就可以反過來改善地圖資料,像是透過司機按下「取餐」的按鈕的地點與待的時間,就可以估算餐聽可能的位置,然後拿這個資訊比對地圖上的資料,就很容易發現搬家但是地圖上沒更新的情況:

Fraction of the orders where the pick-up location was not “at” the restaurant: This fraction indicates the number of orders with a pick-up location not near the registered restaurant location (with near being defined both spatially and temporally as above). A higher value indicates a higher likelihood of the restaurant not being in the registered location subject to order volume

Median distance between registered and estimated locations: This factor is used to rank restaurants by a notion of “importance”. A restaurant which is just outside the fixed radius from above can be addressed after another restaurant which is a kilometer away.

另外也有不少其他的改善 (像是必須在離餐聽某個距離內才能點「取餐」,這個「距離」會因為餐聽可能在室內商場而需要的調整),整個成果就會反應在訂單的取消率大幅下降:

整體看起來是系統產生清單後讓人工後續處理 (像是打電話去店家問?),但這個方式所提供的清單準確度應該很高 (因為司機不會沒事跟自己時間過不去,跑到奇怪地方按下取餐),用這些資料跑簡單的演算法就能夠快速修正不少問題...

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本

Amazon Aurora (MySQL) 推出相容於 MySQL 5.7 的版本了:「Amazon Aurora is Compatible with MySQL 5.7」。

不過網站上的介紹還沒更新:

Amazon Aurora is a relational database service that combines the speed and availability of high-end commercial databases with the simplicity and cost-effectiveness of open source databases. The MySQL-compatible edition of Aurora delivers up to 5X the throughput of standard MySQL running on the same hardware, and is designed to be compatible with MySQL 5.6, enabling existing MySQL applications and tools to run without requiring modification.

5.7 其中一個賣點在於支援 Spatial index (透過 R-tree),不過 AWS 的版本看起來是自己用 B-tree 加上 Z-order curve 實做:「Amazon Aurora under the hood: indexing geospatial data using Z-order curves」。

我覺得看看就好啦,拿 244GB RAM 的 r3.8xlarge 跑 1GB 的 data set,當大家是傻逼嗎...

讀書時間:Spectre 的攻擊方式

上次寫了 Meltdown 攻擊的讀書心得 (參考「讀書時間:Meltdown 的攻擊方式」),結果後來中獎狂流鼻水,加上 Spectre 用的手法就更複雜,慢慢看的情況就拖到最近才看完... 這邊就以讀者看過 Meltdown 那篇心得的前提來描述 Spectre。

Spectre 的精華在於 CPU 支援 branch prediction 與 out-of-order execution,也就是 CPU 遇到 branch 時會學習怎麼跑,這個資訊提供給 out-of-order execution 就可以大幅提昇執行速度。可以參考以前在「CPU Branch Prediction 的成本...」提到的效率問題。

原理的部份可以看這段程式碼:

這類型程式碼常常出現在現代程式的各種安全檢查上:確認 x 沒問題後再實際將資料拉出來處理。而我們可以透過不斷的丟 x 值進去,讓 CPU 學到以為都是 TRUE,而在 CPU 學壞之後,突然丟進超出範圍的 x,產生 branch misprediction,但卻已經因為 out-of-order execution 而讓 CPU 執行過 y = ... 這段指令,進而導致 cache 的內容改變。

然後其中讓人最驚豔的攻擊,就是論文示範了透過瀏覽器的 JavaScript 就能打的讓人不要不要的...

圖片裡,上面這段是 JavaScript 程式碼,下面則是 Chrome V8JIT 後轉成的 assembly (這是 AT&T style):

可以從這段程式碼看到,他想要透過這段 JavaScript 取出本來無法存取到的祕密值 index,然後透過 probeTable 得知 cache 的變化。

在這樣的攻擊下,你就可以取得這個 process 裡可以看到的空間,甚至極端的 case 下有可能是 kernel space (配合 Meltdown 的條件)。

不過如果你不能跑 JavaScript 也沒關係,Spectre 的論文裡也提供各種變形方式提供攻擊。像是這樣的程式碼也可以被拿來攻擊:

if (false but mispredicts as true)
    read array1[R1]
read [R2]

其中 R1 是有帶有祕密值的 register,當 array[R1] 有 cache 時,讀 [R2] 就有機會比較快,而沒有 cache 時就會比較慢 (這是因為 memory bus 被佔用的關係),在這個情境下就能夠產生 timing attack:

Suppose register R1 contains a secret value. If the speculatively executed memory read of array1[R1] is a cache hit, then nothing will go on the memory bus and the read from [R2] will initiate quickly. If the read of array1[R1] is a cache miss, then the second read may take longer, resulting in different timing for the victim thread.

所以相同道理,利用乘法器被佔用的 timing attack 也可以產生攻擊:

if (false but mispredicts as true)
    multiply R1, R2
multiply R3, R4

在論文裡面提到相當多的方法 (甚至連 branch target buffers (BTB) 都可以拿來用),就麻煩去論文裡看了。現在用 cache 算是很有效的方式,所以攻擊手法主要都是透過 cache 在取得資訊。

Spectre 論文提到的 mitigation (workaround) 是透過 mfencelfence 強制程式碼的順序,但這表示 compiler 要針對所有的 branch 加上這段,對效能影響應該蠻明顯的:

In addition, of the three user-mode serializing instructions listed by Intel, only cpuid can be used in normal code, and it destroys many registers. The mfence and lfence (but not sfence) instructions also appear to work, with the added benefit that they do not destroy register contents. Their behavior with respect to speculative execution is not defined, however, so they may not work in all CPUs or system configurations.

Google 推出的 Retpoline 則是想要避免這個問題。Google 在「Retpoline: a software construct for preventing branch-target-injection」這邊詳細說明了 Retpoline 的原理與方法,採取的方向是控制 speculative execution:

However, we may manipulate its generation to control speculative execution while modifying the visible, on-stack value to direct how the branch is actually retired.

這個方式是抽換掉 jmpcall 兩個指令,以 *%r11 為例,他將 jmp *%r11call *%r11 改成 jmp retpoline_r11_trampolinecall retpoline_r11_trampoline (這邊的 jmp 指的是所有 jump 系列的指令,像是 jz 之類的):

retpoline_r11_trampoline:
  call set_up_target;
capture_spec:        
  pause;
  jmp capture_spec;
set_up_target:
  mov %r11, (%rsp); 
  ret;

藉由抽換 %rsp 內容跳回正確位置,然後也利用這樣的程式結構控制 CPU 的 speculative execution。

而在效能損失上,已經有測試報告出來了。其實並沒有像 Google 說的那麼無痛,還是會因為應用差異而有不同等級的效能損失... 可以看到有些應用其實還是很痛:「Benchmarking Linux With The Retpoline Patches For Spectre」。

下半年新出的 CPU 應該會考慮這些問題了吧,不過不知道怎麼提供解法 @_@

讀書時間:Meltdown 的攻擊方式

Meltdown 的論文可以在「Meltdown (PDF)」這邊看到。這個漏洞在 Intel 的 CPU 上影響最大,而在 AMD 是不受影響的。其他平台有零星的消息,不過不像 Intel 是這十五年來所有的 CPU 都中獎... (從 Pentium 4 以及之後的所有 CPU)

Meltdown 是基於這些前提,而達到記憶體任意位置的 memory dump:

  • 支援 µOP 方式的 out-of-order execution 以及當失敗時的 rollback 機制。
  • 因為 cache 機制造成的 side channel information leak。
  • 在 out-of-order execution 時對記憶體存取的 permission check 失效。

out-of-order execution 在大學時的計算機組織應該都會提到,不過我印象中當時只講「在確認不相干的指令才會有 out-of-order」。而現代 CPU 做的更深入,包括了兩個部份:

  • 第一個是 µOP 方式,將每個 assembly 拆成更細的 micro-operation,後面的 out-of-order execution 是對 µOP 做。
  • 第二個是可以先執行下去,如果發現搞錯了再 rollback。

像是下面的 access() 理論上不應該被執行到,但現代的 out-of-order execution 會讓 CPU 有機會先跑後面的指令,最後發現不該被執行到後,再將 register 與 memory 的資料 rollback 回來:

而 Meltdown 把後面不應該執行到 code 放上這段程式碼 (這是 Intel syntax assembly):

其中 mov al, byte [rcx] 應該要做記憶體檢查,確認使用者是否有權限存取那個位置。但這邊因為連記憶體檢查也拆成 µOP 平行跑,而產生 race condition:

Meltdown is some form of race condition between the fetch of a memory address and the corresponding permission check for this address.

而這導致後面這段不該被執行到的程式碼會先讀到資料放進 al register 裡。然後再去存取某個記憶體位置造成某塊記憶體位置被讀到 cache 裡。

造成 cache 內的資料改變後,就可以透過 FLUSH+RELOAD 技巧 (side channel) 而得知這段程式碼讀了哪一塊資料 (參考之前寫的「Meltdown 與 Spectre 都有用到的 FLUSH+RELOAD」),於是就能夠推出 al 的值...

而 Meltdown 在 mov al, byte [rcx] 這邊之所以可以成立,另外一個需要突破的地方是 [rcx]。這邊 [rcx] 存取時就算沒有權限檢查,在 virtual address 轉成 physical address 時應該會遇到問題?

原因是 LinuxOS X 上有 direct-physical map 的機制,會把整塊 physical memory 對應到 virtual memory 的固定位置上,這些位置不會再發給 user space 使用,所以是通的:

On Linux and OS X, this is done via a direct-physical map, i.e., the entire physical memory is directly mapped to a pre-defined virtual address (cf. Figure 2).

而在 Windows 上則是比較複雜,但大部分的 physical memory 都有對應到 kernel address space,而每個 process 裡面也都還是有完整的 kernel address space (只是受到權限控制),所以 Meltdown 的攻擊仍然有效:

Instead of a direct-physical map, Windows maintains a multiple so-called paged pools, non-paged pools, and the system cache. These pools are virtual memory regions in the kernel address space mapping physical pages to virtual addresses which are either required to remain in the memory (non-paged pool) or can be removed from the memory because a copy is already stored on the disk (paged pool). The system cache further contains mappings of all file-backed pages. Combined, these memory pools will typically map a large fraction of the physical memory into the kernel address space of every process.

這也是 workaround patch「Kernel page-table isolation」的原理 (看名字大概就知道方向了),藉由將 kernel 與 user 的區塊拆開來打掉 Meltdown 的攻擊途徑。

而 AMD 的硬體則是因為 mov al, byte [rcx] 這邊權限的檢查並沒有放進 out-of-order execution,所以就避開了 Meltdown 攻擊中很重要的一環。

電視節目上表演從 Amazon Echo 買東西...

然後觀眾家裡的 Amazon Echo 就跟著買了 XDDD:「TV anchor says live on-air 'Alexa, order me a dollhouse' – guess what happens next」。

A San Diego TV station sparked complaints this week – after an on-air report about a girl who ordered a dollhouse via her parents' Amazon Echo caused Echoes in viewers' homes to also attempt to order dollhouses.

MySQL 8.0 將會實作「真正的」Descending Indexes

在「MySQL 8.0 Labs – Descending Indexes in MySQL」這邊看到 MySQL 打算在 8.0 時實作出真正的 Descending Indexes。在 5.7 以及之前的版本,可以從「14.1.14 CREATE INDEX Syntax」看到這個參數是~假~的~XDDD

An index_col_name specification can end with ASC or DESC. These keywords are permitted for future extensions for specifying ascending or descending index value storage. Currently, they are parsed but ignored; index values are always stored in ascending order.

所以當 8.0 建立了 a_desc_b_asc (a DESC, b ASC) 這樣的 index,可以看到對於不同 ORDER BY 時效能的差異:(一千萬筆資料)

有些變快可以理解,但有些結果不太清楚造成的原因...

Anyway,對於變慢的兩個 query,他提了一個不算解法的解法,就是加上對應的 index XDDD:

If user wants to avoid filesorts for Query 5 and Query 6, he/she can alter the table to add a key (a ASC, b ASC) . Further to this, if the user wants to avoid backward index scans too, he/she can add both ( a ASC, b DESC) and (a DESC, b DESC).

這樣就會變快,但寫入的 overhead 會增加啊... XD

但不管怎樣,總算是把這個功能生出來了...

Python 3.6 對 Dict 的改善

Python 3 的 Dict 將會有重大的改變:「[Python-Dev] Python 3.6 dict becomes compact and gets a private version; and keywords become ordered」。

在 3.5 時:

Python 3.5.1 (default, Jun 20 2016, 14:48:22)
>>> def func(**kw): print(kw.keys())
...
>>> func(a=1, b=2, c=3, d=4, e=5)
dict_keys(['c', 'd', 'e', 'b', 'a'])   # random order

對上目前還在開發的 3.6:

Python 3.6.0a4+ (default:d43f819caea7, Sep  8 2016, 13:05:34)
>>> def func(**kw): print(kw.keys())
...
>>> func(a=1, b=2, c=3, d=4, e=5)
dict_keys(['a', 'b', 'c', 'd', 'e'])   # expected order

在「Compact and ordered dict」這邊可以看到記憶體的使用量降低:

It seems like the memory usage is between 20% and 25% smaller. Great job!

Memory usage, Python 3.5 => Python 3.6 on Linux x86_64:

./python -c 'import sys; print(sys.getsizeof({str(i):i for i in range(10)}))'

* 10 items: 480 B => 384 B (-20%)
* 100 items: 6240 B => 4720 B (-24%)
* 1000 items: 49248 B => 36984 B (-25%)

Note: the size is the the size of the container itself, not of keys nor values.

不過效能上似乎慢了一些:

3% slowdown in microbench is not surprising.
Compact dict introduces one additional indirection.

Instead, I've added freelist for most compact PyDictKeys.
So I think overall performance is almost same to before compact dict.

不過也有人提到應該拿 3.5 + patch 測,而不是直接拿 3.6 測:

There are a lot of other changes in interpreter core between 3.5 and 3.5 (such as new bytecode and optimized function calls). Could you compare the performance between the version just before adding new dict implementation and the version just after this?

看起來後續還在進行中...