Здесь я опишу то, что ядро предоставляет для любой подсистемы.
String.h
Поскольку ядро -- это автономная система, использование в ней
glibc запрещено, а поэтому все стандарные функции по работе со
строками написаеы, причем оптимизированы под конкретный камень.
strlen, memcpy, strncmp -- все это есть и работает так же как и
user-space аналоги. Интересно упомянуть об оптимизации под названием
alternative_input. Если одно и то же действие можно сделать
с разной скоростью разными инструкциями в зависимости от модели
процессора -- можно явно указать, какую инструкцию при каком
процессоре использовать. Основная и альтернативная инструкции
укладыватся друг за другом и на одну из них делается
jmp.
Одно время я видел эту оптимизацию во многих местах, но потом
ее много где поубирали.
Списки и хеш таблицы
Вся работа со списками написана в
include/linux/list.h.
Как они работают проще всего пояснить на примере. Итак, допустим
программист хочет подвязывать в список
my_list объекты
структуры
my_struct. Он делает следующее:
Код: Выделить всё
static struct list_head my_list = LIST_HEAD_INIT(&my_list);
этим самым объявляется голова списка и инициализируется. Структура
list_head состоит из двух указателей на саму себя --
next
и
prev, и
LIST_HEAD_INIT инициализирует эти указатели
на голову в знак того, что в списке нет элементов. Макрос
list_empty
как раз проверяет этот момент. Далее описывается структура:
Код: Выделить всё
struct my_struct {
... /* fields */
struct list_head list;
... /* fields */
};
Как видим, достаточно завести два указателя внутри структуры.
Добавление и удаление из списка выглядит оченть просто:
Код: Выделить всё
stryct my_struct *obj;
...
list_add(&obj->list, &my_list);
...
list_del(&obj->list);
Как видим для удаления из списка даже не надо знать из какого -- указатели
на
next и
prev сами указывают на те элементы, между которыми нужно
сомкнуть дырку. А теперь -- самое интересное -- как извлечь элемент из списка.
Код: Выделить всё
struct my_struct *obj;
struct list_head *lp;
...
obj = list_entry(lp, struct my_struct, list);
Макрос
list_entry устроен следующим образом. Вычисляется смещение поля
list в структуре
struct my_struct и это смещение вычитается из
указателя
lp. Вот вариант кода, как он выглядел в ранних версиях:
Код: Выделить всё
#define list_entry(lp, type, mem) \
(type *)(((char *)lp - &(((type *)0)->mem)))
Для удобства программиста так же есть макросы прохода по списку в разных
вариантах, склеивания списков и так далее, но все они построены на описанной
идее -- вычислять элемент из
struct list_head по смещению.
Про хеши два слова -- вместо
struct list_head есть структуры
hlist_head
и
hlist_entry. В первой сидит указатель на первый элемент, а во второй --
указатель на следующий и указатель на указатель, указывающий на себя.
Хеш организуется следующим образом -- заводится массив
hlist_head-ов,
и в нужную цепочку подшивается новый
hlist_entry по тем же правилам, что
и в случае со списками.
Синхронизация
Синхронизация представлена в виде большого спектра примитивов. Начнем с простейших.
Атомарные переменные.
Все знают, что на SMP-системах операция
inc (%eax) может привести не к тому
о чем думал программист. Именно для этого ввели специальный платформонезависимый
тип
atomic_t и операции с ним --
atomic_inc,
atomic_dec и так
далее. На i386 архитектуре они выполнены с помощью аппаратного префикса
lock
к соответствующей инструкции. Этот префикс гарантирует эксклюзивный доступ к шине
на время операции, то есть на время чтение-операция-запись.
Защелки или spinlock
Все знают для чего они нужны, расскажу как они сделаны и о чем нужно помнить, используя
их. Устройство защелки видно из устройства (схематичного) функции
spin_lock:
Код: Выделить всё
1:
lock decl (%1); /* %1 points to lock in memory */
js 2f
.section LOCK_FAILED
2:
cmp 0, (%1)
jle 2b
jmp 1b
.endsection
Открытый lock содержит 1, значит если два процессора сделают decl, то один из них получит
sign бит в флаговом регистре и упрыгает в отдельную секцию ждать открытия lock.
При работе с защелками важно помнить одну простую вещь -- нельзя звать функцию schedude(),
так как защелка останется закрытой и не факт, что откроется. За это время будут
простаивать все остальные процессоры, пытаясь ее взять.
Семафоры или semaphore (в 2.6.16 ядре их заменили на mutex)
Семафор -- это тот же spinlock, но имеющий на борту список процессов, ожидающих его
открытия. При неудаче взять семафор процесс переводится в uninterruptible состояние и
зовется schedule() чтобы освободить процессор. Процессы в таком состоянии не убиваются
никаким сигналаси вообще. Таким образом отличия семафоров от lock такие: можно звать
schedule() с неотпущенным семафором и честность по отношению к процессам. Поясню -- в
случае spinlock если три процессора пытаются взять lock, то очередность прохода будет
произвольной, в случае же с семафорами -- сначала семафор достанется первому попытавшемуся,
потом второму и так далее. Функции для самостоятельной работы --
down и
up,
а в новых (2.6.16 и выше) ядрах --
mutex_lock и
mutex_unlock.
Защелки и семафоры на чтение
Это обычные защелки, но защелкивать их можно двумя способами -- для чтения и для записи.
Защелка, закрытая на чтение допускает защелкивание на чтение еще раз (с другого процессора).
Защелка, закрытая на запись не пропускает никого. Устроено это все так:
Код: Выделить всё
/* read_lock - lock for reading */
lock decl (%1)
js 1f
... /* same as in lock */
/* write_lock - lock for writing */
lock subl 0x01000000, (%1)
js 1f
... /* same as in lock */
Открытая зацелка содержит
0x01000000, что допускает ее взятие большому количеству
чтецов и всего одному писателю. Правила раблты с ними -- такие же как и в простых аналогах.
Счетчики вхождений
Эти используются в случае, когда писатель один но ему нельзя ждать ни одного тика.
Чтобы этого достичь отыгрываются на чтецах. Устроено это так:
Код: Выделить всё
static inline void write_seqcount_begin(seqcount_t *lock)
{
lock->sequence++;
smp_wmb();
}
static inline void write_seqcount_end(seqcount_t *lock)
{
smp_wmb();
lock->sequence++;
}
...
seqcount_t lock = SEQCOUNT_ZERO;
...
write_seqcount_begin(&lock);
/* write what you want */
write_seqcount_end(&lock);
как видим -- писатель действительно никого не ждет, а лишь увеличивает два раза счетчик.
Функция
smp_wmb -- это барьер для архитектур, у которых запись в память может
менять свой порядок.
Теперь читатель:
Код: Выделить всё
static inline int read_seqcount_begin(struct seqcount_t *lock)
{
int ret;
ret = lock->sequence;
smp_rmb();
return ret;
}
static inline int read_seqcount_retry(struct seqcount_t *lock, int s)
{
smp_rmb();
return (s & 1) | (lock->sequence ^ s);
}
...
int seq;
do {
seq = read_seqcount_begin(&lock);
/* read data */
} while (read_seqcount_retry(&lock, seq));
Функция
read_seqcount_retry -- это оптимизированная проыверка того, что
в момент начала чтения счетчик был нечетным (писатель работал) или изменился
в процессе чтения (писатель отработал быстрее), то есть читатель повторяет
попытки чтитать данные пока не убедится в том, что в процессе чтения никто
их не попортил.
to be continued...