calloc() 與 malloc() 的差異

前陣子在 Hacker News Daily 上看到的,原文是 2016 的文章:「Why does calloc exist?」,裡面講的東西包括了 implementation dependent 的項目,所以要注意一下他的結論未必適用於所有的平台與情境。

malloc()calloc() 的用法是這樣,其中 calloc() 會申請 countsize 的空間:

void* buffer1 = malloc(size);
void* buffer2 = calloc(count, size);

第一個差異是,count * size 可能會 overflow (而 integer overflow 在 C 裡面是 undefined behavior),這點除非你在乘法時有檢查,不然大多數的行為都還是會生一個值出來。

calloc() 則是會幫你檢查,如果會發生 overflow 的時候就不會真的去要一塊記憶體用。

第二個差異是 calloc() 保證會將內容都設定為 0,這點在 POSIX 的標準裡面是這樣寫的:

The calloc() function shall allocate unused space for an array of nelem elements each of whose size in bytes is elsize. The space shall be initialized to all bits 0.

但作者就發現 malloc() + memset() + free() 還是比 calloc() + free() 慢很多:

~$ gcc calloc-1GiB-demo.c -o calloc-1GiB-demo
~$ ./calloc-1GiB-demo
calloc+free 1 GiB: 3.44 ms
malloc+memset+free 1 GiB: 365.00 ms

研究發現是 calloc() 用了 copy-on-write 的技巧,先把所有的 page 都指到同一塊完全被塞 0 的記憶體,只有在真的寫到該段記憶體時,系統才會要一塊空間來用:

Instead, it fakes it, using virtual memory: it takes a single 4 KiB page of memory that is already full of zeros (which it keeps around for just this purpose), and maps 1 GiB / 4 KiB = 262144 copy-on-write copies of it into our process's address space. So the first time we actually write to each of those 262144 pages, then at that point the kernel has to go and find a real page of RAM, write zeros to it, and then quickly swap it in place of the "virtual" page that was there before. But this happens lazily, on a page-by-page basis.

但畢竟這是 implementation dependent,看看有個印象就好。

兩個 unsigned int 取平均值的方法

Hacker News Daily 上看到 Raymond Chen 在講怎麼對兩個 unsigned int 取平均值的方法:「On finding the average of two unsigned integers without overflow」,這篇裡面提到了不少有趣的歷史,另外 Hacker News 上的討論「Finding the average of two unsigned integers without overflow (microsoft.com)」也可以翻翻。

最直覺的解法會有 overflow 的問題:

unsigned average(unsigned a, unsigned b)
{
    return (a + b) / 2;
}

如果已知 a 與 b 的大小的話 (如同作者說的,蠻多時候都符合這個情況),可以用這個方法避免 integer overflow:

unsigned average(unsigned low, unsigned high)
{
    return low + (high - low) / 2;
}

另外還有個方法是有專利的 (「Calculating the average of two integer numbers rounded towards zero in a single instruction cycle」),雖然在 2016 年到期了,各除以二相加後,只有 ab 都是奇數的情況下需要補 1:

unsigned average(unsigned a, unsigned b)
{
    return (a / 2) + (b / 2) + (a & b & 1);
}

接下來的這個方法用 AND 與 XOR 搞事,其中的原理可以解釋成,相同的 bit 不動表示值不需要動,不同的 bit 表示降一位 (除以 2):

unsigned average(unsigned a, unsigned b)
{
    return (a & b) + (a ^ b) / 2;
}

最後是暴力解,用個比較大的 data type 搞定他:

unsigned average(unsigned a, unsigned b)
{
    // Suppose "unsigned" is a 32-bit type and
    // "unsigned long long" is a 64-bit type.
    return ((unsigned long long)a + b) / 2;
}

後面有很多 assembly 的妖魔鬼怪跑出來就不提了 XDDD

Stack Overflow 被 Prosus 併購

