Try   HackMD

2021q1 Homework4 (refinement)

tags: linux2021
  • 30 min - 兩個完整問題
    • 完整問題
      1. 問題情況鬆散、有一段歷史根源

03/18 - 一對一討論

quiz 1 - sort

  • B[16] tree - sort / 實務上改進需注意
    • 改寫時要看當下的特性，例如
      • 記憶體使用率
      • WCET
      • real-time
      • percpu - list_sort
      • 符不符合更改目標環境所提出的限制
      • 是不是 MT-safe
    • 例如 Timsort 可能因為較複雜的實作，不符合 Linux 核心精簡的原則，特別是驗證的難度，可見 Timsort : formal verification
    • simd sort - percpu

quiz 2 - string interning

  • GCC __sync : deprecated 過時還可以用
    • 取決於 OS 或 hardware, 有些架構實做不完全、是系統呼叫、或是根本沒有
    • memory barrier mode switch/transition

      can use transfer mode to suspend user mode extension

    • 設計實驗時要考慮好所有情境，例如在 string interning 裡要考慮到 ref 的次數

obsolete 過時不會用

TODO

ASK

  • Alignment why 4
  • assambly - SetPageReserved()
  • ​​​​#define xs_tmp(x)                                                              \
​​​​  ((void)((struct {                                                            \
​​​​     _Static_assert(sizeof(x) <= MAX_STR_LEN, "it is too big");                \
​​​​     int dummy;                                                                \
​​​​   }){1}),                                                                     \
​​​​   xs_new(&xs_literal_empty(), x))

03/23 - code review

quiz 2 - string interning

linD026

字串處理

  • cstring cstr_cat(cstr_buffer sb, const char *str)

    • 只對 hash 操作有 lock 處理
    • 細部處理，因涉及到有可能呼叫到其他函式，因此選擇包起來
      • 範圍太大、效率不高

  • 原先測試沒辦法進入到 hash 操作

    ​​​​static void test_cstr(void *buf) {
​​​​  cstr_buffer *a = (cstr_buffer *)buf;
​​​​  cstr_cat((*a), "a");
​​​​  cstr_cat((*a), "a");
​​​​}
    • 後來修改成先對 cstr_buffer a 做處理在進入到測試函式

  • 最後，每個對字串操作的都包起來。

reference count

  • wikipedia - 參照計數

    參照計數是電腦程式語言中的一種記憶體管理技術，是指將資源（可以是物件、記憶體或磁碟空間等等）的被參照次數儲存起來，當被參照次數變為零時就將其釋放的過程。使用參照計數技術可以實現自動資源管理的目的。同時參照計數還可以指使用參照計數技術回收未使用資源的垃圾回收演算法。

    當建立一個物件的實例並在堆上申請記憶體時，物件的參照計數就為1，在其他物件中需要持有這個物件時，就需要把該物件的參照計數加1，需要釋放一個物件時，就將該物件的參照計數減1，直至物件的參照計數為0，物件的記憶體會被立刻釋放。

  • wikipedia - Reference_counting

    Reference counts are also useful information to use as input to other runtime optimizations.

    For example,systems that depend heavily on immutable objects such as many functional programming languages can suffer an efficiency penalty due to frequent copies. However, if the compiler (or runtime system) knows that a particular object has only one reference (as most do in many systems), and that the reference is lost at the same time that a similar new object is created (as in the string append statement str ← str + "a"), it can replace the operation with a mutation on the original object.

  • 對增減值的單一操作保證
    • 只要 lock 就好
  • 對增減值最後的結果保證 (結果最後要符合特定值)
  • 執行順序很重要
  • hash table

quiz 3 - xs reference counting

linD026

reference counting

  • 基本定義
    • 有多少個人用他的資料，他就要記錄
  • xs_cow_lazy_copy
    • 不太符合 lazy copy

多執行緒

