Crypto performance challenge

Crypto operations optimisation challenge

In this challenge, you will have a complete ready-to-use kernel module doing cryptographic operations. Your aim is to maximise the computations done in 60 seconds whilst managing the thermal budget of the SoC.

This guide will start with the presentation of some control and monitoring features (usually) present on the board, then detail the structure of the kernel module, before giving you a checklist of strategies you can try to optimise your regulation.

SoC and frequency management

The main SoC on the board is a Quad-core 32-bit Qualcomm Krait 400 CPU to can go up to 2.26GHz. Usually, if the kernel has been compiled with CONFIG_CPU_FREQ=y, we have some information on the CPU frequency exposed in /sys/devices/system/cpu/cpu*/cpufreq/, where cpu* is each of the cores inside the CPU. Among other things, we can find the governor settings, which manages the dynamic frequency scaling (DVFS) of the CPU, based on the load, temperature, voltage, etc. Similarly, if the kernel was compiled with CONFIG_HOTPLUG_CPU=y, an interface is exposed in the same cpu* folder to enable/disable individual cores, allowing us to manage the thermal load and power management.

Both options are loaded in the board kernel. Yet, neither interfaces are available. At the moment, it is yet unclear whether it's a Linux implementation quirk or a Qualcom SoC feature.

You will thus need to find other avenues to manage the board thermal budget.

Temperature monitoring

Several temperature sensors are embedded in the board and are exposed through thermal zones.

They can be checked from userspace like so:

citro@board:~$ for i in /sys/class/thermal/thermal_zone*; do echo "$i: $(cat $i/type)"; done
/sys/class/thermal/thermal_zone0: pm8841-thermal
/sys/class/thermal/thermal_zone1: q6-dsp-thermal
/sys/class/thermal/thermal_zone10: gpu-bottom-thermal
/sys/class/thermal/thermal_zone11: pm8941-thermal
/sys/class/thermal/thermal_zone2: modemtx-thermal
/sys/class/thermal/thermal_zone3: video-thermal
/sys/class/thermal/thermal_zone4: wlan-thermal
/sys/class/thermal/thermal_zone5: cpu0-thermal
/sys/class/thermal/thermal_zone6: cpu1-thermal
/sys/class/thermal/thermal_zone7: cpu2-thermal
/sys/class/thermal/thermal_zone8: cpu3-thermal
/sys/class/thermal/thermal_zone9: gpu-top-thermal

The main zones that will be of interest to us thus are 5 through 8, the cpu*-thermal zones. For example, we can keep an eye on cpu1 by calling watch -n 0.1 "cat /sys/class/thermal/thermal_zone6/temp"

How the kernel module code is structured

The following section explains how the different parts of the LKM work. It is essential you understand how it all interface, but you don't need to implement everything by hand. The complete module and Makefile are available in the repository.

The module works with five threads: one control thread and four worker threads.

• The control thread job is to regulate the activity of the worker threads in order to respect the thermal budget.
• The worker thread do crypto operations with no other purpose than CPU loading. It's also pinned to one of the four SoC cores.
• In the background, a timer triggers a sampling function that logs the temperature on each core every 100ms.
• A procfs entry is created at /proc/crypto_challenge/stats exposing some info on the challenge.

Structures

Each worker has its own structure, essentially to set a unique ID cpu_id to the thread, the required task info and all the data for crypto operations.

struct worker {
    struct task_struct *task;
    struct crypto_skcipher *tfm;
    struct skcipher_request *req;

    u8 *buf;
    u8 key[KEY_SIZE];
    u8 iv[IV_SIZE];

    int cpu_id;
};

A global structure holds all the information about the benchmark: worker threads, thermal zones to monitor, operations count, score, etc. As it's a global variable, its content is shared across threads. This means for example that the run and stop booleans can be controlled by the control thread and checked by all worker threads.

struct challenge_ctx {
    struct worker workers[MAX_CORES];
    struct thermal_zone_device *tz[MAX_CORES];