Hacker News 首頁上看到的消息,Stack OverflowProsus 併購,直接站上第一名:「Stack Overflow Sold to Tech Giant Prosus for $1.8 Billion」,Prosus 的官方新聞稿也已經出來了:「Prosus to acquire Stack Overflow for US$1.8 billion」,Hacker News 上的討論:「Stack Overflow sold to Prosus for $1.8B (wsj.com)」也很熱鬧。

算是大消息沒錯,不過不知道後續會有什麼樣的影響... Prosus 算是投資集團,不知道會對 Stack Overflow 有什麼想法,怎麼介入或是整合手上的資源。

更新 Sudo (CVE-2021-3156)

Sudo 這次的安全性漏洞頗痛的:「CVE-2021-3156: Heap-Based Buffer Overflow in Sudo (Baron Samedit)」。

依照 Sudo Security Alerts 這邊的說明,這次的漏洞只要是本機有執行權限的人都有機會打穿,不需要有 sudo 帳號權限:

A potential security issue exists in sudo that could be used by a local user to gain root privileges even when not listed in the sudoers file. Affected sudo versions are 1.8.2 through 1.8.31p2 and 1.9.0 through 1.9.5p1. Sudo 1.9.5p2 and above are not affected.

不限於本來就有 sudo 帳號 (但可能可執行指令受限) 就比較麻煩了,這代表從 web 之類的管道打進去以後 (可能是 www-data 身份),就可以用這個洞取得 root 權限,另外一條路是透過資料庫打進去後 (像是 mysql 身份) 取得。

該來把一堆機器更新了...

繞過 Screensaver Lock 的有趣話題...

Hacker News Daily 上看到「Screensaver lock by-pass via the virtual keyboard」這篇,裡面這邊題到了 screensaver lock 的有趣話題。

先講嚴肅一點的,這個 bug 被編號為 CVE-2020-25712,問題出在 xorg-x11-server 上:

A flaw was found in xorg-x11-server before 1.20.10. A heap-buffer overflow in XkbSetDeviceInfo may lead to a privilege escalation vulnerability. The highest threat from this vulnerability is to data confidentiality and integrity as well as system availability.

比較有趣的事情是,這個 bug 是小朋友在亂玩時拉出 virtual keyboard 觸發的:

A few weeks ago, my kids wanted to hack my linux desktop, so they typed and clicked everywhere, while I was standing behind them looking at them play... when the screensaver core dumped and they actually hacked their way in! wow, those little hackers...

然後他說他自己搞不出來:

I tried to recreate the crash on my own with no success, maybe because it required more than 4 little hands typing and using the mouse on the virtual keyboard.

另外一個人也說他家小朋友也弄出 segfault 了:

My kids came upon a similar cinnamon-screensaver segfault! I've emailed details of how to reproduce the problem to root@linuxmint.com.

小朋友超強 XDDD

把 BOOKWALKER 的書名完整顯示出來

從剛開始工作就有在看輕小說,但是現在住在外面租屋,實在不方便買一堆實體書,所以就弄了 iPad 在看電子書 (yeah,我對電子紙的材質還是不太喜歡,不過那是另外一回事了...),平台的話主力就是 BOOKWALKER

然後每次買書都會遇到很討厭的問題,最重要的集數給我顯示出來啊啊啊 (上排中間的書名,與下排左二與中間的書名):

看起來是被 height + overflow 幹掉了,所以寫了一個 www.bookwalker.com.tw.user.css 處理,讓他不受到 height 限制冒出來 (需要安裝 Stylus (Chrome) 或是 Stylus (Firefox) 之類的套件):

這樣總算是好了點...

找數列的平均值

2016 年的文章,不過算是經典的題目,所以最近又冒出來了。要怎麼找數列的平均值:「Calculating the mean of a list of numbers」。

You have a list of floating point numbers. No nasty tricks - these aren’t NaN or Infinity, just normal “simple” floating point numbers.

