changed 6 years ago
Linked with GitHub

2019q1 Homework2 (fibdrv)

contributed by < JulianATA >

Reviewed by jeffcarl67

  • mutex 的實驗中, 可以加入一份使用 mutex 相關操作的程式碼, 實際比較在有無 mutex 的情況下程式的行為有何不同

Environmet

$ uname -a
Linux 4.15.0-20-generic
$ gcc -v
gcc (Ubuntu 7.3.0-27ubuntu1~18.04) 7.3.0

自我檢查清單

檔案 fibdrv.c 裡頭的 MODULE_LICENSE, MODULE_AUTHOR, MODULE_DESCRIPTION, MODULE_VERSION 等巨集做了什麼事,可以讓核心知曉呢? insmod 這命令背後,對應 Linux 核心內部有什麼操作呢?請舉出相關 Linux 核心原始碼並解讀

MODULE_LICENSE

In fibdrv.c:

MODULE_LICENSE("Dual MIT/GPL");
MODULE_AUTHOR("National Cheng Kung University, Taiwan");
MODULE_DESCRIPTION("Fibonacci engine driver");
MODULE_VERSION("0.1");

We used these macros to define our modules.
Take a look at linux/module.h.(use License as example):

#define MODULE_LICENSE(_license) MODULE_INFO(license, _license)
.
.
.
#define MODULE_INFO(tag, info) __MODULE_INFO(tag, tag, info)

Found __MODULE_INFO in linux/moduleparam.h:

#ifdef MODULE
#define __MODULE_INFO(tag, name, info)					  \
static const char __UNIQUE_ID(name)[]					  \
  __used __attribute__((section(".modinfo"), unused, aligned(1)))	  \
  = __stringify(tag) "=" info
#else  /* !MODULE */
/* This struct is here for syntactic coherency, it is not used */
#define __MODULE_INFO(tag, name, info)					  \
  struct __UNIQUE_ID(name) {}
#endif

It'll like config the Module information if module has been defined.

insmod

It's a program with following steps

  1. Call init_module() to tell kernel that a module is try to be load in the kernel and transfer the control to the kernel.
  2. Run sys_init_module(), which verifies if the user who trying to load the module is allowed or not. If allowed do step3.
  3. Call load_module function, which assigns temporary memory and duplicate theelf module from user space to kernel using copy_from_user(). Then check if the ELF file is proper or not. Copy users arguments to the kernel. Update the state of module to MODULE_STATE_COMING. Then returns a reference to the kernel module!
  4. The reference returned will be added to a doubly linked list for modules loaded.
  5. Module stat update to MODULE_STATE_LIVE.

當我們透過 insmod 去載入一個核心模組時,為何 module_init 所設定的函式得以執行呢?Linux 核心做了什麼事呢?

Covered in last question.
need to paste source code(todo).

試著執行 $ readelf -a fibdrv.ko, 觀察裡頭的資訊和原始程式碼及 modinfo 的關聯,搭配上述提問,解釋像 fibdrv.ko 這樣的 ELF 執行檔案是如何「植入」到 Linux 核心

這個 fibdrv 名稱取自 Fibonacci driver 的簡稱,儘管在這裡顯然是為了展示和教學用途而存在,但針對若干關鍵的應用場景,特別去撰寫 Linux 核心模組,仍有其意義,請找出 Linux 核心的案例並解讀。提示: 可參閱 Random numbers from CPU execution time jitter

查閱 ktime 相關的 API,並找出使用案例 (需要有核心模組和簡化的程式碼來解說)

In my fibdrv.c:

static unsigned long long fib_sequence(long long k)
{
    ktime_t t = ktime_get();
    /* FIXME: use clz/ctz and fast algorithms to speed up */
    unsigned long long f[k + 2];

    f[0] = 0;
    f[1] = 1;

    for (int i = 2; i <= k; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
    runtime = ktime_sub(ktime_get(), t);
    printk("iteration %llu runtime = %lldns\n", k, runtime);
    return f[k];
}

Use my own code as reference!
The first variable t store the starting time of the calculation.
Then after the calculation, use ktime_sub to get the differnce of the ending time and the starting time, whic can be represent as runtime!

clock_gettime 和 High Resolution Timers (HRT) 的關聯為何?請參閱 POSIX 文件並搭配程式碼解說

In the manpage of clock_gettime, we find clock_getres():

The function clock_getres() finds the resolution (precision) of the
       specified clock clk_id, and, if res is non-NULL, stores it in the
       struct timespec pointed to by res.  The resolution of clocks depends
       on the implementation and cannot be configured by a particular
       process.  If the time value pointed to by the argument tp of
       clock_settime() is not a multiple of res, then it is truncated to a
       multiple of res.

The word Resolution is to describe the precision of clock.
I wrote a simple program to get resolution of CLOCK_MONOTONIC

#include <time.h>
#include <stdio.h>

int main()
{
  struct timespec t;
  clock_getres(CLOCK_MONOTONIC, &t);
  printf("resolution: %ld\n", t.tv_nsec);
  return 0;
}
resolution: 1000#The unit of the time is nano sec.

I found the rationale in linux.org

Currently, timers in Linux are only supported at a resolution of 1 jiffy. The length of a jiffy is dependent on the value of HZ in the Linux kernel, and is 1 millisecond on i386 and some other platforms, and 10 milliseconds on most embedded platforms.

Higher resolution timers are needed to allow the system to wake up and process data at more accurate intervals.

fibdrv 如何透過 Linux Virtual File System 介面,讓計算出來的 Fibonacci 數列得以讓 userspace (使用者層級) 程式 (本例就是 client.c 程式) 得以存取呢?解釋原理,並撰寫或找出相似的 Linux 核心模組範例

注意到 fibdrv.c 存在著 DEFINE_MUTEX, mutex_trylock, mutex_init, mutex_unlock, mutex_destroy 等字樣,什麼場景中會需要呢?撰寫多執行緒的 userspace 程式來測試,觀察 Linux 核心模組若沒用到 mutex,到底會發生什麼問題

Mutex lock here is for protection of critical section!

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
void thread1(void)
{
    for(int i=0;i<5;i++)
        printf("This is a pthread1.\n");
}
void thread2(void)
{
    for(int i=0;i<5;i++)
        printf("This is a pthread2.\n");
}
int main(void)
{
    pthread_t t1, t2;
    pthread_create(&t1,NULL, (void *) thread1,NULL);
    pthread_create(&t2,NULL, (void *) thread2,NULL);
    for(int i=0;i<5;i++)
        printf("This is the main process.\n");
    pthread_join(t1,NULL);
    pthread_join(t2,NULL);
    return (0);
}

Expected outcome:


This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.
This is the main process.
This is the main process.
This is the main process.
This is the main process.

What I got:

This is the main process.
This is the main process.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is a pthread1.
This is the main process.
This is the main process.
This is a pthread1.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is a pthread2.
This is the main process.

許多現代處理器提供了 clz / ctz 一類的指令,你知道如何透過演算法的調整,去加速 費氏數列 運算嗎?請列出關鍵程式碼並解說

Original Fibdrv time testing(100 Repeat)

ktime_t vs get_time

ktime_t

dynamic programing(100 repeat)

with clz cts(todo)

tags: Cprogramming LinuxKernel
Select a repo