Search     or:     and:
 LINUX 
 Language 
 Kernel 
 Package 
 Book 
 Test 
 OS 
 Forum 
iakovlev.org

Для чего нужен System.map ?

"System.map" - файл,включающий символические имена и адреса из бинарного ядра-vmlinux. Он используется для дебага. При появлении в ядре сообщений типа "oops" утилита ksymoops может быть использована для их декодирования в нормальный читабельный вид. В ядре 2.5 использовался встроенный декодер kksymoops,которому не нужен был System.map.

Можно вычислить сообщения в System.map по дате. Команда ps l использует System.map для определения WCHAN. Сам System.map может быть размещен как в /boot/System.map,так и в /usr/src/linux/System.map.


likely() и unlikely()

Для чего они нужны ?

В коде ядра часто можно встретить вызовы likely() и unlikely(), типа :

bvl = bvec_alloc(gfp_mask, nr_iovecs, &idx);
 if (unlikely(!bvl)) {
   mempool_free(bio, bio_pool);
   bio = NULL;
   goto out;
 }
 

Фактически,это наводка компилятору для оптимизации. Определение этих макросов можно найти в include/linux/compiler.h :

#define likely(x)       __builtin_expect(!!(x), 1)
 #define unlikely(x)     __builtin_expect(!!(x), 0)
 

В документации так описана роль __builtin_expect() :

 -- Built-in Function: long __builtin_expect (long EXP, long C)
      You may use `__builtin_expect' to provide the compiler with branch
      prediction information.  In general, you should prefer to use
      actual profile feedback for this (`-fprofile-arcs'), as
      programmers are notoriously bad at predicting how their programs
      actually perform.  However, there are applications in which this
      data is hard to collect.
 
      The return value is the value of EXP, which should be an integral
      expression.  The value of C must be a compile-time constant.  The
      semantics of the built-in are that it is expected that EXP == C.
      For example:
 
           if (__builtin_expect (x, 0))
             foo ();
 
      would indicate that we do not expect to call `foo', since we
      expect `x' to be zero.  Since you are limited to integral
      expressions for EXP, you should use constructions such as
 
           if (__builtin_expect (ptr != NULL, 1))
             error ();
 
      when testing pointer or floating-point values.
 

Что это за оптимизация такая ?

Оптимизация проходит на уровне генерации ассемблерного кода. Например,будут удалены все инструкции типа jmp.

Давайте откомпилируем следующий кусок C-кода пользовательской программы с опцией компилятора gcc -O2 :

#define likely(x)    __builtin_expect(!!(x), 1)
 #define unlikely(x)  __builtin_expect(!!(x), 0)
 
 int main(char *argv[], int argc)
 {
    int a;
 
    /* Get the value from somewhere GCC can't optimize */
    a = atoi (argv[1]);
 
    if (unlikely (a == 2))
       a++;
    else
       a--;
 
    printf ("%d\n", a);
 
    return 0;
 }
 

Теперь сделаем дизассемблинг с помощью objdump -S (комменты мои) :

080483b0 <main>:
  // Prologue
  80483b0:       55                      push   %ebp
  80483b1:       89 e5                   mov    %esp,%ebp
  80483b3:       50                      push   %eax
  80483b4:       50                      push   %eax
  80483b5:       83 e4 f0                and    $0xfffffff0,%esp
  //             Call atoi()
  80483b8:       8b 45 08                mov    0x8(%ebp),%eax
  80483bb:       83 ec 1c                sub    $0x1c,%esp
  80483be:       8b 48 04                mov    0x4(%eax),%ecx
  80483c1:       51                      push   %ecx
  80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
  80483c7:       83 c4 10                add    $0x10,%esp
  //             Test the value
  80483ca:       83 f8 02                cmp    $0x2,%eax
  //             --------------------------------------------------------
  //             If 'a' equal to 2 (which is unlikely), then jump,
  //             otherwise continue directly, without jump, so that it
  //             doesn't flush the pipeline.
  //             --------------------------------------------------------
  80483cd:       74 12                   je     80483e1 <main+0x31>
  80483cf:       48                      dec    %eax
  //             Call printf
  80483d0:       52                      push   %edx
  80483d1:       52                      push   %edx
  80483d2:       50                      push   %eax
  80483d3:       68 c8 84 04 08          push   $0x80484c8
  80483d8:       e8 f7 fe ff ff          call   80482d4 <printf@plt>
  //             Return 0 and go out.
  80483dd:       31 c0                   xor    %eax,%eax
  80483df:       c9                      leave
  80483e0:       c3                      ret
 

