Как заблокировать данные из userspace?

Можно было бы сварганить нечто подобное семафорам, например flock+temp_file. Не знаю насколько это будет быстро работать.
Костыль конечно грубоватый. :)

А как твоё мнение на тему posix-семафоров???

Чтобы процессы получали сигнал при доступе к шареной области памяти её надо запротектировать. При етом процессы будут получать SIGSEGV на который надо повесить обработчик.

А ещё если ты при помощи mmap шариш файл отображённый в памяти то можеш использовать fcntl на дескрипторе етого файла. Немного медленовато чем семафоры но неплохо работает. Кстати по всей видимости тебе придётся вспомнить про sched_yeild() & pause();-)

Желаю удачи.

> Есть кусок памяти, расшаренный через mmap с MAP_SHARED. Мне надо его из
> userspace'а одного процесса заблокировать, чтобы другие процессы при
> попытке в него писать получали бы сигнал, а сам процесс мог бы туда писать.

mmap(PROT_READ, MAP_SHARED). процесс, который должен писать делает
mprotect(PROT_READ|PROT_WRITE). не слишком быстро - O(mem_size).

> что можно использовать вместо IPC семафоров для синхронизации доступа
> различных процессов к памяти

futex, если 2.6

> IPC семафоров у меня всего 128, мне их не хватает

хм... /proc/sys/kernel/sem ? у меня сейчас linux 2.20, но судя
по kernel/sysctl.c:kern_table[] должно работать.

> что можно использовать вместо IPC семафоров для синхронизации доступа
> различных процессов к памяти

можете сделать hashed locking: один семафор на N сегментов памяти.
разумеется, у этого подхода есть недостатки: невозможность работать
параллельно с регионами, обслуживаемыми одним семафором.

я так понимаю, mmap у вас MAP_ANONYMOUS. можете с тем же успехом
работать с tmpfs, это не будет медленнее, тогда у вас будет файл
для flock(). но вот это уже, конечно, медленнее.

>Кстати по всей видимости тебе придётся вспомнить про sched_yeild() & pause();-)

Зато реализацию этих семафоров можно выдрать из исходников LinuxThreads (только там придется немного дописать, чтобы семафоры могли жить в shared memory). Вопрос только будет ли это работать не на Intel (Intel благо кэширует по физическим адресам и с атомарными операциями в shared memory у него проблем нет).

Спасибо всем ответившим,

Посмотрел на исходники posix семафоров и сварганил нечто на RT сигналах + sched_yeild(). Конечно, чисто Линух-специфик, но мне нужна оптимизация под конкретную машину. Погоняю сегодня тесты, посмотрю на скорость.

Dead (28.10.2004 1:54:26):

> ...flock+temp_file.

Мне скорость критична.

cvv (28.10.2004 11:06:11):

> А как твоё мнение на тему posix-семафоров???

Первое, что пришло в голову.

Увы :( Под Линухом они между процессами не работают.

Я помещал семафор в общую память, и процесс на нем благополучно засыпал. Но когда я пытался его разбудить из другого процесса, он не просыпался. strace показал, что он на rt_sigsuspend спит -- конечно, не туды сигнал посылается...

> Чтобы процессы получали сигнал при доступе к шареной области памяти её надо запротектировать.

Тормознуто.

idle (28.10.2004 11:25:46):

> futex, если 2.6

Увы, 2.4

> /proc/sys/kernel/sem ?

О, спасибо. Я подозревал про такое, но почему-то не нашел вчера.

> можете сделать hashed locking:

Спасибо за идею, когда-нибудь пригодится.

Но я уже, вроде, нашел приемлемое решение -- гораздо быстрее SysV семафоров получается, вроде...

Murr (28.10.2004 12:28:19):

> Зато реализацию этих семафоров можно выдрать из исходников LinuxThreads.

Я посмотрел на librt, там сплошной inline asm, на неделю разбираться. Вроде, проще сделал -- у меня ж гораздо более trust среда, чем требуется в общем случае.

> Посмотрел на исходники posix семафоров и сварганил нечто на
> RT сигналах + sched_yeild()

что-то никак в толк не возьму, какая-то странная комбинация.
как вы это сделали?

Murr:
> Зато реализацию этих семафоров можно выдрать из исходников
> LinuxThreads (только там придется немного дописать, чтобы семафоры
> могли жить в shared memory)

что-то сомневаюсь я, что это возможно сделать в 2.4
если имеется в виду что-то вроде:

        while (xchng(&semaphore, 1) == 1)
                yield();

то это плохо. очень высокая wakeup latency. хотя в этом конкретном
случае это, возможно, и не страшно.

> while (xchng(&semaphore, 1) == 1)
> yield();

Нет, ну в LinuxThreads не polling все же. ;)

