Wednesday, April 17, 2013

working of the fuction atomic_add_return

Atomic instructions are useful for executing instructions with out interrupt. Theory of the same is given in the post. Let us look into the Linux kernel, and see how atomic functions are implemented in the kernel. The atomic variables are declared as type atomic_t which is nothing but a structure defined in "include/Linux/types.h" as given below. Atomic structure :



File: include/Linux/types.h The value of the atomic variable is updated in the counter member of the structure. Atomic functions are written in different ways for different architectures. In this post We will be looking at atomic functions for x86 architecture. One of the atomic functions defined in atomic.h is atomic_add_return. The function is defined as follows.



The first line "#ifdef CONFIG_M386" is to check which CPU is the kernel being executed on. This is because in modern x86 CPU there are special instructions available that can be used for atomic operations.

If the architecture is 386, then we check if the instruction xadd is available in the CPU. If xadd is not available then we have to implement the atomic operation manually and we ump to the label no_xadd.

If xadd instruction is available or if the CPU is a modern 486 or above CPU, which always has the xadd instruction, then we make use of the instruction and pass the numbers for addition to xadd. Note that the first argument is the atomic number and the second is the number to be added to the atomic number.

If the system has i486 processor it will be defined in file: include/generated/autoconf.h as

The function xadd is implemented in the file arch/x86/include/asm/cmpxchg.h



From the comment above we note that xadd adds the second argument to the first argument and returns the previous value of the first argument. But note that the value of the first argument is updated to the new value.

xadd has been #defined to __xadd, which in turn has been #defined to __xchg_op. To the function __xcgh_op we pass the two numbers to be added, the instruction "xadd" and the keyword lock to signify that the instruction has to be executed in atomic mode.

The __xchg_op is implemented in the same file as



The four arguments passed __xcgh_op are

ptr: Pointer to the first argument, for xadd this the atomic variable which needs to be updated. arg: The second argument and for xadd the value to be added to the atomic variable op: The instruction to be executed, in this case "xadd" lock: To signify that the instruction is to be executed atomically.

The four case statements implement the addition for four different sizes of data. Let us take the first case of addition of single byte.



The above code implements the instruction using "asm" feature of gcc.

asm volatile: Instructs gcc not to do any optimizations to the code that follows.

lock: keyword to make the instruction execute atomically

op: In this case the "op", the assembly instruction, will be equal to xadd

b %b0, %1: b signifies argument is byte sized and %0,%1 are the arguments to the instruction.

"+q" (__ret), "+m" (*(ptr)): Being the first set of variables after the ":" these are the output variables.

"+" signifies the variable is going to read as well as written

q signifies the value is going to be stored in a register

__ret: Is the first argument to the instructions

m: signifies the value will be stored in memory

*(ptr): Is the second argument to instruction.

There are no input arguments thus there are no arguments in the second set of : : .

The last set of arguments are clobbers which are.

memory: The instruction write to some memory and the values in registers should not be cached by gcc

cc: The instruction affects the condition codes.

The working of xadd in i486 is as below.



To understand how the asm implementation of xadd is working we can use the followin example code.



compile it using gcc and execute it.



We can see that the value of i has become equal to "11" which was the value of j and the value of j has become equal to 21 which is the addition of i and j.

Applying the same logic to the kernel code above we can see that the value of __ret will become equal to the value of *ptr, which is the atomic variable, and the value of *ptr will become the sum of *ptr and __ret.

__xchg_op at the end returns __ret which is the value of the *ptr before addition.

Thus in the function atomic_add_return the statement



Increments the value of atomic variable by "i" and returns, "i" + "value of atomic variable before increment", which is nothing but the new value of the atomic variable.

In case the processor does not have an xadd instruction then the following code gets executed.



In the absence of support for atomic instructions in the processor, we have to manually disable the interrupts to make the instruction execute atomically. raw_local_irq_save(flags) : Disabling all interrupts
__i = atomic_read(v) : Atomically read the value of the variable and assign it to __i.
atomic_set(v, i + __i): Set the value of atomic variable,v, to sum of __i ,i.
once the value of atomic variable is updated we can enable the interrupts.
raw_local_irq_restore(flags);

Then return the sum of i,__i which is same as the new value of the atomic variable.

This we can see that atomic_add_return is able to perform the addition atomically using either xadd instruction of the processor or by disabling the interrupts manually.


0 comments:

Post a Comment