空間效率

  • 在 xs_new 裡的記憶體配置是以 2 的冪來估算 (capacity)
    • 空間兩倍
    • reclaim
      • 一般性的分配完後，重新分配或直接分配剛好的記憶體
      • 要另設 flag 來標示， capacity 的值也要考慮到(是要大於還是小於)
        • flag <= source
  • wikipedia - Copy-on-write

wikipedia - Copy-on-write
The string class provided by the C++ standard library was specifically designed to allow copy-on-write implementations in the initial C98 standard,[5] but not in the newer C11 standard:[6]

wikipedia - 寫入時複製
C++ 標準程式庫中的 std::string 類，在 C++98/C++03 標準中是允許寫時複製策略。但在 C++11 標準中為了提高並列性取消了這一策略。GCC 從版本 5 開始，std::string 不再採用 COW 策略。

TODO

NOTE

  • 在多執行緒下，資源要進行分類才能夠作效率高的LOCK、資料結構或函式操作也須調整

第一週至第四週問題整理

此標題與其它標題不同，僅整理。

其它標題為當下筆記

第一週

TODO

quiz1

第二週

quiz2

TODO

  • list_sort 的運作原理
    • 符合 cache friendly 的改變
  • 效能檢測 - 記憶體使用量
    • gcc
      • -fstack-usage
    • valgrind
      • -v –leak-check=full
      • valgrind –tool=massif
    • <sys/resource.h>
      • struct rusage
  • 規格書規範
    • 運算時型態的轉換有規定
  • is_power_of_2
    • fls64 的硬體舉例 - Alpha

      舉例解說的微處理器架構用 x86, x86_64, arm, aarch64, risc-v 等架構為主，你可以忽略 Alpha

  • string interning
    • reference count
    • threads

第三週

TODO

quiz3

第四週

quiz4

CS:APP 相關資料整理

主要相關對象為
『 Linux 核心設計 (Spring 2021) 課程進度表暨線上資源 』
『 CS:APP - international Edition - Second Edition 』

week 1

week 3

  • locality of reference

    • CS:APP - Chapter 6 - page 620
      • 跟程式碼避免產生 page fault 的情景很像

        恐龍書的舉例

      • stride-k reference pattern

    延伸閱讀

    • CS:APP - Chapter 6 - 6.3 The Memory Hierachy - Page 625

  • Page

    • CS:APP - Chapter 9 - page 813, 814

Week 7 quiz

GitHub - sysprog21 - concurrent-programs

mbus

  • problem
    • unregister => need refcnt = 0

05/12 - 一對一討論

COSCUP

COSCUP 社群守則

COW

COW - note

LaTeX

A quick guide to LATEX

Last changed by 
 
linD026
0
1
768

Read more

[Linux 核心 Copy On Write 實作機制](https://hackmd.io/@linD026/Linux-kernel-COW-content)

contributed by < linD026 > <font size = 2>此篇所引用之原始程式碼皆以用 Linux Kernel 5.10 版本，並且有關於硬體架構之程式碼以 arm 為主。</font> Copy On Write 概念 digraph abstract { rankdir = LR node [shape = record] label = "Copy on Write" proc1 [label = "process 1"]

May 21, 2025
Linux 核心採納 Rust 的狀況

<font size=3>此文於 2021 、 2022 年間，整理 Rust 現狀在 Linux 核心中遇到的限制以及問題。最新 patch series: [PATCH v3 00/19] Rust support</font>　

Mar 27, 2025
Linux 核心 Read-Copy Update 筆記整理

contributed by < linD026 >

Feb 18, 2025
[Linux 核心 Copy On Write - Memory Region](https://hackmd.io/@linD026/Linux-kernel-COW-content)

contributed by < linD026 > <font size = 2>此篇所引用之原始程式碼皆以用 Linux Kernel 5.10 版本，並且有關於硬體架構之程式碼以 arm 為主。 前篇： Linux 核心 Copy On Write 實作機制</font> Chapter 4 Process Address Space cs.columbia.edu - W4118: Linux memory management digraph abstract { rankdir = LR

Sep 17, 2024
Read more from linD026
Published on HackMD