Linux Kernel Development 3rd筆記

動機

不記實際上怎麼跑與跑了什麼，只記設計與方便未來查詢的部分 畢竟這是基於linux2.6的

整體心得

讀完上一本工作原理來讀這本剛好，可以互補

推薦讀 中斷: ch7~10 mem: ch12&ch15

省略掉 ch1, 14, 20

簡體版的翻譯錯誤有點多要小心，覺得怪就去看原文

ch1

skip

ch2

folder

make

• make menuconfig
  • 調linux的設定
• make defconfig
  • 把menuconfig的設定設成預設
• make oldconfig
  • load從其他地方來的.config
• make
  • compile
  • 在kernel code的根目錄會產生System.map，裡面有symbol，需要可以看

kernel dev的特點

• 沒有libc與stdlib
  • linux有自己的工具，可以看include裡面的header，像/inlucde/linux就是linux kernel的函數
• 用gnu c
  • inline
  • asmembly 內嵌
  • likely, unlikely之類的if優化
• 沒有mem保護
  • 沒有seg fault，只剩panic
• 幾乎不能用floating point
• kernel stack十分小，並隨arch不同而有改變
• 同步很重要
  • preempt
  • smp(多對稱處理器，多cpu)

ch3

proc

相關struct

• struct task_struct
  • 在<linux/sched.h>
  • proc的DS，有
    • pid
    • addr space
    • 打開的文件 等…
• struct thraed_info
  • 在<asm/thraed_info.h>
  • 放在kernel stack上，用以找到task_struct
    • 為什麼不直接放task_struct
  • 放proc中與arch有關的訊息
    • 可以想成goroutines的struct P

proc state

• 正在跑、可以跑
  • TASK_RUNNING
• 睡
  • TASK_INTERRUPTABLE
    • 等interrupt或其他或signal
  • TASK_UNINTERRUPTABLE
    • 不管signal，其他與TASK_INTERRUPTABLE一樣

clone syscall

• fork
  • clone(SIGCHID, 0)
• kthread
  • clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0)
    • VM: virtual mem
    • FS: file system
    • FILES: opend files
    • SIGHAND: signal handler
• vfork (會sync執行的fork)
  • clone(CLONE_VFORK | CLONE_VM | SIGCHID, 0)

ch4

proc scheduler

proc吃?

• IO
  • scheduler應該要多拉吃IO的proc
    • 不然response time會變慢
  • 但throughput會低
• cpu
  • scheduler應該多拉吃cpu的proc
    • 不然throughput會變慢
  • 但response time會變慢

time slice

• 一個proc能佔cpu多少時間
  • 太長
    • 對吃cpu有利
    • 對吃IO不利
    • 高throughput
    • 差response time
    • cxt switch的總計花費時間小
  • 太短
    • 對吃cpu不利
    • 對吃IO有利
    • 低throughput
    • 好response time
    • cxt switch的總計花費時間多

proc優先級

• nice
  • -20~19
  • 越小越優先
• real-time priority
  • 0~99
  • 越大越優先
  • RT proc永遠優先於普通proc
• 兩個是各自獨立的系統

公平調度(CFS)

• 概念
  • 依據cpu的使用比例分配
    • 分配到的時間與系統負載密切相關
  • 搶的時機是如果有proc花的使用比比當前proc少，就換上去
  • 每個proc預設拿到1/n個cpu時間
    • n是proc個數
    • 就是想像一共有proc個數 個cpu
    • cpu時間在書中叫目標延遲
  • nice就是原本的1/n再乘上nice換出來的比值
• 實作
  • 計時
    • 在<linux/sched.h>
    • struct_sched_entity
      • vruntime
        • 會記錄運行時間
        • 以及以proc總數做標準化
  • choose proc
    • 挑vruntime最小的
  • sched的interface
    • schedule()
      • 如果要睡覺
        • 就是設定proc state再call這個
        • 假喚醒
          • 如果state是TASK_INTERRUPTABLE就會被signal叫醒
          • 所以要檢查喚醒後發生什麼事
• cxt switch
  • 在<asm/mmu_context.h>
    • switch_mm換virtual mem
  • 在<asm/system.h>
    • switch_to換cpu state
• preempt
  • 用一個flag，need_resched去看該不該被搶
  • 誰可以設?
    • scheduler
    • proc自己
  • preempt發生時機
    • user preempt
      • 從syscall回到userspace
      • 從中斷處理程序回到userspace
    • kernel preempt
      • 中斷處理程序結束，且回到kernel space之前
      • kernel的code再一次可以被搶的時候
        • need_resched被設
        • preempt_count是0 (在thread_info)
      • kernel的code被block時
      • kernel的code調用schedule()
