# Kcalc
## 問題探討
### Character device register kernel API( register_chrdev vs. register_chrdev_region vs. alloc_chrdev_region )

[引伸自 ` johnnylord `的共筆](https://hackmd.io/@johnnylord/SJyiQ13wV?type=view)

[Character device vs. Block device](http://haifux.org/lectures/86-sil/kernel-modules-drivers/node10.html)

#### register_chrdev_region()

int register_chrdev_region(dev_t from, unsigned count, const char *name)

Arguemets:
* from: the first in the desired range of device numbers; must include the major number.
* count: the number of consecutive device numbers required
* name: the name of the device or driver

* 搭配 ` MKDEV ` 這個 macro 使用。
行為：
* 先使用 major number( 12bits ) 與 minor number( 20bits ) 使用` MKDEV `取得`from` 這個參數。 也就是這個 device driver 獨一無二的識別碼。
* 放入 ` register_chrdev_region ` 中。
* 如果回傳 = 0，即成功。
* 如果成功，則還要使用 cdev_init() 將把 file operations 註冊到 remapping table 裡。
* 最後 cdev_add ， 將 driver 到 kernel 裡面。
* 然後就能使用 driver 了！

#### register_chrdev()

int register_chrdev(unsigned int major, const char *name, const struct file_operations *fops);

Arguemets:
* major: major device number or 0 for dynamic allocation
* name: name of this range of devices
* fops: file operations associated with the devices

行為：
* 將 major number, name, file operations 放進這個 function
* return 的數值就是 major number
* 因此只要 = 0 或 < 0 都是失敗的情況。
* 然後，就能直接使用 driver 了！

#### alloc_chrdev_region()

int alloc_chrdev_region (dev_t *dev, unsigned  	baseminor, unsigned count, const char *name);

Arguemets:
* dev: output parameter for first assigned number
* baseminor: first of the requested range of minor numbers
* count: the number of minor numbers required
* name: the name of the associated device or driver

行為：
* 這邊的 `dev` 這個參數不用先準備好，宣告後不用給值。
* 給定 `baseminor` 讓這個 function ，幫你從它開始找可用的 minor number。 For instance, baseminor = 10, your minor number could be any number >= 10!
* 不論如何，在這邊的 major number 都是系統配置的！
* 回傳數值 = 0，即成功。
* 同樣，後面要做 cdev_init, cdev_add。

#### 比較
| API | Major number | Minor number |
| --- | --- | --- |
| `register_chrdev` | 可自動分配也可開發者指定 | 系統分配 |
| `alloc_chrdev_region` | 系統自動分配 | 開發者自行指定基底和範圍 |
| `register_chrdev_region` | 開發者指定 | 系統分配 |

總歸來說， register_chrdev 承包了大部分會作的事情，也可作自動分配等等功能，不過沒辦法指定 minor number ， alloc_chrdev_region 與 register_chrdev_region 則作差不多的事，只分配 major, minor number，剩下的 file operations remapping 跟 kernel 的動作仍要自己額外去作。
不過， register_chrdev_region 可以指定使用哪個 major number!

### Change file mode

        chmod - change file mode bits

* file mode bits: 用來形容 file 權限的 bits 們

crw-------  1 root root     10,   240 Jun 22 14:27 userio

例如這個例子， 前面的 crw------- 就是從 file mode bits 得到的資訊。

* 4 stands for "read",
* 2 stands for "write",
* 1 stands for "execute", and
* 0 stands for "no permission.1

> 可推廣為 4 + 2 = 6， 代表權限改為可 read + wite ， 以此類推。
> [name=Julian Fang]

chmod 0666

> 第一個 6 代表 user，第二個 6 代表 group ，最後一個代表 others。
> [name=Julian Fang]

### 浮點運算在 Linux kernel 中的特別對待，以及 context switch 的過程中，涉及到 FPU/SIMD context，該注意什麼？
[引伸自 ` rebvivi ` 的共筆](https://hackmd.io/@1az9eaZgQwG38Qx2YiKXDw/BkW1Bn3U4?type=view#1-%E8%A7%A3%E9%87%8B%E6%B5%AE%E9%BB%9E%E9%81%8B%E7%AE%97%E5%9C%A8-Linux-%E6%A0%B8%E5%BF%83%E4%B8%AD%E7%82%BA%E4%BD%95%E9%9C%80%E8%A6%81%E7%89%B9%E5%88%A5%E5%B0%8D%E5%BE%85%EF%BC%8C%E4%BB%A5%E5%8F%8A-context-switch-%E7%9A%84%E9%81%8E%E7%A8%8B%E4%B8%AD%EF%BC%8C%E6%B6%89%E5%8F%8A%E5%88%B0-FPUSIMD-context%EF%BC%8C%E8%A9%B2%E6%B3%A8%E6%84%8F%E4%BB%80%E9%BA%BC%EF%BC%9F%E6%8F%90%E7%A4%BA-%E5%8F%83%E7%85%A7-Lazy-FP-state-restore-%E5%92%8C%E4%B8%8A%E6%96%B9%E5%8F%83%E8%80%83%E8%B3%87%E6%96%99%E3%80%82%E6%87%89%E8%A9%B2%E6%92%B0%E5%AF%AB%E5%B0%8D%E6%87%89%E5%8C%85%E5%90%AB%E6%B5%AE%E9%BB%9E%E9%81%8B%E7%AE%97%E7%9A%84-Linux-%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%EF%BC%8C%E5%AF%A6%E9%9A%9B%E7%B7%A8%E8%AD%AF%E5%92%8C%E6%B8%AC%E8%A9%A6)

- 進行浮點數運算的時候，往往會遇到許多問題
* 輸入與儲存的值不一定精確，可能原因：
* 輸入值本身就不精確
* 儲存浮點數用的記憶體有限
* 不同底數之間的轉換不精確
* 輸入與儲存產生 overflow
* 計算的結果會有誤差：
使用浮點數進行運算時會有上述產生的許多誤差，這些誤差經過反覆而且大量運算之後很有可能會蔓延到其它所在，從而產生不可收拾的後果

#### FPU, SIMD
[What is SIMD?](https://www.quora.com/What-is-SIMD)
[Computer Architecture:SIMD/Vector/GPU](https://www.archive.ece.cmu.edu/~ece740/f13/lib/exe/fetch.php?media=seth-740-fall13-module5.1-simd-vector-gpu.pdf)

- `Floating Point Unit（FPU）`：專用於浮點運算的處理器
- `Single Instruction Multiple Data (SIMD)` : 同時對多個數據執行同一條CPU指令。
#### Context switch and Lazy context switch
[reference](http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.prd29-genc-009492c/ch05s03s01.html)

- `context switch`: 轉換CPU至另一項行程時必須將舊行程的狀態儲存起來，然後再載入新行程的儲存狀態
- `Lazy context switch`：應用於 FPU 的 context switch ，在沒有指令的時候會先被 disable ， 一直等到 FP 指令被執行的時候才 enable FPU ，然後載入資料。

>每次 context switch 的時候如果 CPU 和 FPU 都要做 context switch 會使系統的 overloading 增大，因為存取 FPU 的 hardware context 需要更多的 CPU time

- 在 context switch 的過程中，如果涉及到 FPU context ，會執行`Lazy context switch`，也就是僅在需要時保存並還原 FPU ，但這可能會面臨一些安全性的問題：
* 可以利用 Lazy FP 狀態還原功能，潛在允許一個 process 從另一個 process 推斷數據
* 推斷到的數據也可能包括已加密操作的信息，這個安全漏洞會影響到CPU的預測執行推測執行機制

## 定點數 (fixed-point) vs. 浮點數 (floating-point)
除了浮點數以外的小數表達方法：定點數

### 三個定點數實例

## Kernel 與 userspace 之間的溝通
### Kernel API: copy_to_user()

unsigned long copy_to_user(void *to, const void *from, unsigned long n);

Arguements:
* to：destination address in user space
* from：source address in kernel space
* n: number of bytes to copy
Return:
* 不能被複制的 bytes，如果完全成功，返回值為 0 。

From [kcalc/calc.c](https://github.com/sysprog21/kcalc/blob/master/calc.c)

static ssize_t dev_read(struct file *filep, char *buffer, size_t len, loff_t *offset)
{
    int error_count = 0;
    if (*msg_ptr == 0) {
        return 0;
        }

    memset(message, 0, sizeof(char) * BUFF_SIZE);
    snprintf(message, 64, "%d\n", result);
    size_of_message = strlen(message);

    error_count = copy_to_user(buffer, message, size_of_message);
    if (error_count == 0) {
        printk(KERN_INFO "CALC: size: %d result: %d\n", size_of_message,
               result);
        while (len && *msg_ptr) {
            error_count = put_user(*(msg_ptr++), buffer++);
            len--;
        }

        if (error_count == 0) {
            return (size_of_message);
        } else {
            return -EFAULT;
        }
    } else {
        printk(KERN_INFO "CALC: Failed to send %d characters to the user\n",
               error_count);
        return -EFAULT;
    }
}

這個例子中，使用 copy_to_user 來實作 read from device 的功能。
可以用 return 的值來了解，是否有發生錯誤，或是傳送成功！

### 資料量增長，是否會有效能的嚴重衝擊呢？
[引伸自 ` rebvivi ` 的共筆](https://hackmd.io/@1az9eaZgQwG38Qx2YiKXDw/BkW1Bn3U4?type=view#4-%E5%9C%A8-calcc-%E6%AA%94%E6%A1%88%E4%B8%AD%EF%BC%8C%E7%94%A8%E5%88%B0-copy_to_user-%E9%80%99%E5%80%8B-kernel-API%EF%BC%8C%E5%85%B6%E4%BD%9C%E7%94%A8%E7%82%BA%E4%BD%95%EF%BC%9F%E6%9C%AC%E4%BE%8B%E4%BD%BF%E7%94%A8%E8%A9%B2-API-%E5%81%9A%E4%BA%86%E4%BB%80%E9%BA%BC%E4%BA%8B%EF%BC%9F%E8%8B%A5%E6%98%AF%E8%B3%87%E6%96%99%E9%87%8F%E5%A2%9E%E9%95%B7%EF%BC%8C%E6%98%AF%E5%90%A6%E6%9C%83%E6%9C%89%E6%95%88%E8%83%BD%E7%9A%84%E5%9A%B4%E9%87%8D%E8%A1%9D%E6%93%8A%E5%91%A2%EF%BC%9F)
* 如果使用copy_to_user時，要複製的資料量太大，就會讓 buffer 產生 overflow，導致效能降低
* 如果 user 讀取到錯誤的資料，可能導致程式崩潰
* 如果後面的記憶體存放著應用程式的資料，則會導致其他功能讀取到錯誤的資料，因此工作不正常，也可能導致程式崩潰。

提出實際案例 [HID: debug: check length before copy_to_user](https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=717adfdaf14704fd3ec7fa2c04520c0723247eac)

## MathEX
### `MathEx` 如何解析給定字串，從而分離出變數和對應數學表示法呢？

## 程式與實驗
延續自 afcidk 同學的工作 [Github](https://github.com/afcidk/kcalc)，並針對同學的程式碼做強化

shell script 如果是 `NAN_INT` `INF_INT` 不會正確顯示 會錯誤的顯示數字

Testing  0/0 ...
.20000000000000000000
Testing  1/0 ...
.20000000000000000000

主因是沒有針對 `NAN_INT` `INF_INT` 兩個特殊的定義做檢查造成的

test_op() {
    local expression=$1 
    echo "Testing " ${expression} "..."
    echo -ne ${expression}'\0' > $CALC_DEV
    ret=$(cat $CALC_DEV)
    # Transfer the self-defined representation to real number
    num=$(($ret >> 4))
    frac=$(($ret&15))
    neg=$((($frac & 8)>>3))
    
    [[ $neg -eq 1 ]] && frac=$((-((~$frac&15)+1)))
    
    
    echo "$num*(10^$frac)" | bc -l
}    

修正後的結果

test_op() {
    local expression=$1 
    local NAN_INT=31
    local INF_INT=47
    echo "Testing " ${expression} "..."
    echo -ne ${expression}'\0' > $CALC_DEV
    ret=$(cat $CALC_DEV)
    # Transfer the self-defined representation to real number
    num=$(($ret >> 4))
    frac=$(($ret&15))
    neg=$((($frac & 8)>>3))
    
    [[ $neg -eq 1 ]] && frac=$((-((~$frac&15)+1)))
    
    if [ "$ret" -eq "$NAN_INT" ]
    then
        echo "NAN_INT"
    elif [ "$ret" -eq "$INF_INT" ]
    then 
        echo "INF_INT"
    else
      echo "$num*(10^$frac)" | bc -l
    fi
}

Testing  0/0 ...
INF_INT
Testing  1/0 ...
INF_INT

這邊處理了一些例外狀況，但是還是發現一些數值上的運算錯誤，如上圖 `0/0` 應該是 `NAN_INT` 而非 `INF_INT`，還有其他數值錯誤像是對於負數的除法結果並不正確，乘法與加法的 overflow 沒有做處理，且也沒有處理 減法的 underflow。

// overflow when add 
Testing  9999999999999999999999999999999999999999999999+1 ...
0
// wrong when 負數除法
Testing  (-100)/5 ...
252850180000000
// wrong when edge case
Testing  0/0 ...
INF_INT
//wrong when mult overflow
Testing  999999999999999*999999999999999999999 ...
-57049087

先針對 `0/0` 這個例外的例子做處理

int divid(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);
    // 加入判斷條件
    if (n1 == 0 && n2 == 0)
        return NAN_INT;
    if (n2 == 0)
        return INF_INT;

    while (n1 * 10 < ((1 << 25) - 1)) {
        --frac1;
        n1 *= 10;
    }
    int n3 = n1 / n2;
    int frac3 = frac1 - frac2;

    return FP2INT(n3, frac3);
}

處理加法的 overflow

int plus(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);

    while (frac1 != frac2) {
        if (frac1 > frac2) {
            --frac1;
            n1 *= 10;
        } else if (frac1 < frac2) {
            --frac2;
            n2 *= 10;
        }
    }
    
    n1 += n2;
    // 新增這行檢查，去看說加完的結果是否發生overflow
    if((~n1) >> 31 && (n1 & (15) << 28)) return INF_INT;
    return FP2INT(n1, frac1);
}

Testing  0/0 ...
NAN_INT
Testing  1/0 ...
INF_INT

解決負數除法錯誤的情況。

int divid(int a, int b)
{
    int frac1 = GET_FRAC(a);
    int frac2 = GET_FRAC(b);
    int n1 = GET_NUM(a);
    int n2 = GET_NUM(b);
    int sign = 1;
    printk("a : %d b : %d",a,b);
    printk("n1 : %d n2 : %d frac1 : %d frac2 : %d",n1,n2,frac1,frac2);
    if (n1 == 0 && n2 == 0)
        return NAN_INT;
    if(n1 == NAN_INT || n2 == NAN_INT)
        return NAN_INT;
    if (n2 == 0)
        return INF_INT;
    
    // check if there is negative number
    if(n1 < 0){
        sign = -sign;
        n1 = -n1;
    }
    if(n2 < 0){
        sign = -sign;
        n2 = -n2;
    }

    while (n1 * 10 < ((1 << 25) - 1)) {
        --frac1;
        n1 *= 10;
    }
    int n3 = (n1 / n2)*sign;
    int frac3 = frac1 - frac2;

    return FP2INT(n3, frac3);
}

成功解決除法結果錯誤的問題

Testing  (-100)/(-100) ...
1
Testing  (-100)/5 ...
-20