Теперь заменим unlikely() на likely(), откомпилируем по новой, и дизассемблируем опять :

080483b0 <main>:
  //             Prologue
  80483b0:       55                      push   %ebp
  80483b1:       89 e5                   mov    %esp,%ebp
  80483b3:       50                      push   %eax
  80483b4:       50                      push   %eax
  80483b5:       83 e4 f0                and    $0xfffffff0,%esp
  //             Call atoi()
  80483b8:       8b 45 08                mov    0x8(%ebp),%eax
  80483bb:       83 ec 1c                sub    $0x1c,%esp
  80483be:       8b 48 04                mov    0x4(%eax),%ecx
  80483c1:       51                      push   %ecx
  80483c2:       e8 1d ff ff ff          call   80482e4 <atoi@plt>
  80483c7:       83 c4 10                add    $0x10,%esp
  //             --------------------------------------------------
  //             If 'a' equal 2 (which is likely), we will continue
  //             without branching, so without flusing the pipeline. The
  //             jump only occurs when a != 2, which is unlikely.
  //             ---------------------------------------------------
  80483ca:       83 f8 02                cmp    $0x2,%eax
  80483cd:       75 13                   jne    80483e2 <main+0x32>
  //             Here the a++ incrementation has been optimized by gcc
  80483cf:       b0 03                   mov    $0x3,%al
  //             Call printf()
  80483d1:       52                      push   %edx
  80483d2:       52                      push   %edx
  80483d3:       50                      push   %eax
  80483d4:       68 c8 84 04 08          push   $0x80484c8
  80483d9:       e8 f6 fe ff ff          call   80482d4 <printf@plt>
  //             Return 0 and go out.
  80483de:       31 c0                   xor    %eax,%eax
  80483e0:       c9                      leave
  80483e1:       c3                      ret
 


Preemption

Что такое preemption ?

preemption - способность операционной системы выгрузить или остановить текущую задачу в пользу другой более приоритетной задачи. При этом возможны ограничения со стороны I/O

Linux ?

В линуксе любая пользовательская программа вытесняема: ядро обязательно остановит и переключит ее на другую задачу, используя clock tick. Никакой бесконечный цикл в программе пользователя не способен заблокировать ресурсы процессора полностью.

До версии 2.6 ядро не было preemtible, и это вызывало определенные проблемы при масштабировании. kernel preemption появилось в 2.6 kernels. В опциях конфига теперь появилось CONFIG_PREEMPT. Если CONFIG_PREEMPT enabled, ядро может тормозить все что угодно. Если CONFIG_PREEMPT disabled, возвращается поведение версии 2.4.

Spinlocks и preemption

В версии 2.4 kernels, для одно-процессорных машин, спинлоки были запрещены. Защита от совместного доступа была нужна для мульти-процессорных систем. В версии 2.6, спинлоки разрешены даже для одно-процессорной машины.

Код,который работает под 2.4,может потерпеть фиаско в 2.6, если проблемы совместного доступа к ресурсам решены некорректно.


SyscallTrace

Как перехватить системный вызов?

Перехват системного вызова-первое,что обычно делают начинающие программисты ядра, своеобразная проба пера. Здесь важно различать разницу между двумя ветками:2.4 и 2.6.

2.4 kernel

Перехват означает полную замену системного вызова ядра на вашу собственную функцию. Как правило,это достигается с помощью Loadable Kernel Module (LKM),

Ключ здесь лежит в модификации структуры ядра под названием sys_call_table. Эта таблица включает в себя полный набор системных вызовов. Каждый вызов идентифицируется с помощью целочисленной константы. Эти константы фактически являются индексами в таблице sys_call_table.