Там реализуются классические мьютексы поверх spin-блокировок и sigsuspend/kill. Вполне приличный код, между прочим, хоть его многие и не любят.

Murr:
> мьютексы поверх spin-блокировок и sigsuspend/kill
> Вполне приличный код, между прочим

так я и говорю, при чем здесь sched_yield() ?

>так я и говорю, при чем здесь sched_yield() ?
ну можно и через sched_yield, если процессора не жалко (особенно, если под мьютексом спят). ;o)

Если мьютексы неактивно используются, то можно и так...

Кстати, по поводу sched_yield.

Я недавно в коде нашего продукта нашел очередной образец подобного творчества. while(blah-blah-blah) schedule();

Это был творческий шок.
Если бы хотя бы был policy |= SCHED_YIELD... :)

> Я недавно в коде нашего продукта нашел очередной
> образец подобного творчества

очень любопытно, что за продукт, если не очень секретно.
мне просто интересно, в Москве вообще есть конторы,
связанные с kernel programming?

>очень любопытно, что за продукт, если не очень секретно.
>мне просто интересно, в Москве вообще есть конторы,
>связанные с kernel programming?

Есть и довольно много(большая часть тех, что я знаю - это оффшор). Более того, есть серьезные проблемы с поиском программистов. Многие не хотят мараться меньше, чем за 2000 у.е., так что нанять толкового программиста поработать годик за 1200-1500 у.е. довольно сложно, даже с уловиями довольно гибкого графика и проч.

P.S. Надеюсь, создатель ветки нас простит за оффтоп, т.к. проблему он вроде решил, а темы вверх со временем все равно не всплывают. :)

Вообще, большинство контор, с которыми я сталкивался, занимается Linux в ключе портирования или разработки драйверов устройств. Из серьезных контор, которые серьезно сталкиваются c mm,fs,kernel,drivers/block я сталкивался только с namesys(которые клепали ReiserFS где-то в центре, не знаю, чем занимаются сейчас) и нашей(Datafoundation Inc).

> Есть и довольно много(большая часть тех, что я знаю - это оффшор)

ну все Murr, вы попали. если я после нового года таки
решу сменить работу - буду вытрясать из вас явки, пароли...

> Надеюсь, создатель ветки нас простит за оффтоп

так зато хоть не ругаемся!

idle:

You're welcome.
Если будет свободная минутка и есть интерес,
то могу подробнее рассказать, чем именно мы
занимаемся.

Почта: andrew сбк datafoundation тчк com

Кстати, по поводу sched_yield. 

Странные дела с ней.

На моем десктопе она хорошо работает, т.е., ожидаемо: код типа

В одном процессе:
for(i=0;;i++){ fprintf(stderr, "Child %d\n",i); sched_yield(); }
В другом процессе:
for(i=0;;i++)fprintf(stderr,"%d\n",i);

выдается типа:

Child: ready
Child: ready (1075068048).
Child 0
Parent: ready
0
...
202407
Child 1
202408
...
399758
Child 2
399759
...

Но вот на большой машине оно ведет себя странно:
...
Child 1
3214
Child 2
3215
Child 3
3216
Child 4
3217
Child 5
3218
Child 6
3219
Child 7
...
Типа, на разных процессорах. Ок, понятно Но теперь 
я их на один процессор бахаю:

dplace -e -c0 ./sched

Результат:

...
32419
32420
Child 1
Child 2
...
Child 5205
32421
...
58267
Child 5206
...
Child 23933
58268
58269
...

Т.е. sched_yield() вообще не работает.

И, кстати, в исходниках ядра я не нашел вообще SCHED_YIELD.

Кто мне может объяснить, что за пертурбации с этим флагом ? Я думал, 
ядро при sched_yield() автоматом делает policy |= SCHED_YIELD...

Я вместо sched_yield() использую nanosleep() c параметром 0(нс) или 1(нс). вобщем работа такого решения более красивая чем yield().

Die-Hard:

> Кстати, по поводу sched_yield.
> ...
> Но вот на большой машине оно ведет себя странно:
> ...
> Т.е. sched_yield() вообще не работает.
> И, кстати, в исходниках ядра я не нашел вообще SCHED_YIELD.

должно быть в include/linux/sched.h. у вас, кажется, какое-то
нестандартное ядро? может, они вычистили этот yield вообще,
с ним были проблемы в 2.4. в 2.6 этого флага нет.

посмотрите в kernel/sched.c:sys_sched_yield(), что там?

вообще использование sched_yield() почти всегда неправильно,
и я не понимаю, зачем она вам вообще. в 2.6 она реализована,
вроде бы, правильно, и семантика такова: процесс удаляется
из active, и помещается в expired prio_array. иными словами,
он не получит cpu тех пор, пока _все_ runnable процессы не
исчерпают свой timeslice.

в 2.4 SCHED_YIELD влияет на goodness(), то есть процессы
с этим флагом (который, кстати, очищается, когда процесс
вновь получает cpu), выбираются планировщиком в последнюю
очередь. но там были какие-то проблемы, которые я сейчас
не могу вспомнить.

Далее. вот этот тест:
> В одном процессе:
> for(i=0;;i++){ fprintf(stderr, "Child %d\n",i); sched_yield(); }
> В другом процессе:
> for(i=0;;i++)fprintf(stderr,"%d\n",i);

он, на самом деле, не очень правильный. например, возможно
следующее. когда child получает cpu, он пишет на консоль,
и вызывает sched_yield(), cpu переходит к parent, но child
остается runnable. parent тут же блокируется семафором, т.к.
терминал не готов. если других процессов на cpu нет, его
опять получает child. напоминаю, как только процесс получает
cpu, SCHED_YIELD из policy удаляется. теперь оба процесса
соревнуются за семафор на равных. побеждает child, т.к.
его динамический приоритет выше. и так далее, до тех пор,
пока child не проработает достаточно, чтобы его динамический
приоритет не уменьшился.

> Я вместо sched_yield() использую nanosleep() c параметром
> 0(нс) или 1(нс). вобщем работа такого решения более красивая
> чем yield().

по моему, трудно придумать что-то более неуклюжее.

я, помню, пытался вам это пояснить, но не сумел
http://www.linux.org.ru/view-message.jsp?msgid=553565

idle (*) (29.10.2004 12:48:59):

Thanks.

Ничего не понимаю!

>> И, кстати, в исходниках ядра я не нашел вообще SCHED_YIELD.

> должно быть в include/linux/sched.h.

Есть. #define SCHED_YIELD             0x10 
И что с ним делать? В ядре его нет!

find /usr/src/linux -name '*.c' -exec grep -H SCHED_YIELD \{\} \;

пусто

find /usr/src/linux -name '*.р' -exec grep -H SCHED_YIELD \{\} \;

Только в одном левом драйвере:

./drivers/net/e100/e100.h:        current->policy |= SCHED_YIELD;

> вообще использование sched_yield() почти всегда неправильно,
> и я не понимаю, зачем она вам вообще.

Я организовал вход в критическую секцию обработки семафора, 
проверяя некий атомарный флаг, разделенный между всеми 
процессорами, типа

while(  (++sem->bflag) != 1 ){*Conflict!*/
      /*Wait until a competitor finishes*/
      sem->bflag--;
      sched_yield();
}

<обработка структуры семафора>

sem->bflag--;

