2022q1 Homework3 (fibdrv)
contributed by < oucs638
>
Assignment
oucs638/fibdrv
Development Environment
Compiler
Hardware
Linux kernel version
Install linux-headers
package.
Confirm user identity
Install tools
- Isolate a CPU from the kernel scheduler.
- Check whether the CPU was successfully isolated.
- Restrain address space layout randomization (ASLR)
- Create a shell script named
performance.sh
to set scaling_governor
as performance
.
- For Intel processors, turn off turbo mode.
Use class clz/ctz
instructions to improve Fibonacci number operations.
- Definition of Fibonacci number:
- Fibonacci number can be expressed as:
- Implement in C code:
- Assuming
n = 6
, the result of the program executing the function calls are as follows:
- Assuming
n = 6
, the result of the program executing the function calls are as follows:
- The Fast Doubling method can significantly reduce thr function calls required for program execution.
- Because computers represent numbers in binary, we can start from MSB to determine which operation to perform.
- Find
0
: Calculate and .
- Find
1
: Calculate and first, then calculate .
- But the actual number would not have lead 0s, so we can use class
ctz
instructions to count how many lead 0s and skip them.
Development Progress Records
- Observe the resulting
fibdrv.ko
module.
- Observe the behavior of the
fibdrv.ko
after the linux kernel is mounted.
Calculate the Fibonacci number after the 93rd item (inclusive)
- Refer to assignment, attempt to introduce big number that operate on string-number.
- Use Small/Short String Optimization.
- Refer to the example code provided in the assignment.
- The example code only use string-number addition to calculate the Fibonacci number.
- Expect to add a string-number subtraction and multiplication based on the addition-related code of the example code.
- With string-number substraction and multiplication, fast doubling can be intoduced to calculate Fibonacci numbers.
- But in this part, the Fibonacci number will be calculated by addtion first, and fast doubling will be introduced in the later part.
- Because C99 variable-length array(VLA) is not allowed in Linux kernel, so I use
kmalloc
to allocate memory space for the array dynamically.
- After calculate the Fibonacci number, the allocated memory space should be freed.
- String-number addition will reverse the string first, then add digit one by one from the least significant digit to the most significant digit.
Calculating Fibonacci Numbers by Fast Doubling (big number)
- I found it challenging to overcome positive-negtive sign problem issues when implementing "fasting doubling" with string numbers.
- It needs a lot of reallocating memory space to implement big-number operations with string number.
- Refer to eecheng87, rebuilt the big number operation.
- Preset a space large enough for Fibonacci number value.
- As previous part, the Fibonacci number can be represented as:
- Expressed as functions:
- Assume:
- Because computers represent numbers in binary, we can start from MSB to determine which operation to perform.
- Find
1
: next is odd.
- Find
0
: next is even.
- But the actual number would not have lead 0s, so we can use class
ctz
instructions to count how many lead 0s and skip them.
- Use
__builtin_clzll(k)
for typeof(k) = unsigned long long
Analyze
- Use big number.

- Use builtin
int128
.

- Found that if used builtin
int128
, .