<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by R4 Cheng on Medium]]></title>
        <description><![CDATA[Stories by R4 Cheng on Medium]]></description>
        <link>https://medium.com/@chengr4?source=rss-7b0460db676e------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*YDLYQ6WAHL9MTT5Z</url>
            <title>Stories by R4 Cheng on Medium</title>
            <link>https://medium.com/@chengr4?source=rss-7b0460db676e------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 03:39:51 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@chengr4/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[[C] 從 XV6 OS 學 C]]></title>
            <link>https://chengr4.medium.com/c-%E5%BE%9E-xv6-os-%E5%AD%B8-c-06c93bd84beb?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/06c93bd84beb</guid>
            <category><![CDATA[xv6]]></category>
            <category><![CDATA[operating-systems]]></category>
            <category><![CDATA[c-language]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Mon, 20 Oct 2025 01:59:12 GMT</pubDate>
            <atom:updated>2026-07-05T00:19:51.124Z</atom:updated>
            <content:encoded><![CDATA[<h4>Learning C from XV6 Operating System</h4><blockquote>Slowly port to <a href="https://hackmd.io/@tQN1jUM6TwaU156s8AO7kQ/ryw0tY2GMl">https://hackmd.io/@tQN1jUM6TwaU156s8AO7kQ/ryw0tY2GMl</a></blockquote><h4>取得固定大小陣列的元素個數</h4><pre>#define NELEM(x) (sizeof(x)/sizeof((x)[0]))</pre><ul><li>sizeof(x)：取得整個陣列的大小（以 byte 為單位）</li><li>sizeof((x)[0])：取得陣列中<strong>單一元素</strong>的大小</li><li>相除後就得到陣列的元素數量</li></ul><h4>宣告函式指標陣列</h4><pre>static uint64 (*syscalls[])(void) { //... }</pre><ul><li>(void): 每個函式 (system call) 都是無參數</li><li>Return uint64</li><li>未明確指定的索引會被初始化為 NULL</li></ul><p>E.g.</p><pre>// 假設 SYS_fork = 1, SYS_exit = 2, SYS_trace = 22<br>static uint64 (*syscalls[25])(void) = {<br>  [1]  sys_fork,<br>  [2]  sys_exit,<br>  // [3] 到 [21] 未指定<br>  [22] sys_trace,<br>};<br><br>// 編譯後實際狀態：<br>syscalls[0]  = NULL   // 未指定<br>syscalls[1]  = sys_fork<br>syscalls[2]  = sys_exit<br>syscalls[3]  = NULL   // 未指定<br>syscalls[4]  = NULL   // 未指定<br>// ...<br>syscalls[21] = NULL   // 未指定<br>syscalls[22] = sys_trace<br>syscalls[23] = NULL   // 未指定<br>syscalls[24] = NULL   // 未指定</pre><h4>變數名稱</h4><p>sz : size, 記憶體區塊的大小（byte）== PGSIZE 4096 // bytes per page</p><h4>Macro</h4><pre>#define PTE2PA(pte) (((pte) &gt;&gt; 10) &lt;&lt; 12)</pre><p>從 Page Table Entry 提取對應的 Physical Page Address</p><blockquote>44 bits + 12 bits offset = real physical address</blockquote><p>在 RISV-V 的 SV39 架構中， 一個 PTE 是 64 bit，其中低 10 bit 是 flag，因此右移後得到 Physical Page Number (PPN) ，再左移 12 bit 就是 Physical Page Base Address</p><pre>#define PGROUNDUP(sz) (((sz)+PGSIZE-1) &amp; ~(PGSIZE-1))</pre><p>將任意大小 sz 向上對齊到最近的 page 大小倍數，一般是 4096 bytes</p><p>E.g.</p><p>sz = 1000 → PGROUNDUP(1000) = 4096</p><p>sz = 4096 → PGROUNDUP(4096) = 4096</p><p>sz = 4100 → PGROUNDUP(4100) = 8192</p><pre>// fs.h<br>#define MAXFILE (NDIRECT + NINDIRECT)</pre><p>Max file capacity in blocks (default: 268)</p><h3>記憶體存取</h3><h4>存取 return address 的值</h4><p>假設 frame pointer = 0x80004F00</p><pre>In memory:<br>┌─────────────────────────┐<br>│ 0x80004F00: [局部變數]   │ ← fp<br>├─────────────────────────┤<br>│ 0x80004EF8: 0x80001234  │ ← fp - 8 (返回地址)<br>├─────────────────────────┤<br>│ 0x80004EF0: 0x80004E00  │ ← fp - 16 (上一層 fp)<br>└─────────────────────────┘</pre><pre>uint64* saved_ra_addr = (uint64*)(fp - 8); // get 0x80004EF8<br>uint64 saved_ra_val = *saved_ra_addr; // get 0x80001234</pre><h3>XV6 System Calls</h3><h4>sys_sbrk</h4><p>調整「程式的 heap（program break）」大小。</p><ul><li>讀取使用者傳入的第一個參數 n（要增減的位元組數）</li><li>回傳「調整前」的 break（舊的 sz）。因此使用者端可把回傳值當成指標起點使用。</li></ul><h3>XV6 functions</h3><h4>In trap.c</h4><p><em>usertrap</em></p><pre>void usertrap(void)</pre><ol><li>Determine the cause of the trap</li><li>process trap: uservec — &gt; kernelvec,</li><li>return (call usertrapret)</li></ol><p><em>usertrapret</em></p><pre>void usertrapret(void)</pre><ol><li>It sets up the RISC-V control register to prepare for a future trap from user space: setting stvec to uservec and preparing the trapframe fields that uservec relies on.</li><li>It sets sepc to the previously saved user program counter</li><li>Finally, it calls userret on the trampoline page</li></ol><blockquote>Assembly code in userret will switch page tables</blockquote><h4>In proc.c</h4><p><strong><em>allocproc</em></strong>: 建立一個新的行程</p><h4>In vm.c</h4><p>管理虛擬位址空間與 page table</p><p><strong><em>freewalk</em></strong></p><pre>void<br>freewalk(pagetable_t pagetable)</pre><p>Recursively free page-table pages. All leaf mappings must already have been removed.</p><p><strong><em>mappages</em></strong></p><pre>int mappages(pagetable_t pagetable, uint64 va, uint64 size, uint64 pa, int perm)</pre><p>為從虛擬位址 va 開始的虛擬地址建立 page table entry (PTE)，使其對應從實體位址 pa 開始的實體地址。</p><blockquote>va 和 size 必須是 page-aligned</blockquote><blockquote>成功時回傳 0，若 walk() 無法分配所需的 page-table page 則回傳 -1</blockquote><p><strong><em>uvmalloc</em></strong></p><pre>uint64 uvmalloc(pagetable_t pagetable, uint64 oldsz, uint64 newsz, int xperm)</pre><p>為一個行程增加記憶體空間，將其大小從 oldsz 擴展到 newsz ，oldsz 是行程當前的 virtual memory 的大小，也是行程的界線。</p><p>Returns new size or 0 on error.</p><p>Two steps:</p><ol><li>分配實體記憶體（使用 kalloc）</li><li>建立虛擬位址到實體位址的映射（使用 mappages），並更新 pagetable</li></ol><p><strong><em>walk</em></strong></p><pre>pte_t* walk(pagetable_t pagetable, uint64 va, int alloc)</pre><p>遍歷行程的 Page Table，以找到對應特定虛擬位址的 level 0 PTE 的位址。</p><blockquote>如果沿途有任何需要的 Page Table Page 不存在，並且 alloc 參數為真，它就會<strong>分配並創建</strong>它們。</blockquote><p>Return: 找到的 PTE 的位址；如果找不到且不允許分配，則回傳 0。</p><p><strong><em>uvmcopy</em></strong></p><pre>int uvmcopy(pagetable_t old, pagetable_t new, uint64 sz)</pre><ul><li>old<strong> :父行程</strong>的 page table</li><li>new:<strong>子行程</strong>的 page table (new)</li></ul><p><strong><em>uvmunmap</em></strong></p><pre>void uvmunmap(pagetable_t pagetable, uint64 va, uint64 npages, int do_free)</pre><p><strong>移除</strong>一個程式 pagetable中從 va 開始的連續 <strong>npages</strong> 個虛擬頁面的映射。它還允許<strong>選擇性地釋放</strong>這些虛擬頁面所對應的物理記憶體。</p><blockquote>保留物理記憶體的原因之一是另一個行程，例如父行程可能還需要使用</blockquote><h4>In bio.c (block I/O)</h4><p><em>brelse (block release)</em></p><pre>void brelse(struct buf *b)</pre><blockquote>It must be called after using the buffer.</blockquote><h4>In fs.c</h4><p><em>bmap (block map)</em></p><pre>static uint bmap(struct inode *ip, uint block_number)</pre><p><strong>功能</strong>：找到或者建立 logical block 在磁碟上的 physical block number</p><blockquote>Logical block: virtual contiguous block (檔案視角)</blockquote><p><em>itrunc (truncate inode)</em></p><pre>void itrunc(struct inode *ip)</pre><p>將一個 inode 對應的所有資料全部清除，釋放磁碟空間，並將檔案大小歸零。</p><h3>XV6 Data Structures</h3><h4>In file.h</h4><p><strong><em>struct inode</em></strong></p><pre>// Copy of disk inode in memory<br>struct inode {<br>// ... other fields<br>short nlink;<br>uint addrs[NDIRECT+1];<br>}</pre><p>一個檔案只有一個 inode ，由於檔案的「內容」是分散存放在不同的 Block，inode 就是負責儲存這些 block 的位置。</p><blockquote>設計哲學：檔案的「身份」與「內容」是分開的</blockquote><p>nlink: number of directory entries (dirent)</p><ul><li>若 nlink 不為 0，檔案不會被刪除</li><li>通常 directory 的 nlink 是 2: parent/curr_dir and .</li></ul><p>addrs[NDIRECT+1]: <strong>區塊編號</strong></p><p>他決定了一個檔案可以有的最大區塊數目，NDIRECT 的 default 是 12 (kernel/fs.h)，+1是指一個 singly-indirect block number，他可以再容納 256 block。因此，總共可以有 12 個直接區塊 + 256 間接區塊 = 268 blocks。</p><blockquote>Default block size is 1024 bytes (BSIZE)</blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oFuvpbqTGzTz_cOatNZKQw.png" /></figure><p><em>Directory Entry</em></p><p><strong>(X) 迷思：</strong> 目錄（Directory）是一個特殊的容器，把檔案裝在裡面。</p><p><strong>(O) 真相：</strong> 目錄只是一個<strong>特殊的檔案</strong>，它的「內容」不是文字，而是一張「對照表」。</p><p>這張對照表裡的每一行，就叫做 <strong>Directory Entry</strong>。</p><pre>// Directory is a file containing a sequence of dirent structures.<br>#define DIRSIZ 14<br><br>struct dirent {<br>  ushort inum; // Inode 編號<br>  char name[DIRSIZ]; // 檔名<br>};</pre><p><strong>Directory Entry 的核心功能：</strong> 它負責將 <strong>「人類讀得懂的字串 (name)」</strong> 映射到 <strong>「電腦讀得懂的編號 (inum)」</strong>。</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=06c93bd84beb" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[No Encounter No Growth — 1] Clean up the commits]]></title>
            <link>https://chengr4.medium.com/no-encounter-no-growth-1-clean-up-the-commits-c697a79c9578?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/c697a79c9578</guid>
            <category><![CDATA[commit]]></category>
            <category><![CDATA[pull-request]]></category>
            <category><![CDATA[git]]></category>
            <category><![CDATA[code-review]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Tue, 24 Dec 2024 23:07:50 GMT</pubDate>
            <atom:updated>2025-05-08T21:23:06.056Z</atom:updated>
            <content:encoded><![CDATA[<h3>[No Encounter No Growth — 1] Clean up the commits</h3><h4>Series of No Encounter, No Growth</h4><blockquote>In software development, without knowing how to search for information, progress can be slow. However, much knowledge and many skills aren’t fully covered in books or videos and can be hard to find. Sometimes, they are simple and can be grasped with a little guidance, but without prior experience, it’s easy to waste time. Though I’m just a regular software engineer, I hope to assist others facing the same challenges I have met.</blockquote><h4>Always Organize Commits Before Creating a Pull Request</h4><p>Before creating a pull request (PR), it is very important to clean up the commits. First of all, the order of commits is crucial as it helps the reviewer clearly understand the changes in each commit. The order of commits can be:</p><ol><li><strong>refactor</strong> commits</li><li><strong>test</strong> demonstrating the problem</li><li><strong>fix</strong> with test update showing new behavior</li></ol><p>or</p><ol><li><strong>test</strong> demonstrating the problem</li><li><strong>fix</strong> with test update showing new behavior</li><li><strong>refactor</strong> commits</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*shd7KEeW3myAnm2mDM8fAw.png" /></figure><blockquote>Decide the commit order based on the situation</blockquote><h4>Enhance Commit Messages for Better Clarity</h4><p>Sometimes a commit message alone isn’t enough to fully describe its purpose, and that’s when adding additional explanations becomes important.</p><p>For example, The scenario involves</p><ol><li>adding a new <strong>test case</strong></li><li>along with a <strong>fix</strong> for it.</li></ol><p>In the commit for the new <strong>test</strong> case, the complement information should indicate that existing tests pass, and only the new test is failing. Then, in the <strong>fix</strong> commit, the message should explain</p><ol><li>the fix</li><li>and confirm that all tests now pass.</li></ol><blockquote><strong>The key is to make it easier for the reviewer to understand the intended behavior change!</strong></blockquote><h4>Git rebase is a useful tool</h4><p>To modify a specific commit in Git git rebase is an essential tool. Here’s how to use it:</p><pre># Go back N commits<br>git rebase -i HEAD~N # -i stands for interactive mode</pre><p>In the rebase editor:</p><ul><li>Change pick to action (e.g. edit) for the commit you want to modify</li><li>Save and close the editor (:wq)</li><li>Follow the instructions shown in your terminal</li></ul><blockquote>Special thanks to <a href="https://github.com/epage">Ed Page</a> for helping me grow</blockquote><h4>References</h4><ul><li><a href="https://github.com/rust-lang/annotate-snippets-rs/pull/142">https://github.com/rust-lang/annotate-snippets-rs/pull/142</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c697a79c9578" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day45] Read Rust Atomics and Locks — Caching and Cache Coherence]]></title>
            <link>https://chengr4.medium.com/day45-read-rust-atomics-and-locks-caching-and-cache-coherence-d60389f61733?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/d60389f61733</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[cache]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Thu, 12 Dec 2024 00:19:00 GMT</pubDate>
            <atom:updated>2024-12-12T00:19:00.059Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day45] Read Rust Atomics and Locks — Caching and Cache Coherence</strong></h3><h4>By Mara Bos</h4><blockquote>At Topic: Chapter 7: Caching and Cache Coherence</blockquote><blockquote>The cache aka. caché in French, meaning “hidden”</blockquote><h4><em>Notes</em></h4><ul><li>When an instruction writes to memory, the cache might keep the modified data temporarily without immediately updating the main memory.</li></ul><p>=&gt; Any subsequent read requests for the same memory address will receive the updated data from the cache, <strong>ignoring the outdated data</strong> in main memory.</p><ul><li>Most processor architectures read and write cache in blocks of 64 bytes (aka. cache lines), even if only a single byte is needed.</li></ul><p>=&gt; (Advantage) Caching the entire block allows subsequent instructions to access the same block without needing to fetch it from memory again.</p><p><strong><em>Cache Coherence</em></strong></p><p>Background:</p><p>In multi-core systems, each core typically has its own L1 cache and shares L2, L3 caches etc.. If a core modifies data in its cache without notifying other caches, inconsistencies can arise.</p><p>=&gt; To solve this problem, a <strong>cache coherence protocol</strong> is used.</p><ul><li>The specific cache coherence protocol implemented can differ based on the architecture, the processor model, and even the cache level.</li><li>E.g. The write-through protocol, the MESI protocol</li></ul><p><em>The write-through protocol</em></p><ul><li>“Writes” are not cached but are immediately written to the next layer of cache.</li><li>All caches can observe the same communication and therefore can update to the same value.</li><li>Pros: Simple and easy to implement, Good for optimizing read-heavy workloads.</li><li>Cons: Writes are slower</li></ul><p><em>The MESI protocol</em></p><blockquote>Too lazy for this part = =!</blockquote><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a> (zh-hant)</li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d60389f61733" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day44] Read Rust Atomics and Locks — Load-linked and Store-Conditional Instructions on RISC]]></title>
            <link>https://blog.devgenius.io/day44-read-rust-atomics-and-locks-load-linked-and-store-conditional-instructions-on-risc-8e0914016ea5?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/8e0914016ea5</guid>
            <category><![CDATA[arm]]></category>
            <category><![CDATA[assembly]]></category>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[processors]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Fri, 27 Sep 2024 04:01:37 GMT</pubDate>
            <atom:updated>2024-09-28T17:06:45.300Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day44] Read Rust Atomics and Locks — Load-linked and Store-Conditional Instructions on RISC</strong></h3><h4>by Mara Bos</h4><blockquote>At Topic: Chapter 7: Load-linked and Store-Conditional Instructions</blockquote><blockquote>The closest thing to a `compare-and-exchange` loop on a RISC architecture is a load-linked/store-conditional loop (aka. LL/SC loop).</blockquote><h4>Notes</h4><p>Background: A compare-and-exchange loop is the most common way to implement atomic operations.</p><ul><li>The closest thing to a compare-and-exchange loop on a RISC architecture is a load-linked/store-conditional loop (aka. LL/SC loop).</li><li>Load-linked (LL): Similar to regular load</li><li>Store-conditional (SC): Similar to regular store, but conditional</li><li><strong>LL/SC</strong> should be used together and target the same memory location.</li><li>SC refuses to store if memory has been overwritten since LL.</li><li>If SC fails, the loop will simply retry. =&gt; Promise of atomicity</li><li>ARM64 always lacks single-instruction atomic fetch-and-modify or compare-and-exchange operations.</li><li>Due to its design, ARM64 separates <strong>load</strong> and <strong>store</strong> steps from calculations and comparisons.</li><li>ARM64 uses ldxr (load exclusive register) and stxr (store exclusive register) for load-linked and store-conditional operations.</li><li>Use fetch-and-modify methods instead of a compare-and-exchange loop when possible.</li></ul><blockquote>clrex (clear exclusive) is available as an alternative to stxr to stop tracking memory writes without storing any data.</blockquote><p>Here is an example for x.fetch_add(10, Relaxed) in ARM64:</p><pre>; Non-atomic code to add 10 in function a<br>a:<br>    ldr w8, [x0]<br>    add w8, w8, #10<br>    str w8, [x0]<br>    ret<br><br>; x.fetch_add(10, Relaxed) in function a<br>a:<br>.L1:<br>    ldxr w8, [x0] ; Load the value at address pointed to by x0 into register w8 (LL).<br>    add w9, w8, #10 ; Add 10 to the value in w8 and store the result in w9.<br>    stxr w10, w9, [x0] ; Attempt to store the value in w9 back to the address pointed to by x0 (SC).<br>                       ; The result of the store is written to w10. 0 = success, 1 = fail.<br>    cbnz w10, .L1 ; If the store failed (w10 != 0), branch back to .L1 to retry the loop.<br>    ret ; Return from the function.</pre><blockquote>Compilers generally minimize the number of instructions in LL/SC patterns to reduce the risk of LL/SC loops failing repeatedly or spinning indefinitely.</blockquote><p><strong><em>ARMv8.1 Atomic Instructions</em></strong></p><ul><li>ARMv8.1 introduced new CISC-style atomic instructions in ARM64 for common atomic operations.</li><li>E.g. ldadd (load and add) for fetch_add, without the need for LL/SC loops.</li><li>E.g. instructions for fetch_max</li><li>E.g. cas (compare and swap) corresponds to compare_exchange.</li><li>These new instructions can be more performant than LL/SC pattern and good for some specialized hardware.</li></ul><p><strong><em>Compare-and-exchange on ARM</em></strong></p><p>compare_exchange_weak :</p><pre>pub fn a(x: &amp;AtomicI32) {<br>    x.compare_exchange_weak(5, 6, Relaxed, Relaxed);<br>}</pre><p>=&gt;</p><pre>a:<br>    ldxr w8, [x0] ; Load the value at memory address in x0 into register w8 (LL)<br>    cmp w8, #5 ; Compare the value in w8 with 5<br>    b.ne .L1 ; If w8 is not equal to 5, branch to label .L1<br>    mov w8, #6 ; If comparison succeeded (w8 == 5), move the value 6 into register w8<br>    stxr w9, w8, [x0] ; (SC) Try to store the value in w8 to the address in x0 <br>                      ; and set w9 based on success (0 = success, 1 = failure)<br>    ret ; Return<br>.L1: ; Handling the failure case<br>    clrex ; Abort the LL/SC pattern<br>    ret ; Return</pre><blockquote>Normally, compare_exchange_weak is used in a loop to retry on failure. In this example, we only call it once and ignore the return value to focus on the relevant assembly.</blockquote><blockquote>stxr is allowed to have false negatives that it might fail even if the memory location has not been changed by another thread. (This is why compare_exchange_weak is called weak.)</blockquote><p>compare_exchange :</p><pre>pub fn a(x: &amp;AtomicI32) {<br>    x.compare_exchange(5, 6, Relaxed, Relaxed);<br>}</pre><p>=&gt;</p><pre>a:<br>    mov w8, #6 ; Move the value 6 into register w8 (this will be used for the store)<br>.L1:<br>    ldxr w9, [x0] ; Load the value from memory at address x0 into register w9 (LL)<br>    cmp w9, #5 ; Compare the value in w9 with 5<br>    b.ne .L2 ; If w9 is not equal to 5, branch to label .L2 to handle failure<br>    stxr w9, w8, [x0] ; (SC) Attempt to store w8 (value 6) at memory address in x0<br>                      ; w9 will be set to 0 on success or 1 on failure<br>    cbnz w9, .L1 ; If w9 is non-zero (store failed), branch back to .L1 to retry<br>    ret ; Return<br>.L2: ; Handling the failure case (comparison failed)<br>    clrex ;  Abort the LL/SC pattern<br>    ret ; Return</pre><p>To compare with compare_exchange_weak, compare_exchange has:</p><ol><li>An extra branch</li><li>An extra chnz (compare and branch on nonzero) instruction</li><li>The mov instruction is outside the loop to keep the loop as short as possible.</li></ol><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a> (zh-hant)</li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=8e0914016ea5" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day44-read-rust-atomics-and-locks-load-linked-and-store-conditional-instructions-on-risc-8e0914016ea5">[Day44] Read Rust Atomics and Locks — Load-linked and Store-Conditional Instructions on RISC</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day43] Read Rust Atomics and Locks — Read-Modify-Write in the x86 Processor]]></title>
            <link>https://blog.devgenius.io/day43-read-rust-atomics-and-locks-read-modify-write-in-the-x86-processor-6fe671d701ee?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/6fe671d701ee</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[x86]]></category>
            <category><![CDATA[assembly]]></category>
            <category><![CDATA[processors]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Sun, 22 Sep 2024 22:43:01 GMT</pubDate>
            <atom:updated>2024-09-24T17:31:11.871Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day43] Read Rust Atomics and Locks — Read-Modify-Write in the x86 Processor</strong></h3><h4>by Mara Bos</h4><blockquote>At Topic: Chapter 7: Read-Modify-Write Operations</blockquote><blockquote>x86 systems provide an instruction prefix called `lock` as a modifier to make instructions like `add` <strong>atomic</strong>.</blockquote><h4>Recall</h4><p><strong><em>Compare-and-Exchange Operations</em></strong></p><ul><li>Compare-and-Exchange checks if the atomic value is equal to a given value, and only if that is the case does it replace it with a new value (as a single operation)</li><li>compare_exchange_weak: Similar to compare_exchange, but the difference is that the weak version may still sometimes leave the value untouched and return an Err, even though the atomic value matched the expected value.</li><li>We could use Compare-and-Exchange to implement all the other atomic operations by putting it in a loop to retry if it did change.</li></ul><pre>// source: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#examples-11<br>use std::sync::atomic::{AtomicUsize, Ordering};<br><br>let some_var = AtomicUsize::new(5);<br><br>// some_var compares to the first argument (5) and if it is equal, it will be replaced by the second argument (10)<br>assert_eq!(some_var.compare_exchange(5, 10,<br>                                     Ordering::Acquire,<br>                                     Ordering::Relaxed), Ok(5));<br>assert_eq!(some_var.load(Ordering::Relaxed), 10);</pre><h4>Notes</h4><p>An example of read-modify-write operation in x86-64 and ARM64:</p><pre>// Rust code<br>pub fn a(x: &amp;mut i32) {<br>    *x += 10;<br>}</pre><p>=&gt;</p><pre>; Compiled x86-64<br>a:<br>    add dword ptr [rdi], 10<br>    ret<br><br>; Compiled ARM64<br>a:<br>    ldr w8, [x0]<br>    add w8, w8, #10<br>    str w8, [x0]<br>    ret</pre><ul><li>While loading and storing happens in different steps in ARM64, it is clear that the instructions are not atomic.</li><li>x86–64’s add instruction will be separated by the process into several <strong>micro-instructions</strong> behind the scenes, so it is not atomic as well.</li></ul><blockquote>If instructions run on a single core, the atomic issue is not a problem, as switching a processor core between threads generally only happens <strong>between instructions</strong>. But if multiple cores are involved, it is crucial to consider the multiple steps of a read-modify-write operation.</blockquote><p>x86 systems provide an instruction prefix called lock as a modifier to make instructions like `add` <strong>atomic:</strong></p><pre>a:<br>    lock add dword ptr [rdi], 10<br>    ret</pre><ul><li>In modern processors, The lock prefix blocks the using memory while allowing other cores to operate on unrelated memory.</li><li>The lock prefix can only be applied to a few instructions, including add, sub, and, not, or, and xor.</li><li>The xchg instruction (exchange), used for atomic swaps, <strong>implicitly</strong> behaves as if it has a lock prefix, ensuring it is always atomic.</li></ul><p>A fetch_add example in x86–64:</p><pre>pub fn a(x: &amp;AtomicI32) -&gt; i32 {<br>    x.fetch_add(10, Relaxed)<br>}</pre><p>=&gt;</p><pre>a:<br>    mov eax, 10<br>    lock xadd dword ptr [rdi], eax<br>    ret</pre><p>Instead of the add instruction, the xadd (exchange and add) instruction is used here, as it places the original value of x into a register (eax) before performing the addition.</p><blockquote>add can provide a little of useful to next instructions though, such as whether the updated value was zero or negative.</blockquote><ul><li>xadd (O), xchf (O), xsub (X), xand (X), xor (X)</li><li>For subtraction, this isn’t problematic since xadd can be used with negative values.</li><li>For and, or and xor(Bitwise Operations) =&gt; bts (bit test and set), btr (bit test and reset), and btc (bit test and complement)</li><li>When operations affect more than one bit, they cannot be represented by a single x86–64 instruction.</li><li>The x86–64 architecture supports a lock-prefixable cmpxchg (compare and exchange) instruction, which can be used to implement atomic operations that are not directly supported by the x86–64 instruction such as fetch_or:</li></ul><pre>pub fn a(x: &amp;AtomicI32) -&gt; i32 {<br>    x.fetch_or(10, Relaxed)<br>}</pre><p>=&gt;</p><pre>a:<br>    mov eax, dword ptr [rdi]      ; Load the value from the atomic variable (pointed to by rdi) into eax<br>.L1:<br>    mov ecx, eax                  ; Copy the value in eax to ecx (prepare for OR operation)<br>    or ecx, 10                    ; Perform a bitwise OR on ecx with 10, storing the result in ecx<br>    lock cmpxchg dword ptr [rdi], ecx  ; Atomically compare and exchange:<br>                                       ; - Compare the value in eax with the value at the memory address rdi<br>                                       ; - If they are equal, store ecx (new value) at eax<br>                                       ; - If not, store the current value at rdi in eax<br>    jne .L1                       ; If the comparison failed (values were not equal), jump back to .L1 to retry<br>    ret                           ; Return from the function, with the original value in eax</pre><blockquote>On x86–64, there is no difference between compare_exchange and compare_exchange_weak. Both compile down to a lock cmpxchg instruction.</blockquote><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a> (zh-hant)</li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=6fe671d701ee" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day43-read-rust-atomics-and-locks-read-modify-write-in-the-x86-processor-6fe671d701ee">[Day43] Read Rust Atomics and Locks — Read-Modify-Write in the x86 Processor</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day42] Read Rust Atomics and Locks — Load and Store in the Processor]]></title>
            <link>https://blog.devgenius.io/day42-read-rust-atomics-and-locks-load-and-store-in-the-processor-63c83ddd9a39?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/63c83ddd9a39</guid>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[processors]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Tue, 10 Sep 2024 08:12:19 GMT</pubDate>
            <atom:updated>2024-09-10T14:50:57.245Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day42] Read Rust Atomics and Locks — Load and Store in the Processor</strong></h3><h4>by Mara Bos</h4><blockquote>At Topic: Chapter 7 Load and Store</blockquote><blockquote>The processor does not differentiate between atomic and non-atomic stores and loads</blockquote><h4>Notes</h4><p>Interestingly, both non-atomic store through &amp;mut i32 and atomic store to an AtomicI32 are compiled to the same assembly code:</p><pre>// Non-atomic store through &amp;mut i32<br>pub fn a(x: &amp;mut i32) {<br>    *x = 0;<br>}<br><br>// Atomic store to an AtomicI32<br>pub fn b(x: &amp;AtomicI32) {<br>    x.store(0, Relaxed);<br>}</pre><p>=&gt;</p><pre>// Compiled x86-64<br>// copy (move) dats from a zero constant to memory<br>a:<br>    mov dword ptr [rdi], 0 ret<br><br>// Compiled ARM64<br>// store a 32-bit register into memory<br>// wzr: register that always contains zero<br>a:<br>    str wzr, [x0] ret</pre><p>Because mov and str (store) have already been atomic on x86–64 and ARM64. =&gt; They either happened or did not happen at all. Therefore, the meaning of atomic “relaxed” store is <strong>only relevant</strong> for the compiler checks and optimizations and <strong>useless</strong> for the processor.</p><blockquote>The load operation remains the same.</blockquote><ul><li>Although it makes no difference for the processor between atomic and non-atomic operations stores and loads, we still need to identify them in our Rust code.</li></ul><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a></li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=63c83ddd9a39" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day42-read-rust-atomics-and-locks-load-and-store-in-the-processor-63c83ddd9a39">[Day42] Read Rust Atomics and Locks — Load and Store in the Processor</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day41] Read Rust Atomics and Locks — Processor Introduction]]></title>
            <link>https://blog.devgenius.io/day41-read-rust-atomics-and-locks-processor-introduction-256ec569a819?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/256ec569a819</guid>
            <category><![CDATA[assembly]]></category>
            <category><![CDATA[processors]]></category>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Fri, 30 Aug 2024 06:46:08 GMT</pubDate>
            <atom:updated>2024-08-31T17:25:08.536Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day41] Read Rust Atomics and Locks — Processor Introduction</strong></h3><h4>by Mara Bos</h4><blockquote>At Topic: Chapter 7</blockquote><h4>Notes</h4><p>Two main specific processor architectures:</p><p><strong><em>x86</em></strong></p><ul><li>CISC, complex instruction set computer</li><li>Able to directly operate on memory</li><li>Intel + AMD are two main manufacturers</li><li>Mainly used in desktops, laptops, servers and game consoles</li><li>x86–16 and x86–32 are mainly dominated by Intel</li><li>x86–64: AMD64, IA-64 (Intel) and more popular AMD’s extensions IA-32e (Intel), EMT64T (Intel), Intel 64</li></ul><p><strong><em>ARM64</em></strong></p><blockquote>aka. AArch64</blockquote><ul><li>RISC, reduced instruction set computer</li><li>Loading and storing ot memory takes a seperate instruction</li><li>Mainly used in modern mobile devices, embedded systems, and increasingly in laptops and desktops</li><li>E.g. cars, electronic COVID tests</li></ul><h4><strong>Assembly</strong></h4><pre>ldr x, 1234 // load from memory address 1234 into x<br>li y, 0     // set y to zero<br>inc x       // increment x<br>add y, x    // add x to y<br>mul x, 3    // multiply x by 3<br>cmp y, 10   // compare y to 10<br>jne -5      // jump five instructions back if not equal<br>str 1234, x // store x to memory address 1234<br>// =&gt;<br>         ldr x, SOME_VAR<br>         li y, 0<br>my_loop: inc x<br>         add y, x<br>         mul x, 3<br>         cmp y, 10<br>         jne my_loop<br>         str SOME_VAR, x</pre><ul><li>Registers (part of the processor, hold a single integer or memory address): x, y</li></ul><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a></li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=256ec569a819" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day41-read-rust-atomics-and-locks-processor-introduction-256ec569a819">[Day41] Read Rust Atomics and Locks — Processor Introduction</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day40] Read Rust Atomics and Locks — Optimize Arc]]></title>
            <link>https://blog.devgenius.io/day40-read-rust-atomics-and-locks-optimize-arc-653de23c9626?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/653de23c9626</guid>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Thu, 29 Aug 2024 06:08:25 GMT</pubDate>
            <atom:updated>2024-08-29T14:33:58.977Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day40] Read Rust Atomics and Locks — Optimize Arc</strong></h3><h4>By Mara Bos</h4><blockquote>At Topic: Chapter 6. Optimizing</blockquote><blockquote>Implementing an ad hoc (spin) lock can sometimes be a valid strategy for operating on multiple atomic variables at once.</blockquote><h4>Recall</h4><p><strong><em>Arc</em></strong></p><ul><li>Goal: To share ownership</li><li>Thread safe (While Rc is not)</li><li>Immutable (So is Rc)</li></ul><pre>let a = Arc::new([1, 2, 3]);<br>let b = a.clone();<br>assert_eq!(a.as_ptr(), b.as_ptr()); // Same allocation!</pre><p><strong><em>UnsafeCell</em></strong></p><ul><li>An UnsafeCell is the primitive building unit for <strong>interior mutability</strong></li><li>No restrictions to avoid undefined behavior</li><li>Can only be used in unsafe block</li><li>Commonly, an UnsafeCell is wrapped in another type that provides safety through a limited interface, such as Cell or Mutex.</li><li>In other words, all types with interior mutability are built on top of UnsafeCell, Including: Cell, RefCell, RwLock, Mutex…</li><li>Gets a mutable raw pointer (*mut T) to the wrapped value by get method.</li></ul><pre>pub const fn get(&amp;self) -&gt; *mut T</pre><p><strong><em>Compare-and-Exchange Operations</em></strong></p><ul><li>Compare-and-Exchange checks if the atomic value is equal to a given value, and only if that is the case does it replace it with a new value (as a single operation)</li><li>compare_exchange_weak: Similar to compare_exchange, but the difference is that the weak version may still sometimes leave the value untouched and return an Err, even though the atomic value matched the expected value.</li><li>We could use Compare-and-Exchange to implement all the other atomic operations by putting it in a loop to retry if it did change// source: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#examples-11<br>use std::sync::atomic::{AtomicUsize, Ordering};</li></ul><pre>// source: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#examples-11<br>use std::sync::atomic::{AtomicUsize, Ordering};<br><br>let some_var = AtomicUsize::new(5);<br><br>// some_var compares to the first argument (5) and if it is equal, it will be replaced by the second argument (10)<br>assert_eq!(some_var.compare_exchange(5, 10,<br>                                     Ordering::Acquire,<br>                                     Ordering::Relaxed), Ok(5));<br>assert_eq!(some_var.load(Ordering::Relaxed), 10);</pre><h4>Notes</h4><blockquote>To see full implementation, please go <a href="https://github.com/m-ou-se/rust-atomics-and-locks/blob/main/src/ch6_arc/s3_optimized.rs">here</a>. I just write down things that I feel important.</blockquote><ul><li>In this case, the Arc&lt;T&gt; does not wrap around Weak&lt;T&gt;</li></ul><ol><li>Since the existence of Arc&lt;T&gt; has already told us whether the data is sill alive or not, we do not need another None state to tell us that. Therefore, instead of Option&lt;T&gt;, we use ManuallyDrop&lt;T&gt; to store the data.</li><li>std::mem::ManuallyDrop&lt;T&gt;: it takes the exact same amount of space as a `T`, but allows us to manually drop it at any point by using an `unsafe` call to `ManuallyDrop::drop()`.</li><li>The way to design alloc_ref_count is really cool</li></ol><pre>struct ArcData&lt;T&gt; {<br>    /// Number of `Arc`s.<br>    data_ref_count: AtomicUsize,<br>    /// Number of `Weak`s, plus one if there are any `Arc`s.<br>    alloc_ref_count: AtomicUsize,<br>    /// The data. Dropped if there are only weak pointers left.<br>    data: UnsafeCell&lt;ManuallyDrop&lt;T&gt;&gt;,<br>}</pre><ul><li>get_mut method is a great case to study (I might only understand about 60% on this read).</li><li>(Recall) The locking operation must use Acquire to ensure that all previous writes are visible to the current thread. The unlocking operation (store) must use Release to ensure that all subsequent writes are visible to other threads.</li></ul><h4>Questions</h4><blockquote>Some questions I hope someone can answer me.</blockquote><ol><li>I think if another thread runs weak.clone() right after the main thread runs get_mut(), it is possible that the process could be aborted.</li><li>In get_mut() implementation, I think it is allowed to clone an Arc between fence(Acquire) and if condition which might violate the exclusive access to the data.</li></ol><pre>pub fn get_mut(arc: &amp;mut Self) -&gt; Option&lt;&amp;mut T&gt; {<br>    // Acquire matches Weak::drop&#39;s Release decrement, to make sure any<br>    // upgraded pointers are visible in the next data_ref_count.load.<br>    if arc.data().alloc_ref_count.compare_exchange(<br>        1, usize::MAX, Acquire, Relaxed<br>    ).is_err() {<br>        return None;<br>    }<br>    let is_unique = arc.data().data_ref_count.load(Relaxed) == 1;<br>    // Release matches Acquire increment in `downgrade`, to make sure any<br>    // changes to the data_ref_count that come after `downgrade` don&#39;t<br>    // change the is_unique result above.<br>    arc.data().alloc_ref_count.store(1, Release);<br>    if !is_unique {<br>        return None;<br>    }<br><br>    // I think it is allowed to clone an `Arc` here<br><br>    fence(Acquire);<br>    unsafe { Some(&amp;mut *arc.data().data.get()) }<br>}</pre><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a></li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=653de23c9626" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day40-read-rust-atomics-and-locks-optimize-arc-653de23c9626">[Day40] Read Rust Atomics and Locks — Optimize Arc</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day39] Read Rust Atomics and Locks — Upgrade Arc with `Weak` ability]]></title>
            <link>https://blog.devgenius.io/day39-read-rust-atomics-and-locks-upgrade-arc-with-weak-ability-b33cca3f3be2?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/b33cca3f3be2</guid>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Sat, 24 Aug 2024 11:25:05 GMT</pubDate>
            <atom:updated>2024-08-26T17:49:08.651Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day39] Read Rust Atomics and Locks — Upgrade Arc with `Weak` ability</strong></h3><h4>By Mara Bos</h4><blockquote>At Topic: Chapter 6. <a href="https://marabos.nl/atomics/building-arc.html#weak-pointers">Weak Pointers</a></blockquote><blockquote>A Weak&lt;T&gt;, also called a <em>weak pointer</em>, behaves a bit like an Arc&lt;T&gt;, but does not prevent an object from getting dropped.</blockquote><h4>Recall</h4><p><strong><em>Arc</em></strong></p><ul><li>Goal: To share ownership</li><li>Thread safe (While Rc is not)</li><li>Immutable (So is Rc)</li></ul><pre>let a = Arc::new([1, 2, 3]);<br>let b = a.clone();<br><br>assert_eq!(a.as_ptr(), b.as_ptr()); // Same allocation!</pre><p><strong><em>UnsafeCell</em></strong></p><ul><li>An UnsafeCell is the primitive building unit for <strong>interior mutability</strong></li><li>No restrictions to avoid undefined behavior</li><li>Can only be used in unsafe block</li><li>Commonly, an UnsafeCell is wrapped in another type that provides safety through a limited interface, such as Cell or Mutex.</li><li>In other words, all types with interior mutability are built on top of UnsafeCell, Including: Cell, RefCell, RwLock, Mutex…</li><li>Gets a mutable raw pointer (*mut T) to the wrapped value by get method.</li></ul><pre>pub const fn get(&amp;self) -&gt; *mut T</pre><p><strong><em>Compare-and-Exchange Operations</em></strong></p><ul><li>Compare-and-Exchange checks if the atomic value is equal to a given value, and only if that is the case does it replace it with a new value (as a single operation)</li><li>compare_exchange_weak: Similar to compare_exchange, but the difference is that the weak version may still sometimes leave the value untouched and return an Err, even though the atomic value matched the expected value.</li><li>We could use Compare-and-Exchange to implement all the other atomic operations by putting it in a loop to retry if it did change</li></ul><pre>// source: https://doc.rust-lang.org/std/sync/atomic/struct.AtomicUsize.html#examples-11<br>use std::sync::atomic::{AtomicUsize, Ordering};<br><br>let some_var = AtomicUsize::new(5);<br><br>// some_var compares to the first argument (5) and if it is equal, it will be replaced by the second argument (10)<br>assert_eq!(some_var.compare_exchange(5, 10,<br>                                     Ordering::Acquire,<br>                                     Ordering::Relaxed), Ok(5));<br>assert_eq!(some_var.load(Ordering::Relaxed), 10);</pre><h4>Notes</h4><blockquote>To see full implementation, please go <a href="https://github.com/m-ou-se/rust-atomics-and-locks/blob/main/src/ch6_arc/s2_weak.rs">here</a>. I just write down things that I feel important.</blockquote><ul><li>A weak pointer provides a solution for dropping “cyclic structure”</li><li>Weak&lt;T&gt; behaves similar to Arc&lt;T&gt;, but does not prevent an object from getting dropped =&gt; Weak&lt;T&gt; can exist without a T</li><li>Weak&lt;T&gt; can be upgraded to Arc&lt;T&gt; through its upgrade method, but only if the T still exists.</li><li>To provide Arc as well as Weak, it is needed to modify ArcData struct:</li></ul><pre>// Before<br>struct ArcData&lt;T&gt; {<br>    ref_count: AtomicUsize,<br>    data: T,<br>}<br><br>// After<br>struct ArcData&lt;T&gt; {<br>    /// Number of `Arc`s.<br>    data_ref_count: AtomicUsize,<br>    /// Number of `Arc`s and `Weak`s combined.<br>    alloc_ref_count: AtomicUsize,<br>    /// The data. `None` if there&#39;s only weak pointers left.<br>    data: UnsafeCell&lt;Option&lt;T&gt;&gt;,<br>}</pre><ul><li>When implementing Deref for Arc, note that the type of ArcData.data is now UnsafeCell&lt;Option&lt;T&gt;&gt; rather than T. Therefore, it takes more steps to get &amp;T:</li></ul><pre>// Instead of <br>fn deref(&amp;self) -&gt; &amp;T {<br>        &amp;self.data().data<br>}<br><br>// It should be<br>fn deref(&amp;self) -&gt; &amp;T {<br>    // Using `UnsafeCell::get()`<br>    let ptr = self.weak.data().data.get();<br>    // Safty: Since there&#39;s an Arc to the data,<br>    // the data exists and may be shared.<br>    // (*ptr): *mut Option&lt;T&gt; =&gt; Option&lt;T&gt;<br>    // (*ptr).as_ref(): &amp;Option&lt;T&gt; to Option&lt;&amp;T&gt;<br>    unsafe { (*ptr).as_ref().unwrap() }<br>}</pre><ul><li>There are 2 focal points about Arc::get_mut:</li></ul><pre>struct ArcData&lt;T&gt; {<br>    data_ref_count: AtomicUsize,<br>    alloc_ref_count: AtomicUsize, // key for checking if it&#39;s the only Arc<br>    data: UnsafeCell&lt;Option&lt;T&gt;&gt;,<br>}<br><br>impl&lt;T&gt; Arc&lt;T&gt; {<br>    pub fn get_mut(arc: &amp;mut Self) -&gt; Option&lt;&amp;mut T&gt; {<br>        if arc.weak.data().alloc_ref_count.load(Relaxed) == 1 {<br>            fence(Acquire);<br>            // Safety: Nothing else can access the data, since<br>            // there&#39;s only one Arc, to which we have exclusive access,<br>            // and no Weak pointers.<br>            let arcdata: &amp;mut ArcData&lt;T&gt; = unsafe { arc.weak.ptr.as_mut() };<br>            let option: &amp;mut Option&lt;T&gt; = arcdata.data.get_mut();<br>            // We know the data is still available since we<br>            // have an Arc to it, so this won&#39;t panic.<br>            let data: &amp;mut T = option.as_mut().unwrap();<br>            Some(data)<br>        } else {<br>            None<br>        }<br>    }<br>}</pre><ol><li>By alloc_ref_count, we can check both Arc and Weak count at the same time. If alloc_ref_count is 1, it means there’s only one Arc and no Weak pointers. So, it’s safe to get mutable access to the data.</li><li>(My guess) arc.weak.ptr.as_mut() is used rather than arc.weak.data() because we need &amp;mut ArcData&lt;T&gt; rather than &amp;ArcData&lt;T&gt;.</li></ol><h4>Questions</h4><p><strong><em>Why does not </em></strong><strong><em>Weak implemented </em></strong><strong><em>Deref?</em></strong></p><blockquote>According to Claude</blockquote><ol><li>Safety considerations: Weak pointers don’t guarantee that the data they point to still exists. If Weak implemented Deref, users might incorrectly assume that the data is always available, which could lead to unsafe behavior.</li><li>Semantic mismatch: Deref is typically used to represent some kind of “ownership” or “guaranteed existence” relationship. Weak pointers fundamentally don’t provide this guarantee.</li><li>Different usage patterns: Arc needs frequent access to its internal data, so Deref is useful. Weak is primarily used to check if data exists and potentially upgrade to an Arc, not for direct access.</li></ol><h4><strong>My Difficulty</strong></h4><ul><li>I know UnsafeCell supplies more control and lower overhead and is great for synchronization. But the timing to use it rather than Cell or RefCell is quite difficult!</li><li>When to know my customized struct needs to implement Drop?</li></ul><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a></li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b33cca3f3be2" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day39-read-rust-atomics-and-locks-upgrade-arc-with-weak-ability-b33cca3f3be2">[Day39] Read Rust Atomics and Locks — Upgrade Arc with `Weak` ability</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[[Day38] Read Rust Atomics and Locks — Build Basic Arc]]></title>
            <link>https://blog.devgenius.io/day38-read-rust-atomics-and-locks-build-basic-arc-2fce4ec05f19?source=rss-7b0460db676e------2</link>
            <guid isPermaLink="false">https://medium.com/p/2fce4ec05f19</guid>
            <category><![CDATA[rust]]></category>
            <dc:creator><![CDATA[R4 Cheng]]></dc:creator>
            <pubDate>Thu, 15 Aug 2024 07:08:40 GMT</pubDate>
            <atom:updated>2024-08-15T17:23:25.857Z</atom:updated>
            <content:encoded><![CDATA[<h3><strong>[Day38] Read Rust Atomics and Locks — Build Basic Arc</strong></h3><h4>by Mara Bos</h4><blockquote>At Topic: Chapter 6. Basic Reference Counting</blockquote><blockquote>The Arc::new function creates a new allocation, just like Box::new. However, unlike a Box, a cloned Arc will share the original allocation, without creating a new one.</blockquote><h4>Recall</h4><p><strong><em>Arc</em></strong></p><ul><li>Goal: To share ownership</li><li>Thread safe (While Rc is not)</li><li>Immutable (So is Rc)</li></ul><pre>let a = Arc::new([1, 2, 3]);<br>let b = a.clone();<br><br>assert_eq!(a.as_ptr(), b.as_ptr()); // Same allocation!</pre><h4>Notes</h4><blockquote>To see full implementation, please go <a href="https://github.com/m-ou-se/rust-atomics-and-locks/blob/main/src/ch6_arc/s1_basic.rs">here</a>. I just write down things that I feel important.</blockquote><p>ArcData&lt;T&gt; is the core unit of Arc and should not be public</p><pre>struct ArcData&lt;T&gt; {<br>  ref_count: AtomicUsize,<br>  data: T<br>}</pre><p>Arc is basically a pointer to a shared ArcData&lt;T&gt; object. For this:</p><ul><li>Box&lt;ArcData&lt;T&gt;&gt; is <strong>unacceptable</strong> because a Box represents exclusive ownership, not shared ownership.</li><li>Using reference is also <strong>unacceptable</strong> because of the lifetime issue (Arc does not follow the lifetime rule).</li><li>Instead, std::ptr::NonNull&lt;T&gt; is used which represents a pointer to T that is never null.</li></ul><pre>pub struct Arc&lt;T&gt; {<br>  ptr: NonNull&lt;ArcData&lt;T&gt;&gt;<br>}</pre><p>For</p><pre>pub fn new(data: T) -&gt; Arc&lt;T&gt; {<br>    Arc {<br>        ptr: NonNull::from(Box::leak(Box::new(ArcData {<br>            ref_count: AtomicUsize::new(1),<br>            data,<br>        }))),<br>    }<br>}</pre><ul><li>Using Box::new() to allocate memory not &amp;ArcData because &amp;ArcData causes lifetime issues.</li><li>Box::leak() is used to give up the exclusive ownership of the allocation.</li></ul><p>—</p><ul><li>Box::from_raw(): reclaim exclusive ownership of the allocation (for dropping)</li><li>An Arc should not implement DerefMut since it represents shared ownership.</li><li>When ref_count == 1, get mutable reference is possible.</li><li>After changing the value by get_mut, we need to use mutex etc. to access the value of Arc (Actually, I do not understand why it is necessary).</li></ul><h4>References</h4><ul><li><a href="https://marabos.nl/atomics/">Rust Atomics and Locks by Mara Bos</a></li><li><a href="https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D">並行程式設計</a></li><li><a href="https://github.com/m-ou-se/rust-atomics-and-locks">Code examples of Rust Atomics and Lock</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2fce4ec05f19" width="1" height="1" alt=""><hr><p><a href="https://blog.devgenius.io/day38-read-rust-atomics-and-locks-build-basic-arc-2fce4ec05f19">[Day38] Read Rust Atomics and Locks — Build Basic Arc</a> was originally published in <a href="https://blog.devgenius.io/">Dev Genius</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>