Тази статия описва внедряването на конвейери в ядрото на Unix. Бях донякъде разочарован, че скорошна статия, озаглавена "
За какво говорим?
Тръбопроводите, „вероятно най-важното изобретение в Unix“, са определяща характеристика на основната философия на Unix за свързване на малки програми заедно, както и познат знак на командния ред:
$ echo hello | wc -c
6
Тази функционалност зависи от осигуреното от ядрото системно извикване pipe
, което е описано на страниците с документация
Тръбопроводите осигуряват еднопосочен канал за междупроцесна комуникация. Конвейерът има вход (край за запис) и изход (край за четене). Данните, записани на входа на тръбопровода, могат да бъдат прочетени на изхода.
Конвейерът се създава с помощта на повикването
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 г. се работи за подобряване на третото издание, ядрото е пренаписано на C и така се ражда четвъртото издание на Unix.
Един читател намери сканиране на документ, в който Дъг Макилрой предлага идеята за „свързване на програми като градински маркуч“.
В книгата на Браян Керниган
Когато Unix се появи, очарованието ми от съпрограмите ме накара да помоля автора на операционната система, Кен Томпсън, да позволи на данните, записани в процес, да отидат не само към устройството, но и да бъдат изведени към друг процес. Кен реши, че е възможно. Въпреки това, като минималист, той искаше всяка системна функция да играе важна роля. Писането директно между процесите наистина ли е голямо предимство пред писането в междинен файл? Едва когато направих конкретно предложение със закачливото име „тръбопровод“ и описание на синтаксиса за взаимодействие между процесите, Кен най-накрая възкликна: „Ще го направя!“
И го направи. Една съдбовна вечер Кен промени ядрото и обвивката, поправи няколко стандартни програми, за да стандартизира начина, по който те приемат въвеждане (което може да дойде от конвейер), и също така промени имената на файловете. На следващия ден тръбопроводите започнаха да се използват много широко в приложенията. До края на седмицата секретарите ги използваха, за да изпращат документи от текстообработващите програми до принтера. Малко по-късно Кен замени оригиналния API и синтаксис за опаковане на използването на тръбопроводи с по-чисти конвенции, които се използват оттогава.
За съжаление изходният код за третото издание на Unix ядрото е изгубен. И въпреки че имаме изходния код на ядрото, написан на C
Имаме текст на документацията за pipe(2)
от двете версии, така че можете да започнете с търсене в документацията pipe(2)
е написан на асемблер и връща само един файлов дескриптор, но вече предоставя очакваната основна функционалност:
Системно обаждане тръба създава механизъм за вход/изход, наречен тръбопровод. Върнатият файлов дескриптор може да се използва за операции за четене и запис. Когато нещо се запише в конвейера, до 504 байта данни се буферират, след което процесът на запис се спира. При четене от тръбопровода, буферираните данни се отнемат.
До следващата година ядрото беше пренаписано на C и pipe(fildes)
"
Системно обаждане тръба създава механизъм за вход/изход, наречен тръбопровод. Върнатите файлови дескриптори могат да се използват в операции за четене и запис. Когато нещо се запише в конвейера, се използва манипулаторът, върнат в r1 (съответно fildes[1]), буфериран до 4096 байта данни, след което процесът на запис се спира. При четене от тръбопровода манипулаторът, върнат към r0 (съответно fildes[0]), взема данните.
Предполага се, че след като конвейерът е дефиниран, два (или повече) комуникиращи процеса (създадени от последващи извиквания на вилица) ще предава данни от тръбопровода с помощта на повиквания чета и пиша.
Обвивката има синтаксис за дефиниране на линеен масив от процеси, свързани с конвейер.
Извикванията за четене от празен тръбопровод (несъдържащ буферирани данни), който има само един край (всички записващи файлови дескриптори са затворени), връщат "край на файла". Обажданията за писане в подобна ситуация се игнорират.
Най-рано
Шесто издание на Unix (1975)
Нека започнем да четем изходния код на Unix
В продължение на много години книгата Lions беше единственият документ за ядрото на Unix, достъпен извън Bell Labs. Въпреки че лицензът за шестото издание позволява на учителите да използват неговия изходен код, лицензът за седмото издание изключва тази възможност, така че книгата се разпространява в незаконни машинописни копия.
Днес можете да закупите копие на книгата, на чиято корица са изобразени ученици на копирната машина. И благодарение на Warren Toomey (който започна проекта TUHS), можете да изтеглите
Преди повече от 15 години написах копие на дадения изходен код Lions, защото не ми хареса качеството на моето копие от неизвестен брой други копия. TUHS все още не съществуваше и нямах достъп до старите източници. Но през 1988 г. намерих стара касета с 9 песни, която съдържаше резервно копие от компютър PDP11. Беше трудно да се каже дали работи, но имаше непокътнато /usr/src/ дърво, в което повечето от файловете бяха обозначени с годината 1979, която дори тогава изглеждаше древна. Беше седмото издание или производната му PWB, както вярвах.
Взех находката като основа и ръчно редактирах източниците до състоянието на шестото издание. Част от кода остана същата, част трябваше да бъде леко редактирана, променяйки модерния токен += на остарелия =+. Нещо просто беше изтрито и нещо трябваше да бъде напълно пренаписано, но не твърде много.
И днес можем да прочетем онлайн на TUHS изходния код на шестото издание от
Между другото, на пръв поглед основната характеристика на C-кода преди периода на Керниган и Ричи е неговата краткост. Не се случва често да мога да вмъкна фрагменти от код без обширно редактиране, за да се поберат в относително тясна област за показване на моя сайт.
Рано
/*
* 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
. Първо трябва да заключим inode (вижте по-долу plock
/prele
).
След това проверяваме брояча на референтните индекси. Докато двата края на тръбопровода остават отворени, броячът трябва да е равен на 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);
}
Може да ви е по-лесно да прочетете тази функция отдолу нагоре. Клонът "четене и връщане" обикновено се използва, когато има някои данни в конвейера. В този случай ние използваме f_offset
прочетете и след това актуализирайте стойността на съответното отместване.
При следващи четения конвейерът ще бъде празен, ако отместването за четене е достигнато i_size1
в inode. Нулираме позицията на 0 и се опитваме да събудим всеки процес, който иска да пише в тръбопровода. Знаем, че когато конвейерът е пълен, writep()
ще заспи на ip+1
. И сега, когато конвейерът е празен, можем да го събудим, за да възобнови своя цикъл на запис.
Ако няма какво да се чете, тогава readp()
може да постави флаг IREAD
и заспивам на ip+2
. Знаем какво ще го събуди writep()
, когато записва някои данни в тръбопровода.
Коментари за u
„Можем да ги третираме като нормални I/O функции, които вземат файл, позиция, буфер в паметта и броят байтовете за четене или запис.
/*
* 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, докато не завършат работата си или не получат резултат (т.е. call 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), това изисква истинска отдаденост. Днешният код е за производителност и поддръжка на функции като векторни и асинхронни I/O. И подробностите за разпределението на паметта, заключванията и конфигурацията на ядрото се различават значително. Това не е необходимо на колежите за въвеждащ курс по операционни системи.
Във всеки случай за мен беше интересно да разкрия няколко стари модела (например генериране SIGPIPE
и обратно EPIPE
когато пишете в затворен конвейер) във всички тези, толкова различни, модерни ядра. Вероятно никога няма да видя компютър PDP-11 на живо, но все още има какво да науча от кода, който беше написан няколко години преди да се родя.
Написана от Диви Капур през 2011 г., статията "
Източник: www.habr.com