• RT schedule
  • SCHED_FIFO
    • proc一直跑，除非
      • block
      • 自己想換
  • SCHED_RR
    • 有time slice的SCHED_FIFO
    • 低優先無法搶高優先即使對方的time slice花完了
  • 都是soft rt

ch5

syscall在上一篇筆記就說了，所以這裡focus在一些之前沒提到的東西

• asmlinkage
  • 叫compiler只能從stack拿參數
• 參數驗證
  • ptr的addr是userspace的addr
  • ptr的addr在proc的addr space中
  • 讀寫要符合原本的讀寫限制
  • 參數有效
    • pid有效
    • 檔案有效
• process context
  • syscall是在process cxt
  • 會睡覺
  • 會被搶
• 在你想多加一個syscall(衝動)之前，可以
  • 用dev file實現read, write，配合ioctl
  • 創其他操作介面，像semaphore可以像file一樣操作
  • sysfs

ch6

list_elment

• 在<linux/list.h>
• Linked List (bidiretion)
• 用法是在自己的struct中放一個list_elment
  • 因為c沒泛型!!
  • c應該叫mem描述語言才對
• 沒有特別需求時優先用list

kfifo

• 在<linux/kfifo.h>
• Queue
• 遇到 consumer/producer時用

idr

• 在<linux/idr.h>
• Hash table
  • uid(int) -> void *
• 要mapping時就用

rbtree

• 在<linux/rbtree.h>
• 紅黑樹
• 沒有find與insert，要自己寫
  • 因為c沒泛型!!
• 大量data與反覆search就用

ch7

中斷(IRQ)

• 就是一個數字
• 異常與中斷很像
  • 但異常要與cpu時鐘同步

中斷上下文

• 不會block(睡覺)
• 當他出現時，一定是
  • 打斷了某個proc
  • 甚至是，不同irq stack的irq

上半段 與 下半段

• 上半段: 馬上處理
• 下半段: 原本中斷中可以之後再處理的

request_irq

• 註冊irq
• 會sleep

reenter?

• irq被call時，該irq會被mask起來，其他cpu看不到

IRQF_SHARED

• 多個dev用同一個irq
• 所以
  • dev的addr唯一，也就是可以區分不同device
  • code有辦法對應不同device

/procs/interrupts

• PC上所有irq的資訊

中斷控制器

• 停用
  • cpu上的整個中斷
    • 這樣這個cpu上就不會被preempt
    • 但其他cpu還是可以中斷!!
  • 所有cpu的某個中斷
• 看<asm/system.h>與<asm/irq.h>

ch8

中斷，下半段

softirq

• 同一個softirq可以同時跑在其他cpu上
• 靜態註冊 (compile-time)
  • 在<linux/interrupt.h>
    • struct softirq_action
  • softirq放在array中(32個)
• 中斷上下文
• softirq沒辦法搶其他的softirq
  • softirq只會被irq搶!!
• 跑什麼softirq
  • irq handler在return前會標
• 什麼時候跑softirq?
  • irq handler在return時
  • 在softirqd中
  • 有人去看還有哪些softirq還沒跑與直接執行softirq的時候

tasklet

• 同一個tasklet不可以同時跑在其他cpu上
• 動態註冊
  • 在<linux/interrupt.h>
    • struct tasklet_struct
    • 有執行狀態
      • 所以其他cpu不會跑正在跑的tasklet
  • tasklet放在cpu上的linked list
    • tasklet_vec
    • tasklet_hi_vec (hi是high)
    • 所以可以動態加
• 中斷上下文
• tasklet就是掛在兩個softirq上
  • 把task往裡面放，需要時就跑

ksoftirqd

• 每個cpu上會有一個
• 處理大量softirq
  • 在最低nice的kthread中去調用還沒跑的softirq

work queue

• proc上下文
  • 可以allocate大mem
  • semaphore
  • 用block IO
• 每個cpu一個queue與kthread，跑task
  • 我們需要一個可以看到所有cpu的struct
    • 在<linux/workqueue.h>
      • struct workqueue_struct
        • 放workqueue訊息
    • proc叫event/n
      • 在<kernel/workqueue.c>
        • struct cpu_workqueue_struct
          • 就是queue
      • 在<linux/workqueue.h>
        • struct work_struct
          • 就是task
      • 每個cpu上會有一個
      • n是cpu編號

how to lock

• proc cxt與bottom half分享data
  • 鎖bottom half
  • 拿鎖
• irq cxt與bottom half分享data
  • 鎖irq
  • 拿鎖