Когда пользовательской программе нужен системный вызов, прерывание 0x80 загружает в регистр EAX system call number. Далее хэндлер внутри ядра использует содержимое этого регистра в качестве индекса sys_call_table и вызывает нужную функцию из нее.

Если мы изменим адрес в sys_call_table на индекс,соответствующий номеру системного вызова fork, мы сможем заменить ее на свою функциюю из собственного LKM. В следующий раз,когда произойдет вызов fork, будет вызвана наша функция. При этом можно выводить системное сообщение при каждом вызове fork.

В LKM нужно сделать следующее:

  • Изменить sys_call_table

  • Создать в модуле необходимую функцию
  • Еще раз изменить sys_call_table при выгрузке модуля и возврата оригинального системного вызова

Следующие файлы представляют интерес:

  • /include/linux/syscalls.h Сигнатура системных вызовов
  • /include/asm-um/unistd.h Хидеры для system calls
  • /include/asm-um/arch/unistd.h Определения констант __NR ,соответствующим внутренним номерам системных вызовов

LKM для 2.4 с перехватом системного вызова

В этом разделе показан код для 2.4 LKM , способного перехватить fork system call. Работать это будет только на 2.4 kernels. Подробнее об этом можно прочитать в части 8 Linux Kernel Module Programmer's Guide (Salzman, Burian, Pomerantz, 2005/05/26 version 2.6.1, http://www.tldp.org/LDP/lkmpg/2.6/lkmpg.pdf).

// base modules inclusions 
 #include <linux/init.h>
 #include <linux/module.h>
 
 // for getpid() 
 #include <linux/unistd.h>
 #include <asm/arch/unistd.h>
 
 
 MODULE_LICENSE("GPL"); 
 
 
 extern void* sys_call_table[];
 

Таблица sys_call_table экспортируется в ядро.Нам нужен собственный массив указателей на эти функции.

int (*original_fork)(struct pt_regs);
 // we define original_fork as a pointer on function w/ the same prototype 
 // as the fork system call. It is meant to store the address of the original 
 // fork function in the kernel while we replace it w/ our own 
 
 int edu_fork(struct pt_regs regs)
 {
   pid_t pid;
   
   // loging the syscall
   printk(KERN_ALERT "[edu]   fork syscall intercepted from %d\n", current->pid); 
 

Почему бы не использовать getpid()? current - глобальный указатель ядра,ссылаемый на структуру task_struct текущего процесса. Из этой структуры мы используем поле pid .

  // making the call to the original fork syscall
   pid = (*original_fork)(regs);
     
   return pid;
 }
 

Наша функция делает враппер для форка. Мы делаем вызов оригинального системного вызова, но перед ним или после него мы можем добавить свой код.

system call-это один из самых критических по скорости вызовов в ядре.

static int edu_init(void)
 {
   printk( KERN_ALERT "[edu]   Module successfully loaded\n"); 
   printk( KERN_ALERT "[edu]   Intercepting fork() syscall... "); 
 
   original_fork = sys_call_table[__NR_fork];
   sys_call_table[__NR_fork] = edu_fork;  
 

Здесь мы используем константу NR_fork для системного вызова.

  printk( KERN_ALERT "done/n"); 
   printk( KERN_ALERT "[edu]   Starting Loging system calls\n"); 
   return 0; 
 }
 
 static void edu_exit(void)
 {
   sys_call_table[__NR_fork] = original_fork;
   printk(KERN_ALERT "[edu]   Stopping loging system calls\n"); 
 }
 

Загрузка и выгрузка модуля:

module_init(edu_init); 
 module_exit(edu_exit); 
 

Ограничения: sys_execve

execve system call с нашим модулем работать не будет. Прототип sys_execve() :

asmlinkage int sys_execve(struct pt_regs regs)
 

Её аргумент - НЕ указатель! Попытка перехватить sys_execve не будет работать. Регистры процесса сохраняются в стеке. Код внутри sys_execve модифицирует этот стек.

Например,код,который модифицирует регистры- start_thread(),вызываемый внутри load_elf_binary().

Обойти эту проблему можно с помощью вызова do_execve() вместо sys_execve, который дублирует вызов sys_execve(). Но это тоже неправильно.

2.6 kernel