Сначала я хотел организовать нечто типа ethernet'а, то есть 
засыпать на случайный короткий промежуток, но потом подумал
про yield: конфликты предполагаются быть редкими, а по условию
на каждый процессор у меня не более одной "голодной" задачи.

Может, чего поумнее подскажете?

idle (29.10.2004 12:48:59):

> Далее. вот этот тест ... не очень правильный. например, возможно следующее. когда child получает cpu, он пишет на консоль, и вызывает sched_yield(), cpu переходит к parent, но child остается runnable. parent тут же блокируется семафором, т.к. терминал не готов.

На однопроцессорных боксах (с похожим ядром) он работает, как ожидалось.

Кроме того, я пробовал просто в общую память писАть -- результат тот же...

> while ((++sem->bflag) != 1) {
>        /*Wait until a competitor finishes*/
>        sem->bflag--;
>        sched_yield();
> }

это не будет работать. все очень racy. один пример:

               sem->bflag == 0

CPU1                               CPU2

load sem->bflag                    load sem->bflag

               оба прочитали ноль

increment, store                   increment, store

              sem->bflag == 1
              оба процесса считают, что
              семафор захвачен.

вам нужны atomic операции, но это поможет сделать
spinlock, а не семафор.

еще раз. sched_yield() использовать плохо. если она не
работает - вы просто зря тратите cpu. если работает
"как надо" у вас нет возможности "разбудить" процесс.
он не поучит cpu до тех пор, пока все процессы не
выработают timeslice.

вам действительно нужно сделать что-то похожее на реализацию
в LinuxThreads, как и писал Murr, но yield() вам не надо.

все таки, любобытно, что у вас в kernel/sched.c:sys_sched_yield()?

> > Далее. вот этот тест ... не очень правильный.
>
> На однопроцессорных боксах (с похожим ядром) он работает, как ожидалось.

да я просто как пример привел, что может случиться, и почему
yield() иногда дает "неожиданные" результаты.

2idle

Просто информация я как-то пытался трассировать работу оракловой БД так вот большая часть системных вызовов состояла из kill() & sched_yield().

2idle

оракл кстати на SMP работает прекрасно.

Тоесть задача каким-то образом решаема

anonymous (*) (29.10.2004 14:32:26):

> вам нужны atomic операции, но это поможет сделать
> spinlock, а не семафор.

А как мне завести spinlock из userspace'а, не имея ассемблера
(на IA64 __asm__ не работает).

> все таки, любобытно, что у вас в kernel/sched.c:sys_sched_yield()?

asmlinkage long sys_sched_yield(void)
{
   runqueue_t *rq = this_rq_lock();
   prio_array_t *array = current->array;

       /*
   * Decrease the yielding task's priority by one, to avoid
   * livelocks. This priority loss is temporary, it's recovered
   * once the current timeslice expires.
   *
   * If priority is already MAX_PRIO-1 then we still
   * roundrobin the task within the runlist.
   */

   /*
    * If the task has reached maximum priority (or is a RT task)
    * then just requeue the task to the end of the runqueue:
    */
   if (likely(current->prio == MAX_PRIO-1 || rt_task(current))) {
      list_del(&current->run_list);
      list_add_tail(&current->run_list, array->queue + current->prio);
   } else {
      list_del(&current->run_list);
      if (list_empty(array->queue + current->prio))
         __clear_bit(current->prio, array->bitmap);
      current->prio++;
      list_add_tail(&current->run_list, array->queue + current->prio);
      __set_bit(current->prio, array->bitmap);
   }
   spin_unlock(&rq->lock);

   schedule();

   return 0;
}

> Просто информация я как-то пытался трассировать работу оракловой БД так
> вот большая часть системных вызовов состояла из kill() & sched_yield().

и что? возможно, они используют ее правильно, возможно - нет.

> оракл кстати на SMP работает прекрасно. Тоесть задача каким-то образом решаема

вы о какой сейчас задаче говорите?

> anonymous (*) (29.10.2004 14:32:26):

так уж и anonymous :)

> > вам нужны atomic операции, но это поможет сделать
> > spinlock, а не семафор.
>
> А как мне завести spinlock из userspace'а, не имея ассемблера