• irq -> softirq/tasklet -> proc
  • 如果要和上一層share data
    • 鎖上一層!!
      • 防smp與preempt
    • 拿鎖
  • 可以看Unreliable Guide To Locking有詳細的解釋

ch9&10

怎麼等鎖

• busy waiting
  • 都能用
• sleep
  • only in proc ctx

要同步的原因是

• in userspace
• preempt
• re schedule
• in kernel space
  • irq
  • softirq/tasklet
  • preempt
  • sleep & sync with userspace
  • smp

struct什麼時候加鎖

• kernel struct大部分都要
• 有其他proc可以access
• 任何人都看的到的

原子性與順序性

• 原子性
  • 執行期間不打斷，只有兩個case
    • 沒有跑
    • 跑完了
• 順序性
  • ABC分散在不同中，也要ABC去跑
    • 用lock只能保證，ABC一起跑，一起不跑
    • 用semaphore可以幹出來
    • 主要用barrier

讀寫鎖(RW)

• 只能有下面的其中一種case
  • 1寫
  • 多讀
• 有利於讀
  • 只要一堆讀，寫就只要等就飽了

工具

• atomic_t
• spinlock
  • busy waiting
    • 使用時不能sleep
    • 不然就是增加整體的response time
  • 如果lock時間小於2次ctx switch才有利
  • no recur
    • 不能鎖了又鎖
  • 在irq中用的話
    • 先關irq
    • 不然被中斷，另一irq又拿同一個鎖的話…
  • 有RW版
  • 禁止preempt
    • 持有spinlock就是禁止preempt
• semaphore
  • sleep
    • only in proc ctx
  • 任何持有人都可以上鎖或解鎖!!
  • 可以超過一個人到critical zone
  • 有RW版
• mutex
  • sleep
    • only in proc ctx
  • 上鎖的人才能解鎖
  • 只有一個人能到critical zone
  • 可以recur
  • 可以處理priority inversion
• complete variable
  • cond var
• seq lock
  • 實作
    • 有一個acc
    • 當write拿鎖時，會acc++
    • read時就是確認開始與結束的acc值是不是一樣
      • 確認中間沒有write
    • 也可以透過acc是不是偶數看寫結束語否
  • 有利於寫
• mem barrier
  • barrier前面的code跑完前，絕對不會跑後面去
  • 起因於
    • 指令重排，所以有些指令會跑到後面去
    • 前半部的code不會到reorder到後面去

priority inversion

• 一般來說是在RT才會提，但想到就記一下
• 情境
  • pri最小(A)拿到lock中被中斷
  • pri高的(C)想拿lock，但拿不到!!
    • 像spinlock會busy waiting
  • pri高的跑不動，time slice吃完
  • 有下一個pri比較低的(B)，來了，也做完了!?
  • 但pri高的還沒做完阿!!
• 起因
  • lock的效果會影響優先權，但是沒有納入原有優先權的系統中
    • 像只要有人拿了spiclock，那他在這一塊就是最優先的
    • 不管其他優先權怎麼設，bust waiting就是wait，沒有轉圜的機會
    • 同時也無法打斷，不然就不是crtical zone了
• 解法
  • 大方向: crtical zone要先跑!!
    • 要改crtical zone的優先權
      • 改到與現在最高的一樣高
      • 改到沒有人比crtical zone高
  • Priority inheritance
    • 在crtical zone時，遇到更高的proc同時要進來
    • 把crtical zone的優先權拉到與那個proc一樣高
    • 跑完crtical zone就降回去
  • Priority ceiling protocol
    • 在crtical zone時拉到最高
    • 跑完crtical zone就降回去

ch11

怎麼算1秒

• 系統計時器會依一定頻率(tick rate)打中斷
  • 這樣kernel知道兩次中斷之間的間隔時間(tick)
• HZ就是1sec打幾次
  • HZ可以改!!
  • HZ越高
    • 時間精準度越高
      • 連帶與時間有關的都會變準
        • poll, select
        • preempt
    • system load上升
  • 這是kernel用的
    • userspace的叫USER_HZ
• 1sec = tick * HZ

開機多久了

• jiffies
  • 紀錄系統計時器中斷打了幾次
• jiffies/HZ => 開機多久

硬體

• RTC
  • bios上存時間(幾點幾分之類的)的
  • 就算電腦關機，還是藉由CMOS繼續跑
  • 開機時初始化xtime變數
• 系統計時器
  • 由kernel設定tick rate

關於proc的計時

• 每一次中斷時就把當前proc狀態(idle, run…)的變數遞增一次
  • 如果在這中斷之間多次換狀態?
    • 不管，現在他在這個狀態，這一段時間都是這個狀態的

