У цій статті описано реалізацію конвеєрів в ядрі Unix. Я був дещо розчарований, що недавня стаття під назвою «
Про що мова?
Конвеєри — «ймовірно, найважливіший винахід у Unix» — це визначальна характеристика об'єднання воєдино маленьких програм, що лежить в основі Unix філософії, а також знайомий напис у командному рядку:
$ echo hello | wc -c
6
Ця функціональність залежить від системного виклику, що надається ядром. pipe
, який описано на сторінках документації
Конвеєри забезпечують односпрямований канал міжпроцесної взаємодії. У конвеєра є вхід (write end) та вихід (read end). Дані, записані у вхід конвеєра, можна зчитати на виході.
Конвеєр створюється за допомогою дзвінка
pipe(2)
, який повертає два файлові дескриптори: один посилається на вхід конвеєра, другий на вихід.
Результати трасування наведеної вище команди демонструють створення конвеєра та потік даних через нього з одного процесу до іншого:
$ strace -qf -e execve,pipe,dup2,read,write
sh -c 'echo hello | wc -c'
execve("/bin/sh", ["sh", "-c", "echo hello | wc -c"], …)
pipe([3, 4]) = 0
[pid 2604795] dup2(4, 1) = 1
[pid 2604795] write(1, "hellon", 6) = 6
[pid 2604796] dup2(3, 0) = 0
[pid 2604796] execve("/usr/bin/wc", ["wc", "-c"], …)
[pid 2604796] read(0, "hellon", 16384) = 6
[pid 2604796] write(1, "6n", 2) = 2
Батьківський процес викликає pipe()
, щоб отримати підключені файлові дескриптори. Один дочірній процес записує в один дескриптор, а інший зчитує ті ж дані з іншого дескриптора. Оболонка за допомогою dup2 перейменовує дескриптори 3 і 4, щоб вони відповідали stdin і stdout.
Без конвеєрів оболонці довелося б записувати результат одного процесу файл і передавати його іншому процесу, щоб той прочитав дані з файлу. В результаті ми витрачали б більше ресурсів та місце на диску. Однак конвеєри хороші не тільки тим, що дозволяють уникнути використання тимчасових файлів:
Якщо процес намагається прочитати з порожнього конвеєра, тоді
read(2)
заблокує доти, доки дані не стануть доступними. Якщо процес спробує записати у заповнений конвеєр, тодіwrite(2)
заблокує до тих пір, поки з конвеєра не буде зчитано достатньо даних для виконання запису.
Як і вимога POSIX, це важлива властивість: запис в конвеєр аж до PIPE_BUF
байтів (як мінімум 512) має бути атомарною, щоб процеси могли взаємодіяти один з одним через конвеєр так, як звичайні файли (які не надають таких гарантій) не можуть.
При використанні звичайного файлу процес може записати у нього всі свої вихідні дані та передати іншому процесу. Або процеси можуть діяти в режимі жорсткого розпаралелювання, за допомогою зовнішнього сигнального механізму (на зразок семафору) повідомляючи один одному про завершення запису або читання. Конвеєри позбавляють нас від усіх цих турбот.
Що ми шукаємо?
Поясню на пальцях, щоб вам було легко уявити, як може працювати конвеєр. Вам знадобиться виділити в пам'яті буфер і стан. Знадобляться функції для додавання та видалення даних із буфера. Знадобиться якийсь засіб, щоб викликати функції під час операцій читання та запису у файлові дескриптори. І знадобляться блокування, щоб реалізувати описану вище спеціальну поведінку.
Тепер ми готові допитати при яскравому світлі ламп вихідний код ядра, щоб підтвердити чи спростувати нашу невиразну уявну модель. Але завжди будьте готові до несподіванок.
Де ми шукаємо?
Я не знаю, де лежить мій екземпляр відомої книги.
Блукання по архівах TUHS схоже на відвідування музею. Ми можемо подивитись нашу спільну історію, і я відчуваю повагу до багаторічних зусиль з відновлення всіх цих матеріалів біт за бітом зі старих касет та роздруківок. І гостро усвідомлюю ті фрагменти, які ще відсутні.
Задовольнивши свою цікавість у частині давньої історії конвеєрів, для порівняння можемо подивитися на сучасні ядра.
До речі, pipe
є системним викликом номер 42 у таблиці sysent[]
. Збіг?
Традиційні ядра Unix (1970-1974)
Я не знайшов жодних слідів pipe(2)
ні в
TUHS стверджує, що
Третя редакція Unix була останньою версією з ядром, написаним на асемблері, але першою версією з конвеєрами. Протягом 1973-го велися роботи з покращення третьої редакції, ядро переписали на С, і так з'явилася четверта редакція Unix.
Один із читачів знайшов скан документа, в якому Даг МакІлрой запропонував ідею «з'єднання програм за принципом садового шлангу».
У книзі Брайана Кернігана «
Коли з'явилася Unix, моє захоплення корутинами змусило мене попросити автора ОС Кена Томпсона дозволити даним, записаним в якийсь процес, йти не тільки на пристрій, а й на вихід до іншого процесу. Кен вирішив, що це можливо. Однак, як мінімаліст, він хотів, щоб кожна системна функція відігравала значну роль. Чи справді прямий запис між процесами має велику перевагу порівняно із записом у проміжний файл? І тільки коли я вніс конкретну пропозицію з яскравою назвою «конвеєр» та описом синтаксису взаємодії процесів, Кен, нарешті, вигукнув: «Я зроблю це!».
І зробив. Одним доленосним вечором Кен змінив ядро та оболонку, виправив кілька стандартних програм, стандартизувавши їхню процедуру прийняття вхідних даних (які можуть надходити з конвеєра), а також змінив імена файлів. Наступного дня конвеєри почали дуже широко застосовувати у додатках. До кінця тижня секретарки з їх допомогою надсилали на принтер документи з текстових редакторів. Трохи пізніше Кен замінив оригінальний API та синтаксис для оболонки використання конвеєрів на чистіші угоди, які відтоді застосовуються.
На жаль, вихідний код ядра третьої редакції Unix втрачено. І хоча у нас є написаний на С вихідний код ядра
У нас є текст документації з pipe(2)
з обох релізів, тому можна почати з пошуку у документації pipe(2)
написаний на асемблері та повертає лише один файловий дескриптор, але вже надає очікувану основну функціональність:
Системний виклик труба створює механізм введення виведення, який називається конвеєром. Файловий дескриптор, що повертається, можна використовувати для операцій читання та запису. Коли конвеєр щось записується, то буферизується до 504 байтів даних, після чого процес запису припиняється. Під час читання з конвеєра буферизовані дані забираються.
До наступного року ядро було переписано С, а pipe(fildes)
'
Системний виклик труба створює механізм введення виведення, який називається конвеєром. Файлові дескриптори, що повертаються, можна використовувати в операціях читання та запису. Коли щось записується в конвеєр, то використовується дескриптор, що повертається в r1 (соотв. fildes [1]), буферизується до 4096 байтів даних, після чого процес запису припиняється. При читанні з конвеєра дескриптор, що повертається в r0 (співвід. fildes [0]), забирає дані.
Передбачається, що після визначення конвеєра два (або більше) взаємодіючі процеси (створені наступними викликами) вилка) будуть передавати дані з конвеєра за допомогою дзвінків зчитування и запис.
В оболонці є синтаксис визначення лінійного масиву процесів, з'єднаних за допомогою конвеєра.
Виклики на читання з порожнього конвеєра (що не містить буферизованих даних), що має лише один кінець (закриті всі файлові дескриптори, що записують), повертають «кінець файлу». Виклики запису в аналогічній ситуації ігноруються.
Найраніша
Шоста редакція Unix (1975)
Починаємо читати вихідний код Unix
Багато років книга Львів була єдиним документом по ядру Unix, доступним поза стінами Bell Labs. Хоча ліцензія шостої редакції дозволяла викладачам використовувати її вихідний код, але ліцензія сьомої редакції виключила цю можливість, тому книга поширювалася у вигляді нелегальних машинописних копій.
Сьогодні можна купити репринтний екземпляр книги, на обкладинці якої зображено студентів у копіювального апарату. А завдяки Уоррену Тумі (який запустив проект TUHS) ви можете завантажити
Більше 15 років тому я набрав копію вихідного коду, наведеного в Львівтому що мені не подобалося якість моєї копії з невідомої кількості інших копій. TUHS ще не існувало, і я не мав доступу до старих вихідників. Але 1988-го я знайшов стару стрічку з 9 доріжками, на якій була резервна копія з комп'ютера PDP11. Важко було зрозуміти, чи працює вона, але там було непошкоджене дерево /usr/src/, в якому більшість файлів були позначені 1979 роком, що вже тоді виглядало давниною. Це була сьома редакція або похідна PWB, як я вважав.
Я взяв знахідку за основу та вручну відредагував вихідники до стану шостої редакції. Частина коду залишилася такою ж, частину довелося трохи підредагувати, помінявши сучасний токен += на застарілий =+. Щось просто видалив, а щось довелося повністю переписати, але не надто багато.
І сьогодні ми можемо в онлайні читати на TUHS вихідний код шостої редакції з
До речі, на перший погляд, головною особливістю С-коду до періоду Кернігана та Річі є його стислість. Не так часто мені вдається вставляти фрагменти коду без редагування, щоб він відповідав відносно вузькій області відображення на моєму сайті.
На початку
/*
* Max allowable buffering per pipe.
* This is also the max size of the
* file created to implement the pipe.
* If this size is bigger than 4096,
* pipes will be implemented in LARG
* files, which is probably not good.
*/
#define PIPSIZ 4096
Розмір буфера не змінювався з часів четвертої редакції. Але тут ми без будь-якої публічної документації бачимо, що колись конвеєри використовували файли як запасне сховище!
Що стосується LARG-файлів, то вони відповідають
Ось справжній системний виклик pipe
:
/*
* The sys-pipe entry.
* Allocate an inode on the root device.
* Allocate 2 file structures.
* Put it all together with flags.
*/
pipe()
{
register *ip, *rf, *wf;
int r;
ip = ialloc(rootdev);
if(ip == NULL)
return;
rf = falloc();
if(rf == NULL) {
iput(ip);
return;
}
r = u.u_ar0[R0];
wf = falloc();
if(wf == NULL) {
rf->f_count = 0;
u.u_ofile[r] = NULL;
iput(ip);
return;
}
u.u_ar0[R1] = u.u_ar0[R0]; /* wf's fd */
u.u_ar0[R0] = r; /* rf's fd */
wf->f_flag = FWRITE|FPIPE;
wf->f_inode = ip;
rf->f_flag = FREAD|FPIPE;
rf->f_inode = ip;
ip->i_count = 2;
ip->i_flag = IACC|IUPD;
ip->i_mode = IALLOC;
}
У коментарі ясно описано, що відбувається. Але розібратися в коді не так просто, почасти через те, як за допомогоюR0
и R1
передаються параметри системних викликів і значення, що повертаються.
Спробуємо за допомогою
pipe()
повинен через R0
и R1
повертати номери файлових дескрипторів для читання та запису. falloc()
повертає покажчик на файлову структуру, але також «повертає» через u.u_ar0[R0]
та файловий дескриптор. Тобто код зберігає в r
файловий дескриптор для читання і надає дескриптор для запису прямо з u.u_ar0[R0]
після другого виклику falloc()
.
прапор FPIPE
, який ми поставили під час створення конвеєра, управляє поведінкою функції
/*
* common code for read and write calls:
* check permissions, set base, count, and offset,
* and switch out to readi, writei, or pipe code.
*/
rdwr(mode)
{
register *fp, m;
m = mode;
fp = getf(u.u_ar0[R0]);
/* … */
if(fp->f_flag&FPIPE) {
if(m==FREAD)
readp(fp); else
writep(fp);
}
/* … */
}
Потім функція readp()
в pipe.c
зчитує дані з конвеєра. Але простежити реалізацію краще починаючи з writep()
. Повторюся, код ускладнився через особливості угоди про передачу аргументів, але деякі подробиці можна опустити.
writep(fp)
{
register *rp, *ip, c;
rp = fp;
ip = rp->f_inode;
c = u.u_count;
loop:
/* If all done, return. */
plock(ip);
if(c == 0) {
prele(ip);
u.u_count = 0;
return;
}
/*
* If there are not both read and write sides of the
* pipe active, return error and signal too.
*/
if(ip->i_count < 2) {
prele(ip);
u.u_error = EPIPE;
psignal(u.u_procp, SIGPIPE);
return;
}
/*
* If the pipe is full, wait for reads to deplete
* and truncate it.
*/
if(ip->i_size1 == PIPSIZ) {
ip->i_mode =| IWRITE;
prele(ip);
sleep(ip+1, PPIPE);
goto loop;
}
/* Write what is possible and loop back. */
u.u_offset[0] = 0;
u.u_offset[1] = ip->i_size1;
u.u_count = min(c, PIPSIZ-u.u_offset[1]);
c =- u.u_count;
writei(ip);
prele(ip);
if(ip->i_mode&IREAD) {
ip->i_mode =& ~IREAD;
wakeup(ip+2);
}
goto loop;
}
На вхід конвеєра ми хочемо записати байти u.u_count
. Спочатку потрібно заблокувати індексний дескриптор (див. нижче plock
/prele
).
Потім перевіряємо лічильник посилань inode. Поки обидва кінці конвеєра залишаються відкритими, лічильник має дорівнювати 2. Ми дотримуємо одне посилання (з rp->f_inode
), так що якщо лічильник буде менше 2, то це повинно означати, що процес, що читає, закрив свій кінець конвеєра. Іншими словами, ми намагаємося писати до закритого конвеєра, а це є помилкою. Вперше код помилки EPIPE
та сигнал SIGPIPE
з'явилися у шостій редакції Unix.
Але навіть якщо конвеєр відкрито, він може бути заповнений. У цьому випадку ми знімаємо блокування і йдемо спати, сподіваючись, що інший процес прочитає з конвеєра і звільнить у ньому достатньо місця. Прокинувшись, ми повертаємося на початок, знову вішаємо блокування і запускаємо новий цикл запису.
Якщо в конвеєрі достатньо вільного місця, ми записуємо в нього дані за допомогою i_size1
у inode'а (при порожньому конвеєрі може дорівнювати 0) вказує на кінець даних, які в ньому вже містяться. Якщо місця для запису достатньо, ми можемо заповнити конвеєр від i_size1
до PIPESIZ
. Потім знімаємо блокування і намагаємося пробудити будь-який процес, який чекає на можливість прочитати з конвеєра. Повертаємося на початок, щоб подивитися, чи вдалося записати стільки байтів, скільки нам було потрібно. Якщо не вдалося, то розпочинаємо новий цикл запису.
Зазвичай параметр i_mode
у inode'а використовується для зберігання дозволів r
, w
и x
. Але у випадку з конвеєрами ми сигналізуємо про очікування якимось процесом запису чи читання за допомогою бітів IREAD
и IWRITE
відповідно. Процес задає прапор та викликає sleep()
, і очікується, що в майбутньому якийсь інший процес викличе wakeup()
.
Справжнє диво відбувається в sleep()
и wakeup()
. Вони реалізовані в
/*
* Give up the processor till a wakeup occurs
* on chan, at which time the process
* enters the scheduling queue at priority pri.
* The most important effect of pri is that when
* pri<0 a signal cannot disturb the sleep;
* if pri>=0 signals will be processed.
* Callers of this routine must be prepared for
* premature return, and check that the reason for
* sleeping has gone away.
*/
sleep(chan, pri) /* … */
/*
* Wake up all processes sleeping on chan.
*/
wakeup(chan) /* … */
Процес, який викликає sleep()
для певного каналу, може бути пізніше збуджений іншим процесом, який викликає wakeup()
для того ж каналу. writep()
и readp()
координують свої дії за допомогою таких дзвінків. Зверніть увагу, що pipe.c
завжди віддає пріоритет PPIPE
під час виклику sleep()
тому все sleep()
можуть перериватись по сигналу.
Тепер ми маємо все, щоб розібратися у функції readp()
:
readp(fp)
int *fp;
{
register *rp, *ip;
rp = fp;
ip = rp->f_inode;
loop:
/* Very conservative locking. */
plock(ip);
/*
* If the head (read) has caught up with
* the tail (write), reset both to 0.
*/
if(rp->f_offset[1] == ip->i_size1) {
if(rp->f_offset[1] != 0) {
rp->f_offset[1] = 0;
ip->i_size1 = 0;
if(ip->i_mode&IWRITE) {
ip->i_mode =& ~IWRITE;
wakeup(ip+1);
}
}
/*
* If there are not both reader and
* writer active, return without
* satisfying read.
*/
prele(ip);
if(ip->i_count < 2)
return;
ip->i_mode =| IREAD;
sleep(ip+2, PPIPE);
goto loop;
}
/* Read and return */
u.u_offset[0] = 0;
u.u_offset[1] = rp->f_offset[1];
readi(ip);
rp->f_offset[1] = u.u_offset[1];
prele(ip);
}
Можливо, вам буде простіше читати цю функцію знизу догори. Гілка "read and return" зазвичай використовується, коли в конвеєрі є якісь дані. У цьому випадку ми за допомогою f_offset
читання, а потім оновлюємо значення відповідного усунення.
При наступному читанні конвеєр буде порожнім, якщо зміщення читання досягло значення i_size1
у inode'а. Ми скидаємо позицію на 0 і намагаємося розбудити будь-який процес, який хоче записати у конвеєр. Ми знаємо, що коли конвеєр буде повний, writep()
засне на ip+1
. А тепер, коли конвеєр порожній, ми можемо збудити його, щоб він відновив свій цикл запису.
Якщо читати нічого, то readp()
може встановити прапор IREAD
і заснути на ip+2
. Ми знаємо, що його розбудить writep()
коли запише в конвеєр якісь дані.
Коментарі до u
» ми можемо поводитися з ними як із звичайними функціями вводу-виводу, які беруть файл, позицію, буфер у пам'яті, і підраховують кількість байтів для читання чи запису.
/*
* Read the file corresponding to
* the inode pointed at by the argument.
* The actual read arguments are found
* in the variables:
* u_base core address for destination
* u_offset byte offset in file
* u_count number of bytes to read
* u_segflg read to kernel/user
*/
readi(aip)
struct inode *aip;
/* … */
/*
* Write the file corresponding to
* the inode pointed at by the argument.
* The actual write arguments are found
* in the variables:
* u_base core address for source
* u_offset byte offset in file
* u_count number of bytes to write
* u_segflg write to kernel/user
*/
writei(aip)
struct inode *aip;
/* … */
Щодо «консервативного» блокування, то readp()
и writep()
блокують inode до того часу, поки закінчать роботу чи отримають результат (тобто викличуть wakeup
). plock()
и prele()
працюють просто: за допомогою іншого набору дзвінків sleep
и wakeup
дозволяють нам пробуджувати будь-який процес, якому потрібне блокування, яке ми щойно зняли:
/*
* Lock a pipe.
* If its already locked, set the WANT bit and sleep.
*/
plock(ip)
int *ip;
{
register *rp;
rp = ip;
while(rp->i_flag&ILOCK) {
rp->i_flag =| IWANT;
sleep(rp, PPIPE);
}
rp->i_flag =| ILOCK;
}
/*
* Unlock a pipe.
* If WANT bit is on, wakeup.
* This routine is also used to unlock inodes in general.
*/
prele(ip)
int *ip;
{
register *rp;
rp = ip;
rp->i_flag =& ~ILOCK;
if(rp->i_flag&IWANT) {
rp->i_flag =& ~IWANT;
wakeup(rp);
}
}
Спершу я не міг зрозуміти, чому readp()
не викликає prele(ip)
до виклику wakeup(ip+1)
. Перше, що writep()
викликає у своєму циклі, це plock(ip)
, який призводить до взаємоблокування, якщо readp()
ще не зняв свій блок, тому код якимось чином має працювати правильно. Якщо подивитися на wakeup()
, то стає зрозуміло, що він тільки позначає сплячий процес як готовий до виконання, щоб у майбутньому sched()
справді запустила його. Так що readp()
викликає wakeup()
, знімає блокування, задає IREAD
і викликає sleep(ip+2)
- все це до того, як writep()
відновлює цикл.
На цьому опис конвеєрів у шостій редакції закінчено. Простий код, далекосяжні наслідки.
Xv6, просте Unix-подібне ядро
На створення ядра
У коді міститься зрозуміла та продумана реалізація pipealloc()
:
#define PIPESIZE 512
struct pipe {
struct spinlock lock;
char data[PIPESIZE];
uint nread; // number of bytes read
uint nwrite; // number of bytes written
int readopen; // read fd is still open
int writeopen; // write fd is still open
};
int
pipealloc(struct file **f0, struct file **f1)
{
struct pipe *p;
p = 0;
*f0 = *f1 = 0;
if((*f0 = filealloc()) == 0 || (*f1 = filealloc()) == 0)
goto bad;
if((p = (struct pipe*)kalloc()) == 0)
goto bad;
p->readopen = 1;
p->writeopen = 1;
p->nwrite = 0;
p->nread = 0;
initlock(&p->lock, "pipe");
(*f0)->type = FD_PIPE;
(*f0)->readable = 1;
(*f0)->writable = 0;
(*f0)->pipe = p;
(*f1)->type = FD_PIPE;
(*f1)->readable = 0;
(*f1)->writable = 1;
(*f1)->pipe = p;
return 0;
bad:
if(p)
kfree((char*)p);
if(*f0)
fileclose(*f0);
if(*f1)
fileclose(*f1);
return -1;
}
pipealloc()
задає стан решти реалізації, яка включає функції piperead()
, pipewrite()
и pipeclose()
. Фактичний системний виклик sys_pipe
є обгорткою, реалізованою в
Linux 0.01
Ви можете знайти вихідний код Linux 0.01. Буде повчально вивчити реалізацію конвеєрів у його fs
/pipe.c
. Тут для представлення конвеєра використовується inode, але сам конвеєр написаний на сучасному C. Якщо ви проникли через код шостої редакції, то тут ви не зазнаєте труднощів. Так виглядає функція write_pipe()
:
int write_pipe(struct m_inode * inode, char * buf, int count)
{
char * b=buf;
wake_up(&inode->i_wait);
if (inode->i_count != 2) { /* no readers */
current->signal |= (1<<(SIGPIPE-1));
return -1;
}
while (count-->0) {
while (PIPE_FULL(*inode)) {
wake_up(&inode->i_wait);
if (inode->i_count != 2) {
current->signal |= (1<<(SIGPIPE-1));
return b-buf;
}
sleep_on(&inode->i_wait);
}
((char *)inode->i_size)[PIPE_HEAD(*inode)] =
get_fs_byte(b++);
INC_PIPE( PIPE_HEAD(*inode) );
wake_up(&inode->i_wait);
}
wake_up(&inode->i_wait);
return b-buf;
}
Навіть не дивлячись на визначення структур можна розібратися, як лічильник посилань inode використовується для перевірки, чи наводить операція запису до SIGPIPE
. Крім побайтової роботи, цю функцію легко зіставити з вищеописаними ідеями. Навіть логіка sleep_on
/wake_up
не виглядає такою чужорідною.
Сучасні ядра Linux, FreeBSD, NetBSD, OpenBSD
Я швидко пробігся деякими сучасними ядрами. У жодному з них немає реалізації з використанням диска (не дивно). У Linux своя реалізація. І хоча три сучасні BSD-ядра містять реалізації на основі коду, який був написаний Джоном Дайсоном, за минулі роки вони стали дуже відрізнятися один від одного.
Щоб читати fs
/pipe.c
(на Linux) або sys
/kern
/sys_pipe.c
(на *BSD), потрібна справжня самовіддача. Сьогодні в коді важливі продуктивність та підтримка таких функцій, як векторні та асинхронні операції введення-виведення. А подробиці виділення пам'яті, блокувань та конфігурації ядра - все це сильно відрізняється. Це не те, що потрібно вузам для вступного курсу з операційних систем.
У будь-якому випадку мені було цікаво розкопати кілька старовинних патернів (наприклад, генерування SIGPIPE
і повернення EPIPE
при записі в закритий конвеєр) у всіх цих, таких різних, сучасних ядрах. Мабуть, я ніколи не побачу наживо комп'ютер PDP-11, але ще є чому повчитися на коді, який був написаний за кілька років до мого народження.
Написана Діві Капуром у 2011-му році стаття «
Джерело: habr.com