Включая 2.4, sys_call_table была экспортируемой таблицей. Это означает что любой LKM мог ссылаться на нее внутри своего кода. Начиная с 2.6, Linus Torvalds решил более не экспортировать эту таблицу. Была захлопнута дверь перед разного рода rootkits. Таблица sys_call_table стала менее доступна, и простейшие методы перехвата системных функций теперь не работают.

Для 2.6 kernel, вышеуказанный LKM работать не будет. Но тем не менее альтернатива остается.

  • Solution #1: kernel patching

Для этого нужно модифицировать ядро,пересобрать его и затем написать LKM. :)

  • Solution #2: hot patching technique

Подробнее о технике hot patching можно почитать тут:

There


Связаные списки

Как в ядре реализованы Linked Lists?

В старых версиях ядра управление такими структурами данных,как связные списки,хеш-таблицы, было прозрачнее. В последних версиях ядра появилось универсальное API для управления такими структурами. Понимание этого API поможет вам как в освоении самого ядра, так и в улучшении собственно навыков с-программирования.

Давайте попробуем рассмотреть linked list API с точки зрения "как это может пригодиться лично мне ?" (например в Loadable Kernel Module). Определим структуру данных,которая будет использована в связном списке:

struct mystruct { 
     int data ; 
 } ; 
 

Для того чтобы можно было линковать struct mystruct , добавим поле struct list_head :

struct mystruct { 
     int data ; 
     struct list_head mylist ; 
 } ; 
 

Обычно для реализации связного списка нужно добавить указатель на следующий элемент в списке. В ядре все немного по-другому,поскольку ядру нужна возможность для добавления-удаления элементов из списка.

Создадим экземпляр нашей структуры:

struct mystruct first ; 
 
 first.data = 10 ; 
 first.mylist = LIST_HEAD_INIT(first.mylist) ; 
 

Последняя строка вызывает макрос LIST_HEAD_INIT в /include/linux/list.h:

 31 
  32 #define LIST_HEAD_INIT(name) { &(name), &(name) }
  33 
 

Полю mylist назначается указатель на список из одного элемента.

Создаем 2-ю переменную и инициализируем ее:

struct mystruct second ; 
 
 second.data = 20 ; 
 INIT_LIST_HEAD( & second.mylist ) ; 
 

На этот раз мы используем другой макрос для инициализации списка:

 37 static inline void INIT_LIST_HEAD(struct list_head *list)
  38 {
  39         list->next = list;
  40         list->prev = list;
  41 }
  42 
 

Нам нужна переменная для обозначения начала списка, проинициализируя ее как пустой связный список,и потом добавиви в него 2 элемента:

LIST_HEAD(mylinkedlist) ;
 

Этот макрос декларирует переменную типа struct list_head и инициализирует ее:

 34 #define LIST_HEAD(name) \
  35         struct list_head name = LIST_HEAD_INIT(name)
  36 
 

Добавляем 2 элемента в список:

list_add ( &first , &mylinkedlist ) ; 
 list_add ( &second , &mylinkedlist ) ; 
 

list_add - макрос :

 59 /**
  60  * list_add - add a new entry
  61  * @new: new entry to be added
  62  * @head: list head to add it after
  63  *
  64  * Insert a new entry after the specified head.
  65  * This is good for implementing stacks.
  66  */
  67 static inline void list_add(struct list_head *new, struct list_head *head)
  68 {
  69         __list_add(new, head, head->next);
  70 }
  71 
 

В нем лежит вложенный макрос list_add:

 43 /*
  44  * Insert a new entry between two known consecutive entries.
  45  *
  46  * This is only for internal list manipulation where we know
  47  * the prev/next entries already!
  48  */
  49 static inline void __list_add(struct list_head *new,
  50                               struct list_head *prev,
  51                               struct list_head *next)
  52 {
  53         next->prev = new;
  54         new->next = next;
  55         new->prev = prev;
  56         prev->next = new;
  57 }
  58 
 

У нас есть handle на двойной связаный список (mylinkedlist), в котором 2 элемента. kernel linked list API реализует несколько макросов для манипуляций с ним.