    struct sample samples[MAX_SAMPLES];
    int sample_count;

    atomic64_t ops;

    int worker_count;
    bool run;
    bool stop;

    int duty_on_ms;
    int duty_off_ms;

    unsigned long start_jiffies;

    struct timer_list sample_timer;

    u64 final_score;
    int invalid;
};

static struct challenge_ctx ctx;

Module __init and __exit

mod_init does the following:

• Set on and off delays for the default (and crude) regulation
• Set the thermal zones to monitor
• Create the procfs entry
• Call the start_worker procedure to launch the worker threads
• Create and run the control thread

mod_exit when removing the module:

• Stop the control thread
• Stop the worker threads
• Remove the procfs entry It is important to stop the threads in one single place, here when removing the module from the kernel.

Managing threads

• To create a thread, call kthread_create(thread_function, arguments, "name", id).
• To start a created thread, call wake_up_process(task_struct*), with argument the task to wake up.
• To create and run a thread in one go, call task_struct* kthread_run(thread_function, NULL, "thread_name"). It will start the thread in the function thread_function and return a task_struct pointer that you should save.
• To stop a thread, call kthread_stop(task_struct*). It must only be done on an existing thread, thus always check that it's not dead yet.
• To bind a thread to a specific CPU core, use kthread_bind(task_struct*, cpu_id). This must be done before the thread is running.

Inside a thread, we often want to do some work until we kill the thread from somewhere else. In that case, we can use

static int thread_function(void *arg) {
    while(!kthread_should_stop()) {
        /* Do stuff */
    }
    /* Clean-up or whatever */
    return 0;
}

kthread_should_stop() will return true when we call kthread_stop() on this thread.

If we want the thread to do nothing for a while, for example following a condition check, we can send it to sleep:

set_current_state(TASK_INTERRUPTIBLE);
schedule_timeout_interruptible(msecs_to_jiffies(10));
continue;

Control thread

The control thread main function is control_fn. It begins by starting the sampling operation and timer: start_sampling();

In its main loop, it checks if the benchmark stopwatch is done: if (time_after(jiffies, ctx.start_jiffies + BENCH_DURATION_SEC * HZ)). If it is, it stops the sampling, computes the final score and prints it to the kernel log. Notice that we read the total operations using an atomic operation to avoid race conditions on the worker threads that might still be updating it: atomic64_read(&ctx.ops).

During the benchmark time, we regulate the activity of the worker threads rather crudely by default: some time on, then some time off.

ctx.run = true;
msleep(ctx.duty_on_ms);

ctx.run = false;
msleep(ctx.duty_off_ms);

It works by changing a variable in the global context that is checked by the worker threads to know if they can do crypto operations or not.

Tip

This is what you will need to adjust.

Worker threads

Workers are initiated in start_worker(), filling the worker structure.

• Allocate memory to the buffer
• Set the key and IV
• Select the cryptographic algorithm
• Create the worker thread
• Bind the thread to a CPU core
• Start the thread using wake_up_process()

During their life, workers execute worker_fn().

• It should not stop until another thread/process calls kthread_stop() on it.
• If the global flag ctx.run is set to false by the manager thread, the worker is set to sleep.
• Otherwise we do a crypto operation and atomically increment the global operations counter ctx.ops.

When we want to kill the worker threads with stop_worker(), there is so clean-up to do:

• Stop the thread
• Free the crypto structures and buffer

Crypto operations

In start_worker(), we select the AES cipher in CBC mode of operation. By setting a 16-byte key, we also select the block size to be the same size (128-bit). The IV is the initialisation vector used by the cryptographic algorithm. Note that we reuse the same IV for multiple encryptions. This is highly cryptographically insecure, but fine for benchmarking.

In do_crypto(), we see the three steps of the encryption process:

1. Initialisation of the buffer, 4096 bytes in this case.
2. Set the encryption request up. We see here that the IV can easily be changed for each operation, which we do not.
3. Actually encrypt the buffer.

Procfs exposure

When created in mod_init(), the procfs entry is linked with a proc_ops structure to set system call callback (akin to a file_operations structure used with character devices).

In that structure, we have but one field set:

static const struct proc_ops stats_fops = {
    .proc_read = stats_read,
};

In that stats_read() callback, we do a simple_read_from_buffer(), a shortcut function compared to what we did with raw character devices.

Whenever we to a read operation on the procfs entry, for example doing cat /proc/crypto_challenge/stats, we execute this callback and we receive in return a string with information on the benchmark.

Sampling

Sampling starts with a timer setup:

static void start_sampling(void)
{
    ctx.sample_count = 0;

    timer_setup(&ctx.sample_timer, sample_fn, 0);
    mod_timer(&ctx.sample_timer, jiffies + msecs_to_jiffies(SAMPLE_PERIOD_MS));
}

The timer is first setup with a callback function sample_fn, then we modify its duration with mod_timer. If the timer is offline, it's woken up and the callback executed when it expires. Jiffies are kind of the heartbeat of the system.

The sample function proper sample_fn logs the amount of operations completed using an atomic operation (atomic64_read) and the temperature of each core.

If any temperature reading is above the thermal limit, we set the invalid field of the context to 1, nullifying the score.

Score

The score is computed as follows:

( operations / benchmark_time ) * 1E5 / ( 1 + sum_i((temp_i - temp_0)**2) / 1E5 )

With temp_0 the temperature when starting the benchmark. The temperature delta is computed on each score. If the delta is negative, it saturates on zero. This method means that larger temperature deltas are more heavily penalised, and more operations during the benchmark is rewarded.

If the invalid field of the context is set, the score is automatically equal to zero.

Tasks

• Add the maximum temperature recorded in the stats file, so that you can better evaluate how close you got from the threshold.
• The benchmark should be stopped if we reach the threshold temperature on any core.
• Get the highest possible score.
  • You can't change the scoring function.
  • You can't change the crypto operation, it has to be AES-CBC-128bit.

Strategies

• Global load regulation based on temperature: when the maximum temperature gets too high, make the running threads sleep.
• Local load regulation: make threads sleep based on the temperature of the core they are running on.
• Change the duty cycle of the computation load.
• Anticipate thermal inertia.
• CPU affinity
• Find a way to disable some cores
• Use Neon instructions

Limitations and unknown at the moment

• Why don't we have a cpufreq subfolder in /sys/devices/system/cpu/cpu*/, even though the parameter CONFIG_CPU_FREQ=y is baked into the kernel? Without it, we don't have control over the CPU governor.
• Why can't we manage which CPU is online, even though CONFIG_HOTPLUG_CPU=y is active in the kernel? It should be in /sys/devices/system/cpu/cpu*/online, allowing us to disable some core, lowering the power dissipation, potentially increasing the frequency of the remaining cores.
• The read operation on a procfs interface is not atomic, there could be race conditions on the information we see. Not a significant problem at this level, as it's mainly for debug and coarse monitoring purposes.
• Is there a way to change the frequency management policy: /sys/module/cpufreq/parameters/default_governor? The default CPU governor is conservative:

citro@board:~/LKM/vault$ cat /sys/module/cpufreq/parameters/default_governor 
conservative

• To monitor CPU frequency, first enable its tracing:

echo 1 | sudo tee /sys/kernel/tracing/events/power/cpu_frequency/enable

But then the even of cpu changing does not seem to fire.

Resources and references

• https://www.thomas-krenn.com/en/wiki/Setting_of_CPU_Governor_under_Linux
• https://xdaforums.com/t/ref-guide-sabers-guide-on-cpu-governors-i-o-schedulers-and-more.3048957/
• Kthread API
• Thermal zone Sysfs API

TODO

• Change the scoring system to better favour a high operation count.