如何delay

delay執行，不應該在有lock時或是關閉中斷後發生

• busy wait
  • base on jiffies
• short delay
  • 如果要的delay比tick小
  • 用udelay(),ndelay(),mdelay()
    • 裡面其實也是loop，但是kernel知道他會跑多久且不用jiffies
• schedule_timeout()
  • 讓task睡，在超過指定時間後跑
    • 沒辦法說很精確在時間到就馬上跑
  • soft rt

ch12

kernel space的mem

整體

• phy
  • mem
    • byte
    • word
  • cpu
    • page
• kernel
  • struct zone
    • 在<linux/mmzone.h>
    • struct page
      • 在<linux/mm_types.h>
      • 對應到實體的page
      • 再從page換成addr
        • alloc_pages -> page_address
        • kmalloc
          • 不能要求ZONE_HIGHEM
            • 因為可能還沒分配邏輯addr
            • 用alloc_pages
        • 上面都是
          • 連續的page
          • 可以sleep時用GFP_KERNEL
          • 不可以sleep時用GFP_ATOMIC
        • vmalloc
          • 可能不連續的page
    • 不同page在不同位置，所以有不同區
    • 4種
      • ZONE_DMA
      • ZONE_DMA32
        • only for 32bits device
      • ZONE_NORMAL
      • ZONE_HIGHEM
        • high mem用，不能用永久map到kernel addr空間
        • 想想kernel都是用低的mem，所以高的其實算是userspace的
          • 如果要用就要map
            • 永久: kmap (low與high都能用，會睡覺)
            • 臨時: kmap_atomic (不會睡，但是會被下一個)
  • slab
    • 在快取記憶體上(kmem_cache)開一個list當成object pool
      • 之後重複利用裡面已經存在的obj
      • slab就是list上的node，node裡面放obj
    • struct slab
      • 在<mm/slab.c>

額外

• stack
  • 每個proc有
    • kernel stack
      • 1~2 page (根據arch)
      • 原本中斷也是用被中斷的proc的stack
      • kernel stack本來就很小，還是別吧
        • 最後有了interrupt stack
    • user stack
      • 就一般的stack
      • kernel stack是為了與user stack分開
      • 想想兩個混在一起會發生什麼事
  • 每個cpu有
    • interrupt stack
• percpu
  • 每個cpu自己的data
  • 因為是cpu自己的，所以
    • cache失效降低
    • 不用擔心smp
      • preempt還是要怕

ch15

user space的mem

整體

• proc的userspace的mem空間
  • struct mm_struct
    • 在<linux/sched.h>
    • 可以到/proc/<pid>/maps看proc現在有什麼
    • 主要兩個
      • struct vm_area_struct
        • 在<linux/mm_types.h>
        • 就是這裡的page，加上權限與狀態之類的
        • 在mm_struct有兩個obj放vm_area_struct
          • list: 方便iterate
          • rbtree: 方便找定點
      • pgd_t
        • phy的page表
          • 三層 (pgd -> pmd -> pte)
        • 用這個換出實際addr

額外

• kthread的mm
  • kthread天生沒有mm (不然怎麼有k)
  • 當需要的時候會從proc的ptr拿到
    • 當schedule會存前一個proc的mm (active_mm)
    • 當kthread需要(像page table)，就直接用active_mm看
• mmap
  • 把file放到proc的userspace的mem空間
    • 生一個addr出來

ch13

virtual file system的流程

1. userspace
2. virtual file system
3. 真的file system
4. phy

VFS的attribute

• superblock
  • 真的file system (ext4, brtfs…)
    • struct file_system_type
      • 在<linux/fs.h>
      • 放fs的訊息(kernel關心的)
    • struct vfsmount
      • 在<linux/mount.h>
      • fs的統計數據與安裝訊息(root, dev等等)與安裝點
        • 可以當成實際fs的入口
  • 放fs的訊息(VFS關心的)
  • struct super_block
    • 在<linux/fs.h>
• inode
  • file or folder
  • 放file/folder的訊息
  • struct inode
    • 在<linux/fs.h>
• dentry
  • path的一部份
    • /usr/bin/vi的
      • /, usr, bin, vi
    • 其實可以當成inode，但是為了查找path，所以獨立出來
  • struct dentry
    • 在<linux/dcache.h>
  • state
    • 被用
      • 有對應的file
      • 也正在被ref
    • 還沒被用
      • 有對應的file
      • 沒被ref
    • 不在
      • 根本沒這個file
        • 總不能每次要等整個找完才丟沒有指定的檔案吧
        • 同時，因為有這個與slab，在之後真的有檔案也可以直接快取