328 /**
 329  * list_for_each        -       iterate over a list
 330  * @pos:        the &struct list_head to use as a loop counter.
 331  * @head:       the head for your list.
 332  */
 333 #define list_for_each(pos, head) \
 334         for (pos = (head)->next; prefetch(pos->next), pos != (head); \
 335                 pos = pos->next)
 

Внутри этого макроса лежит цикл. Ему нужны 2 аргумента-указатель на голову списка - (head) и указатель на элемент,который подвергвется апдэйту - pos.

Выведем на консоль элементы нашего списка:

struct head_list* position ; 
 list_for_each ( position , & mylinkedlist )  
     { 
          printk ("surfing the linked list next = %p and prev = %p\n" , 
              position->next, 
              position->prev ); 
     } 
 

Имея указатель на структуру list_head которая является частью структуры mystruct , нам нужно вернуть адрес следующего элемента. Макрос list_entry делает это:

319 /**
 320  * list_entry - get the struct for this entry
 321  * @ptr:        the &struct list_head pointer.
 322  * @type:       the type of the struct this is embedded in.
 323  * @member:     the name of the list_struct within the struct.
 324  */
 325 #define list_entry(ptr, type, member) \
 326         container_of(ptr, type, member)
 

container_of определен в /include/kernel/kernel.h :

275 /**
 276  * container_of - cast a member of a structure out to the containing structure
 277  * @ptr:        the pointer to the member.
 278  * @type:       the type of the container struct this is embedded in.
 279  * @member:     the name of the member within the struct.
 280  *
 281  */
 282 #define container_of(ptr, type, member) ({                      \
 283         const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
 284         (type *)( (char *)__mptr - offsetof(type,member) );})
 285 
 

У нас есть адрес структурыstruct list_head , которая находится внутри другой структуры (struct task_struct ). Первая строка макроса переводит 0 в указатель на тип структуры struct task_struct в нашем примере. Мы используем этот указатель для доступа в структуре, который соответствует list_head и получаеи его тип с помощью макроса typeof для декларации указателя mptr .

Следующим шагом нужно определить из адреса ptr ( mptr ) смещение для структуры list_head. Это делается с помощью макроса,определенного в /include/linux/stddef.h ;

17 #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
 

Этот макрос вычисляет адрес MEMBER в структуре TYPE. Для получения смещения, берем MEMBER нулевого указателя,переведенного в TYPE.

Мы можем написать цикл,который выводит на консоль содержание полей связного списка элементов:

struct head_list *position = NULL ; 
 struct mystruct  *datastructureptr  = NULL ;  
 list_for_each ( position , & mylinkedlist )  
     { 
          datastructureprt = list_entry ( position, struct mystruct , mylist );
          printk ("data  =  %d\n" , datastructureptr->data ); 
     } 
 

Можно упростить с помощью другого макроса:

369 /**
 370  * list_for_each_entry  -       iterate over list of given type
 371  * @pos:        the type * to use as a loop counter.
 372  * @head:       the head for your list.
 373  * @member:     the name of the list_struct within the struct.
 374  */
 375 #define list_for_each_entry(pos, head, member)                          \
 376         for (pos = list_entry((head)->next, typeof(*pos), member);      \
 377              prefetch(pos->member.next), &pos->member != (head);        \
 378              pos = list_entry(pos->member.next, typeof(*pos), member))
 379 
 

Наш пример:

struct mystruct  *datastructureptr = NULL ;  
 list_for_each_entry ( ptr , & mylinkedlist, )  
     { 
          list_entry ( item , struct mystruct , mylist );
          printk ("data  =  %d\n" , datastructureptr->data ); 
     } 
 

Другие классические структуры данных определены в include/linux/list.h


Why Writing Files From Kernel Is Bad

Почему сохранять файлы из ядра плохо ?

Причины

Этот вопрос задают частенько. Работа с файлами из ядра-плохая затея. Более того,использование любой функции типа sys_*() само по себе плохая идея.

Несколько причин:

  • Права на работу файла-это policy,а policy-это не прерогатива ядра.
  • Для работы с файловой системой необходим user context (current != NULL).
  • Ядро инициализирует для пользовательских процессов несколько filesystem namespaces. Каой из них нужен?
  • Ядро нельзя ставить в зависимость от конкретной файловой системы. Расположение файла находится под контролем policy и policy должно работать в userspace.