Now: Calculate the mean (average). Can you do it?

你有一串浮點數 (沒有 NaN 與 Infinity),要怎麼找出平均值。要考慮的包括:

  • 第一個要處理的就是設計演算法時各種會 overflow 的情況。
  • 降低誤差。
  • 合理的計算量。

好像很適合拿來 data team 面試時互相討論的題目?因為「平均值」是個商業上本來就有意義的指標,而且從 time-series events 灌進來的資料量有機會產生各種 overflow 情境,或是精確度問題,所以這個問題其實是個在真實世界上會遇到的情境。

想了一下,如果是 integer 的確是簡單很多 (可以算出正確的值),但如果是 float 類型真的難很多:

It also demonstrates a problem: Floating point mathematics is very hard, and this makes it somewhat unsuitable for testing with Hypothesis.

馬上想到的地雷是在 IEEE 754 的 float 世界裡,2^24 + 1 還是 2^24

#include <math.h>
#include <stdio.h>

int main(void)
{
    int i;
    float a;

    for (i = 0; i < 32; i++) {
        a = pow(2, i);
        printf("2^%d     = %f\n", i, a);

        a += 1;
        printf("2^%d + 1 = %f\n", i, a);
    }
}

然後在這邊可以看出差異:

2^23     = 8388608.000000
2^23 + 1 = 8388609.000000
2^24     = 16777216.000000
2^24 + 1 = 16777216.000000

Python 在高收入國家的成長

Stack Overflow 的內文其實有點奇怪的誤導... 主要是分析在 Stack Overflow 上 Python 成長的趨勢:「The Incredible Growth of Python」。

但一開始的分析是做高收入國家的部份:

但如果你捲到最下面,即使是非高收入的國家也是一樣急遽成長,只是沒那麼明顯:

Anyway,回到高收入國家的部份,如果用模型預測的話:

另外列出 YoY 成長:

這篇用高收入這個分法有種在炒話題的感覺...

最近 OpenVPN 的安全性漏洞...

看到「The OpenVPN post-audit bug bonanza」這個只有苦笑啊...

作者在 OpenVPN 經過一連串的安全加強後 (包括 harden 計畫與兩個外部單位的程式碼稽核找到不少問題),決定出手挖看看:

After a hardening of the OpenVPN code (as commissioned by the Dutch intelligence service AIVD) and two recent audits 1 2, I thought it was now time for some real action ;).

然後就挖出不少問題了...

可以看到作者透過 fuzzing 打出一卡車,包含了不少 crash XDDD:(然後有一個是 stack buffer corruption,不知道有沒有機會變成 RCE)

  • Remote server crashes/double-free/memory leaks in certificate processing (CVE-2017-7521)
  • Remote (including MITM) client crash, data leak (CVE-2017-7520)
  • Remote (including MITM) client stack buffer corruption
  • Remote server crash (forced assertion failure) (CVE-2017-7508)
  • Crash mbed TLS/PolarSSL-based server (CVE-2017-7522)
  • Stack buffer overflow if long –tls-cipher is given

StackOverflow 預設全上 HTTPS 了...

HTTPS Everywhere 沒什麼感覺,但對於一般人應該不簡單,所以 Nick Craver (根本就是他們家非正式的 PR Engineer XDD 他這幾年寫了不少內部的資訊...) 寫了一篇關於上 HTTPS 的故事:「HTTPS on Stack Overflow: The End of a Long Road」。

其中他們為了支援舊設備 (沒有支援 SNI 的),決定直接把所有 wildcard 類的 SSL certificate 都包進去 (另外找 DigiCert 處理):

然後中間提到這個真的頗無奈的,抱怨 SVG 的 XML... XDDD:

Finding and killing these was a little fun because you can’t just search for "http://". Thank you so much W3C for gems like this:

<svg xmlns="http://www.w3.org/2000/svg"...

一條辛苦路 XD