смотрите libpthread. там должно быть что-то вроде pthread_spin_lock()

> (на IA64 __asm__ не работает).

у вас еще и компилятор не gcc?

> > все таки, любобытно, что у вас в kernel/sched.c:sys_sched_yield()?
>
> asmlinkage long sys_sched_yield(void)

хех! это не код 2.4. это backported ранняя версия O(1) планировщика.
что уж там дальше будет с таким yield'ом - одному аллаху известно.

знаете что, вот _лично_ я бы на вашем месте выкинул бы такое
ядро вместе с поддержкой от SGI, и поставил бы 2.6.

ну, попытался бы.

idle (*) (29.10.2004 15:54:58):

Спасибо за ответы.

Наверное я пока поотлаживаюсь на SysV семафорах и потихоньку поразгребаюсь со спинлоками.

Кстати, такой вопрос:

Допустим, я атомарно проинкрементил нечто на двух процессорах одновременно. Но оно же в кэшэ будет? Кэши по очереди сбросятся, и опять получим то же...

> у вас еще и компилятор не gcc?

icc, ессно.

Но, один хрен, что gcc, что icc на Итаниуме не поддерживают __asm. Вроде, накопал интринсики на тему, но меня уже время поджимает.

> знаете что, вот _лично_ я бы на вашем месте выкинул бы такое ядро вместе с поддержкой от SGI, и поставил бы 2.6.

У них уже давно 2.6 есть. Но я не могу остановить машину в ближайшие месяц-два.

> Допустим, я атомарно проинкрементил нечто на двух процессорах
> одновременно. Но оно же в кэшэ будет?

атомарные операции выполняются при помощи "семафора" 
на шине. для i386 это будет:
      lock; inc

ia64, кажется, делает это с помощью cmpxchg, но это,
в общем, не важно.

> Но, один хрен, что gcc, что icc на Итаниуме не поддерживают __asm

вот этого уже никак не может быть.
ну вот, хотя бы: include/asm-ia64/gcc_intrin.h

idle (29.10.2004 17:20:31):

>> Но, один хрен, что gcc, что icc на Итаниуме не поддерживают __asm

> вот этого уже никак не может быть.

Действительно, gcc проглотил!

Странно - мне говорили, что не работает...

Но мне нужен icc.

В принципе, в нем есть интринсики, типа _InterLockedIncrement() и даже _ReleaseSpinLock(volatile int *x), только я не понимаю, что он означает (release есть, а самого спинлока нет!)

Победил!

Так получилось:

в начале файла:
#include <ia64intrin.h>
#define tands(lock,val) _InterlockedExchange((lock), (val))
. . .

А вход в семафор таков:

while(  tands((volatile int *)&(sem->bflag),1 )!= 0 ){/*Conflict!*/
   /*Wait until a competitor finishes*/
   /* To avoid a memory HotSpot:*/
   while(sem->bflag!=0)
      sched_yield();
}


Функция _InterlockedExchange -- интринсик icc.

> Победил!

в итоге, получилось то, от чего я вас пытался предостеречь
в одном из первых постов в этом топике.

это будет работать, но это плохая реализация. но, возможно,
в вашем случае и сойдет.

особенно, если не contended.

idle (*) (29.10.2004 19:30:42):

> это будет работать, но это плохая реализация. ...

Ну, дык, какие есть альтернативы?
Единственная альтернатива, приходящая в голову -- busy work, то есть 
просто убрать из кода sched_yield():
while(  tands((volatile int *)&(sem->bflag),1 )!= 0 )
   while(sem->bflag!=0)

Меня это устраивает, поскольку время жизни этого (редко возникающего)
цикла будет исчисляться микросекундами.

Но я прикинул на некоторых "экстремальных" тестах -- получается 
медленнее, чем с sched_yield()!

> это будет работать, но это плохая реализация. ...
>
> Ну, дык, какие есть альтернативы?

да это я уже так, "с разгону" :)

я ничего не говорю, дешево и сердито, очень может
быть и сам бы так сделал.

а если коллизии редки, так и нормально.