• file
  • opend file
  • struct file
    • 在<linux/fs.h>

看看proc

• 每個proc都有
  • struct files_struct
    • 在<linux/fdtable.h>
    • 紀錄 開過的檔案
  • struct fs_struct
    • 在<linux/fs_struct.h>
    • 紀錄 pwd, 現在跑的檔案
• 每個namespace都有
  • struct mmt_namespace
    • 在<linux/mmt_namespace.h>
    • 放vfsmount，讓同一namespace的去找

ch14

skip

ch16

快取策略

• nowrite
  • 不管cache，直接寫到mem
  • cache直接失效
• write-through
  • 同時更新cache與mem
• write back
  • 先更cache
  • 再找時間更mem

快取無效策略

• LRU
  • 從list中拿掉最少用到的
• LRU/2
  • 兩條list
    • 熱的
    • 不熱的
  • 變成熱的方式
    • 在不熱的中
    • 有被用到
  • 如何調整兩條list
    • 熱的比不熱的長
    • 把一些去掉
  • 怎麼去掉
    • fifo (不是最少用到)
    • 熱的list就是原本LRU中記錄頻率的腳色
    • 只要在熱的list就是有用過

page快取(上一篇心得的file快取)

• struct address_space
  • 在<linux/fs.h>
  • 應該叫page_cache_entity
• 這是write back
  • 什麼時候寫回去
    • cache要沒了
    • cache放太久了
    • 有人callsync(),fsync()
  • 誰去寫
    • 靠flusher的多thread去寫 (原本是單thread)
      • 但還是會被底下的IO給bound

ch17

編module

makefile

obj-m += foo.o
# obj-m += foo.o 加在sourcetree中的makefile中
foo-objs := foo-main.o foo-utils.o

• 編
  • make -C /kernel/path SUBDIRS=$PWD modules
• 安裝
  • make modules_install
• 生相依訊息
  • depmod
  • depmod -A only for new added modules
• 加編譯選項
  • 改Kconfig

export what?

• 參數
  • static int a = 1;
  • module_param_named(exported_name, a, int, 0644);
• symbol table
  • EXPORT_SYMBOL(your_func);
  • EXPORT_SYMBOL_GPL(your_func);

device model & sysfs

• device model

  • struct kobject

    • 在<linux/kobject.h>
    • 就是obj
    • 與list一樣要嵌到其他struct上才有用
    • 在sysfs中會變成folder
      • 他的參數會變成file
        • struct attribute
          • 在<linux/sysfs.h>
        • 會有值，可讀寫
          • struct sysfs_ops
            • 在<linux/sysfs.h>
            • 有read/write可以實作

  • struct ktype

    • 在<linux/kobject.h>
    • 就是放methods

  • struct kset

    • 在<linux/kobject.h>
    • 就是class(obj的base，js的prototype)
• sysfs
  • block
    • 列出註冊的block dev
  • bus
    • 列出系統的bus
  • class
    • 列出依func排列的dev
      • net, block, ppp, rtc等等
  • dev
    • 列出註冊的dev
      • block, char
  • devices
    • 列出dev的topo
      • platform, system, virtual等等
  • firmware
    • 與系統有關的low-level子系統
      • ACPI, EDD, EFI
  • fs
    • 列出filesystem
  • kernel
    • 列出kernel狀態與option
  • modules
    • 列出載入的module
  • power
    • 列出電源管理的資料

ch18&19

開發tips

• 保留一個能動的，一個用新版，其他用舊版
  • 用uid(user)去切
  • 加個condition
• 加統計量
• 限制output的頻率
  • 每個幾秒印一次
  • 只印幾次
• 輸出自己的錯誤訊息
  • 我自己會在一定看的到的地方(像家目錄)，放log

align

由大到小去排

// total: 12
struct A {
  char a; // 1+3
  unsigned long b;  // 4+0
  unsigned short c; // 2+1+1
  char d;
};

// total: 8
struct B {
  unsigned long b; // 4+0
  unsigned short c; // 2+1+1
  char a;
  char d;
};

big/little endian

• 變成binary: 會變成abcd
• 最左是最高有效位
• big-endian: 最高有效位放arr第一個
• little-endian: 最低有效位放arr第一個

最高有效位與最低有效位的技法: 下坡(反斜線)，所以最高在左邊

一些數字

• 不要假設HZ、page的長度
• 沒有寫明長度的type的長度都是不確定的
  • 除了
    • char是1byte (ansi c)
    • int通常是32位

ch20

skip