get current

NOTE: this FAQ answer applies to the 2.4 kernel. 2.6 with 4kB stacks works differently and this FAQ should be updated.

Как работает get_current()?

static inline struct task_struct * get_current(void)
 {
         struct task_struct *current;
         __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
         return current;
 }
 

get_current() - функция для получения доступа к структуре task_struct текущего процесса. Её часто можно видеть в ассемблерном обрамлении:

        __asm__(
 

Эта директива обязывает компилятор вставлять inline assembler код один-в-один.

        "andl %%esp,%0
 

Берется стековый указатель (register %esp),совершается операция AND и результат хранится в регистре.

Размер task_struct,равно как и task's kernel stack,равен 8KB. Чтобы вычислить tas_struct,нужно очистить13 бит от значения стекового указателя,поскольку task_struct находится в стеке.

        ; "
 

Точка с запятой служит для разделения ассемблерных выражений, равно как "\n".

        :"=r" (current)
 

Тут определяется результат вывода. r указывает на один из регистров основного типа,и результат вывода будет записан в него. 'current'-это наружная си-шная переменная.

        : "0" (~8191UL));
 

Указывает на то,что input переменная должна использовать тот же самый регистр, что и output. Константа '~8191UL' должна быть загружена в тот регистр перед вычислением, в который будет помещен резуьтат output value.


Do While(0)

Почему многие макосы в ядре используют do { ... } while(0)?

Несколько причин:

  • (from Dave Miller) Позволяет организовать логический блок для декларации локальных переменных.

  • (from Ben Collins) Позволяет использовать более комплексные макросы для условного кода.Рассмотрим пример:

    #define FOO(x) \
             printf("arg is %s\n", x); \
             do_something_useful(x);
     
    Пример его использования :
    if (blah == 2)
             FOO(blah);
     
    То же самое:
    if (blah == 2)
             printf("arg is %s\n", blah);
             do_something_useful(blah);;
     

    Условие работает только для printf(), и do_something_useful() в это условие уже не попадает. А используя блок типа do { ... } while(0), мы получаем:

    if (blah == 2)
             do {
                     printf("arg is %s\n", blah);
                     do_something_useful(blah);
             } while (0);
     
    То,что и хотели.
  • Рассмотрим макрос :

    #define exch(x,y) { int tmp; tmp=x; x=y; y=tmp; }
     

    Используем этот макрос в следующей конструкции:

    if (x > y)
             exch(x,y);          // Branch 1
     else  
             do_something();     // Branch 2
     

    Распишем подробно :

    if (x > y) {                // Single-branch if-statement!!!
             int tmp;            // The one and only branch consists
             tmp = x;            // of the block.
             x = y;
             y = tmp;
     }
     ;                           // empty statement
     else                        // ERROR!!! "parse error before else"
             do_something();
     

    Проблема в (;) после первого логического блока. Ее можно разрешить,если заключить первый логический блок в конструкцию do ... while(0):

    if (x > y)
             do {
                     int tmp;
                     tmp = x;
                     x = y;
                     y = tmp;
             } while(0);
     else
             do_something();
     

Оставьте свой комментарий !

Ваше имя:
Комментарий:
Оба поля являются обязательными

 Автор  Комментарий к данной статье
Ярослав
  Привет!

Очень полезная страничка, спасибо!

Заметил брокен-линки в разделе ссылок про хотпатчи ядра.
http:www.phrack.orgshow.php?p=58&a=7 надо заменить на http:www.phrack.orgissues.html?issue=58&id=7#article

http:kernelnewbies.orgSysCallTrack тоже битая ссылка (нету в той вики этого). КУда должна показывать - не знаю.
2007-10-28 07:21:14
Яковлев Се�
  Да , спасибо
Первая ссылка битая , я ее поменял на Вашу : http://www.phrack.org/issues.html?issue=58&id=7#article

Вторая тоже устарела - нонешний адрес такой : http://kernelnewbies.org/FAQ/SyscallTrace/
2007-10-28 10:49:37