Jaderné noviny – 5. 1. 2010

28. 1. 2010 | Jirka Bourek

Články - Jaderné noviny – 5. 1. 2010  

Aktuální verze jádra: 2.6.33-rc3. Citáty týdne: Avi Kivity, Casey Schaufler, Alan Cox, Larry McVoy. list_sort() – řazení spojových seznamů. Omezení sítě. Shlukování využité paměti. RCU řetězce.

Obsah

• Aktuální verze jádra: 2.6.33-rc3
• Citáty týdne: Avi Kivity, Casey Schaufler, Alan Cox, Larry McVoy
• list_sort() – řazení spojových seznamů
• Omezení sítě
• Shlukování využité paměti
• RCU řetězce

Aktuální verze jádra: 2.6.33-rc3

Současné vývojové jádro je 2.6.33-rc3 vydané 5. ledna. Linus říká:

Většina patchů jsou nějaké aktualizace defconfigu SH (40 %), ale když je budu ignorovat, máme normální ,napůl ovladače, napůl všechno ostatní‘. Co se ovladačů týče, pravděpodobně nejvýznamnější změna se víceméně netýká kódu, je to malá změna, která označuje nový firewire stack jako doporučený.

Zkrácený changelog je v oznámení, detaily vizte v kompletním changelogu.

2.6.33-rc2 bylo vydáno 24. prosince. Obsahovalo mnoho oprav, Nouveau generátor „ctxprogs“ pro čipové sady nv40 a ovladač pro videokarty Silicon Motion sm712; toto vydání také odstranilo nepoužívaný a opuštěný subsystém pro distribuované úložiště. Všechny detaily vizte v kompletním changelogu.

Stabilní aktualizace: 2.6.27.43, 2.6.31.10 a 2.6.32.3 byly vydány 6. ledna. Všechny tři obsahují směsici oprav; 2.6.27.43 je relativně malé, zatímco ostatní jsou velké. Vydávání aktualizací pro 2.6.31 pravděpodobně skončí verzí 2.6.31.11.

Citáty týdne: Avi Kivity, Casey Schaufler, Alan Cox, Larry McVoy

A děláme spoustu chyb. A když je opravíme, musíme udržovat chybovou kompatibilitu, abychom umožnili živou migraci mezi chybnou a opravenou verzí. Pokud se někdy budete cítit moc šťastní, zkuste pracovat na kompatibilitě v qemu a to z vás vycucne životní sílu tak na rok nebo dva dopředu.

-- Avi Kivity

Vývojáři aplikací jsou historicky netolerantní vůči systémům, které jim za běhu mění bezpečnostní politiku. Nebo když to řeknu přesněji: Nenávidí je s neuvěřitelným zápalem. Někdy je to kvůli požadavkům systému nutné, ale nemyslete si, že vám za to vývojáři aplikací poděkují.

-- Casey Schaufler

Krátkodobě je jednodušší čůrat do rybníka, než stavět záchod – v dlouhodobém měřítku to ale tak dobrý plán není.

-- Alan Cox

Pokud spustíš benchmark a nevíš, jaká bude odpověď, a to alespoň s činitelem 10, ještě lépe 2, neměl bys ten benchmark spouštět. Teda možná že jo, jsou zábavné. Ale rozhodně bys neměl publikovat výsledky, pokud si nejsi jistý, že jsou správné.

-- Larry McVoy

list_sort() – řazení spojových seznamů

Jádro má již dlouhou dobu sadu standardních funkcí pro manipulaci se spojovými seznamy. Co mu ale chybělo, je funkce pro řazení těchto seznamů. Tedy, to není přesné, ve skutečnosti má dvě: Jednu v kódu přímého vykreslování, druhou v souborovém systému UBIFS. Když Dave Chinner zjistil, že potřebuje stejnou funkci v XFS, rozhodl se, že přidat třetí implementaci není úplně nejlepší nápad.

Místo toho tedy Dave vzal verzi z UBIFS a přepracoval ji do patche pro obecné list_sort(). Výsledkem je tato funkce:

void list_sort(void *priv, struct list_head *head,
               int (*cmp)(void *priv, struct list_head *a, struct list_head *b));

Tato funkce se chová jako mnoho obecných nástrojů pro řazení – funce cmp() je volána s parametry, kterými jsou páry prvků seznamu (a daným ukazatelem priv); měla by vrátit celočíselnou hodnotu, která značí, jestli se první položka má zařadit před druhou, nebo za ni.

Existující uživatelé této funkcionality změnu schválili, takže se téměř určitě objeví v 2.6.34.

Omezení sítě

Nové vlastnosti týkající se bezpečnosti mohou být postiženy „zákonem nezamýšlených důsledků“, protože zdánlivě jednoduché omezení může narazit na neočekávané interakce s dalšími částmi systému – často na jiné bezpečnostní mechanismy. Tyto interakce může být obtížné ihned zaregistrovat, takže když jde o přidávání bezpečnostních vlastností, jaderní vývojáři jsou velmi opatrní. Nedávný návrh, který by umožnil procesům omezit vlastní přístup k síti – což by mohlo být užitečné například pro procesy v sandboxu – na nezamýšlené důsledky narazil. Námitky ale také vyvolala ad hoc povaha této vlastnosti a její ladění pro specifický případ využití.

Základní nápad je poměrně jednoduchý. Michael Stone by chtěl mít k dispozici prostředky, kterými by proces mohl omezit svá vlastní práva tak, aby již nemohl vytvářet síťová spojení. Jedná se v podstatě o jednosměrnou bránu, která by procesu (a jeho případným potomkům) omezila přístup k síti pouze na dříve navázaná spojení. Protože Michael zamýšlí používat tuto funkci na desktopu – specificky v některých částech bezpečnostního modelu Bitfrost OLPC – pro pojmenované sockety AF_UNIX by platila výjimka, aby omezené procesy stále byly schopné komunikovat s X serverem.

Když tento nápad poprvé navrhl v RFC v lednu 2009, použil Michael přímočarý přístup s použitím limitů využívání zdrojů. Přidal nový pravdivostní limit (RLIMIT_NETWORK), který mohl proces použít, aby vypnul další síťovou aktivitu. Problém v tomto schématu byl v tom, že proces ve skutečnosti omezen nebyl, protože se mu nezabránilo použít ptrace(). Zneužitý proces by tedy mohl stále síť používat pomocí jiného procesu tak, že by na něj použil ptrace().

Krom toho James Morris poznamenal, že možným řešením tohoto problému by mohly být síťové jmenné prostory. Po tomto kole komentářů se Michael v prosinci vrátil s aktualizovanou sadou patchů. Problém s ptrace() vyřešil tak, že přidal test na omezení zdrojů do __ptrace_may_access(), který by procesům, jejichž práce se sítí je omezená, zabránil ptrace() použít. Také poznamenal, že použití síťových jmenných prostorů nepodporuje jednu z podmínek nasazení: Procesy v privátním jmenném prostoru by se už nemohly připojit k X serveru pomocí socketů AF_UNIX.

Použití limitu využívání zdrojů nepřijal správce glibc Ulrich Drepper (řešit rozšíření pro rlimit je problematické), který místo toho navrhl použít prctl(). Michael se rychle objevil s další verzí patche, která používala prctl(), ale zde vyrašilo několik problémů.

Na první pohled se odebrání práva používat síť zdá jako neškodný způsob, jak se proces může vzdát části svých práv. Když se to ale spojí se setuid() binárkami, které očekávají, že síť budou moci používat, věci se zesložití. Jak to řekl Eric W. Biederman: Teoreticky můžeš zmást aplikaci, která má nastaveno suid root a způsobit, že se svými zvýšenými právy provede nějakou akci, která porušuje bezpečnostní politiku. To je důvod, proč jsou pro vstup do nového jmenného prostoru vyžadována oprávnění (stejně jako pro věci jako chroot()), protože mohou narušit to, co předpokládají setuid() programy.

Michael nicméně hledá mechanismus, který nevyžaduje privilegovaný proces, proto jako rozhraní navrhoval omezení zdrojů a prctl(). Tato rozhraní ale neřeší problém se suid programy. Během diskuze o Michaelově návrhu byla několikrát zmíněna „chyba sendmailu a kvalifikací“ [sendmail capabilities bug], která je konkrétním příkladem toho, jak se může interakce mezi bezpečnostními mechanismy nepříjemně projevit. Chyba byla v jádře, ale manipulováním s kvalifikacemi před spuštěním sendmail (který běží se setuid(0)) dokázali útočníci obejít separaci privilegií, kterou se sendmail snaží vynutit. Přidání nového bezpečnostního mechanismu (kvalifikací) tedy náhle – chybně – změnilo chování dobře zavedené bezpečnostní techniky.

Když necháme chyby implementace stranou, některým vývojářům se nelíbí, že se podpora pro tuto vlastnost rozhazuje na různá místa v jádře: Do ptrace(), síťového stacku, obzvláště to, že změny vyžadují výjimku u AF_UNIX. Alan Cox to řekl takto:

Toto je bezpečnostní model a jako bezpečnostní model by to mělo používat LSM. Jak to vidím já, již nyní můžeš použít SELinux a podobné, ale tím neříkám, že nemůžeš poslat malý samostatný bezpečnostní modul pro lidi, kteří nechtějí používat velké bezpečnostní moduly.

Jinak budeš do rychlých cest přidávat bordel, který nikdo nepotřebuje, ale všichni za něj budou platit. A také podivné testy a hacky pro rodinu adres a podobně do vnitřního kódu síťování.

Fakt, že ten patch vypadá naprosto hnusně, by ti měl něco říct – to, že používáš špatné kladivo.

Přechod k řešení založenému na LSM bohužel znovu otvírá plechovku červů skládání LSM, jak to nazval Valdis Kletnieks. V současnosti není žádný obecný způsob, jak v jádře používat několik LSM zároveň. Tento nápad se objevil již několikrát, ale povolit to vyvolává vážné obavy ohledně bezpečnosti. Každý nový LSM pravděpodobně nebude příliš využíván, přinejmenším v distribucích, které již nyní používají „monolitické“ bezpečnostní moduly jako je SELinux, TOMOYO nebo AppArmor mimo strom. V jiném vlákně na linux-kernel se Michael ptal na používání LSM a vyjádřil tuto obavu:

Bohužel nemám pocit, že mohu tyto háčky použít efektivně, protože se mi zdá, že jsou „obsazeny velkými frameworky pro vynucování přístupu“.

Vývojář SMACK Casey Schaufler s ním v podstatě souhlasil, ale i tak mu doporučil, aby použil řešení založené na LSM:

Jsi pro to skládat malé bezpečnostní moduly. To je cesta, která byla v minulosti poměrně pevně zablokována, ale která se vždycky objeví, když se objeví někdo jako ty a chce použít modul, který slouží specifickému účelu. Námitky většinou přijdou od lidí, kteří ti řeknou, že něco jiného již dělá to, co se pokoušíš udělat, a že stačí jenom vypořádat se s celým jejich monolitickým přístupem a budeš spokojený.

Na 100 % stojím za tebou. Použij LSM. Tvůj modul je přesně to, proč tu požehnanou věc máme. Jakmile budeme mít dostatečně velkou sbírku jinak nepropojených LSM, potřeba jejich skládání bude dostatečně zjevná k tomu, abychom byli schopni to zajistit korektně.

Mít obavy ze skládání bezpečnostních modulů má dobré důvody, ale ty se většinou objevují kvůli pokusům zkombinovat věci jako SELinux a TOMOYO a ne malé jednoúčelové moduly. Serge E. Hallyn varoval, že problém je v tom, že kombinace libovolných dvou bezpečnostních politik může snadno mít jemné, nepředpokládané, ale nebezpečné efekty. Také ale upozornil na to, že jsou způsoby, jak skládání „zakódovat napevno“ s pomocí dalších vývojářů LSM:

U tvého modulu bych doporučil držet se cest LSM pro kvalifikace. Můžeš poskytnout volitelný samostatný LSM, který se háčkuje jenom do tvých funkcí. Potom může tyto funkce zavolat například smack ze svých vlastních háčků nebo může jednoduše explicitně ve smack_ops přiřadit své háčky do tvých funkcí. Selinux může udělat to samé, i když mám podezření, že ti by mnohem pravděpodobněji implementovali své vlastní funkce pro tvá nově zaháčkovaná místa.

I když Michael proti tomuto návrhu v principu nic neměl, poznamenal, že to vyžaduje, aby ostatní změnili svůj kód, což je něco, čemu se chtěl vyhnout:

Nezdá se ti poněkud podivné doporučovat, aby všichni, kdo používají těch pět bezpečnostních háčků, které chci použít já, detailně modifikovali svůj kód, aby podporovali moji funkcionalitu, vzhledem k tomu, že jejím účelem je přesně to, aby to nevyžadovalo práci na jejich straně?

Upřímně mi to přijde poměrně hloupé, a to ani nezmiňuji, že je to drahé a náchylné k chybám.

Další alternativou pro zajištění omezení je použít SELinux, což navrhl Kyle Moffett: Pokud nyní nepoužíváš SELinux (a tím pádem nemáš žádnou existující politiku), pak je v podstatě velmi přímočaré (relativně řečeno) nastavit ho pro tvůj konkrétní cíl. Následně naznačil schéma politiky SELinuxu, které by vynutilo omezení sítě. Casey byl k tomuto přístupu skeptický – přičemž podotkl, že ho pobavilo, že propagátor SELinuxu o výchozích politikách řekl, že jsou fantasticky komplikované, což Kyle udělal. Casey očekává, že kompletní politika, která by umožňovala Michaelovi nastavit to, co potřebuje, by byla sama o sobě poměrně komplikovaná:

Jsem ochoten vsadit všechno pivo, co vypiješ na posezení, že tato politika by byla větší, než navrhovaný LSM. A můžeš to počítat v bytech i v řádcích.

Mezitím Michael navrhl ještě další verzi, která používá háčky LSM. Vlastnost je stále povolována pomocí prctl(PR_SET_NETWORK, PR_NETWORK_OFF), ale implementaci zajišťuje LSM disablenetwork. Stále ale nezmizel problém s tím, že síť může být odebrána programům se setuid(), které jsou spuštěny z omezeného neprivilegovaného programu. Někdo to nepovažuje za skutečný problém, protože síť může zmizet i z jiných důvodů (vytažený síťový kabel, dostatečně nízký limit pro otevřené soubory atd.), ale jiní jako Pavel Machek, který dal patchi NAK, nesouhlasí a naznačují možné, i když nepravděpodobné situace, které by mohly způsobit problém.

To vedlo Erica k návrhu mechanismu, který by umožnil procesům zavolat prctl(PR_SET_NOSUID) a tím si trvale znemožnit spouštět setuid() programy (podobně jako připojovací volba MNT_NOSUID). Každý proces, který by to udělal, by si klidně mohl znemožnit i přístup k síti. Krom toho by to potenciálně umožnilo udělat ze vstupu do privátních jmenných prostorů neprivilegovanou operaci, protože jmenné prostory trpí některými ze zmíněných problémů, které se týkají setuid() programů.

Ericův patch ale opět implementuje určitý bezpečnostní model, což přísluší LSM, alespoň podle Alana Coxe: Další hezký příklad toho, proč máme bezpečnostní háčky, je, abychom neměli jádro plné jiných hacků pro ,náhodné bezpečnostní nápady dne‘, což nás opět zavádí k problému skládání bezpečnostních modulů. Jako Casey si nicméně Alan podle všeho myslí, že na skládání modulů nakonec dojde:

Ano, možná to znamená, že háčky potřebují trochu vyladit, ano, pravděpodobně to znamená, že lidé, kteří to potřebují, musí udělat nějakou triviální práci na skládání. Ale vzhledem k tomu, že o to má mnoho lidí zájem a mnoho lidí má náhodné nápady jako ,přidejme tlačítko, které ve středu zakáže číst ze sériového portu‘, neměl by být nedostatek lidí, kteří to udělají dobře.

Částí problému je to, že Linux podporuje spoustu bezpečnostních mechanismů: setuid(), kvalifikace, LSM, monolitické LSM, jako je SELinux, bezpečnostní bity [securebits] (ty byl zmíněny jako možné řešení PR_SET_NOSUID), seccomp a další. A chyba sendmailu a kvalifikací ukázala, že se mohou neočekávatelně ovlivňovat. Přidání specifického tlačítka, ať už bude zakazovat síť, nebo setuid(), řeší jenom jeden konkrétní problém, ale potenciálně může mít negativní dopad na celý systém.

Není zrovna zřejmé, že by mohlo vést k dalším bezpečnostním problémům, kdyby měly programy, které neběží pod rootem, možnost zahodit část svých práv. Hlavní příčinou může ve skutečnosti být setuid(), ale tento mechanismus je do unixového programování tak zakořeněn, že se v podstatě nedá dělat nic jiného, než s ním žít – bez příkras. Bude ale čím dál tím větší tlak na to poskytnout způsoby, jakými by procesy sebe (a jiné) mohly uzavřít do pískoviště [sandbox]. Změny v seccomp, které navrhl Google pro svůj prohlížeč Chrome v květnu, mohou být dalším způsobem, jak k problému přistoupit.

I se všemi konkurujícími si – a občas soupeřícími – bezpečnostními mechanismy lze snadno dospět k názoru, že co se bezpečnosti Linuxu týče, je potřeba udělat víc práce na infrastruktuře. Pokud se obavy o zobecněném skládaní LSM týkají pouze monolitických bezpečnostních modulů, lze si snadno představit nějaký druh „LSM Lite“, které by používaly stejné háčky, ale jejich chování by bylo omezeno tak, aby takové moduly bylo možné skládat. Tato omezení by možná bylo možné implementovat pomocí nějakého důvěryhodného démona v uživatelském prostoru, který by měnil kvalifikace běžících procesů. Zatím není jasné, kam věci zamíří, ale je zjevné, že uzavírání do pískoviště je něco, co lidé chtějí, a že k tomuto problému existují přístupy, které Linux ještě nepodporuje.

Shlukování využité paměti

Dlouho známý problém fragmentace paměti byl na těchto stránkách probírán mnohokrát. Ve zkratce: Když systém běží, stránky jsou rozhazovány mezi uživatele a tím se ztěžuje nalezení skupiny fyzicky spojitých stránek, když jsou zapotřebí. Vyhýbání se alokacím vyšších řádů (vícestránkových) tam, kde je to jen možné, byla věnována spousta práce; výsledkem je, že většina funkcí v jádře fragmentací nijak netrpí. Jsou ale stále situace, kdy jsou alokace vyššího řádu zapotřebí; kód, který takové alokace potřebuje, na systému s fragmentovanou pamětí může selhat.

Zde je dobré poznamenat, že problém se zhoršuje. Současné procesory nejsou omezeny na 4k stránky; mohou pracovat s mnohem většími („obrovskými stránkami“) v některých částech adresového prostoru procesu. Používání obrovských stránek může mít velké výkonnostní výhody, které většinou plynou z omezení tlaku na TLB [translation lookaside buffer]. Aby takové stránky ale bylo možné použít, musí systém najít fyzicky spojitou oblast paměti, která nejenom že musí být dostatečně velká, ale také správně zarovnaná. Na systémech, které už nějaký čas běží, to může být poměrně složité.

Během let se vývojáři pokoušeli různými způsoby problém zmírnit; výsledkem byly techniky jako ZONE MOVABLE a uvolňování po kusech [lumpy reclaim]. Stále toho ale lze udělat více, obzvláště pokud jde o to napravit fragmentaci a získat tak větší kusy paměti. Poté, co si v této oblasti dal chvíli pauzu, se Mel Gorman nedávno vrátil s novou sadou patchů implementující shlukování paměti [memory compaction]. Zde se v rychlosti podíváme na to, jak tento patch funguje.

Představme si velmi malou oblast v paměti, která vypadá nějak takto:

Bílé stránky jsou zde volné, zatímco červené jsou alokované k nějakému použití. Jak je možné vidět, zóna je poměrně fragmentovaná a neobsahuje spojité bloky větší než dvě stránky; jakýkoliv pokus alokovat, řekněme, čtyřstránkový blok z této zóny selže. Selžou dokonce i dvoustránkové alokace, protože žádný volný pár není správně zarovnán.

Je čas zavolat shlukovací kód. Tento kód spustí dva oddělené algoritmy; první začne na začátku zóny a vytvoří seznam alokovaných stránek, které lze přesunout:

Zároveň s tím začne od konce zóny druhý algoritmus vytvářet seznam volných stránek, které lze použít jako cíl pro migraci stránek:

Tyto dva algoritmy se nakonec setkají někde uprostřed zóny. V tu chvíli v podstatě stačí pouze zavolat kód pro migraci stránek (který již není jenom pro NUMA systémy) a přesunout použité stránky do volného místa na konci zóny, takže vznikne takovýto pěkný obrázek:

Nyní máme hezký, osmistránkový kus volného místa, které lze využít k uspokojení požadavků na alokace vyššího řádu, pokud bude potřeba.

Obrázek je samozřejmě významně zjednodušený oproti tomu, co se bude dít na reálném systému. Oblasti paměti budou pro začátek mnohem větší; to znamená víc práce, ale volné oblasti budou také mnohem větší.

Tohle vše ale bude fungovat jenom v případě, že zmíněné stránky bude možné přesunout. Ne všechny je totiž možné přesouvat libovolně; přesouvat lze jenom ty, které jsou adresovány nepřímo a které nejsou nijak přišpendleny. Lze tedy přesunout většinu stránek v uživatelském prostoru – přistupuje se k nim přes virtuální adresy; jenom je potřeba poladit relevantní záznamy v tabulce stránek. Většina paměti, kterou používá jádro, se přesouvat nedá – i když část ní je možno získat zpět uvolněním na vyžádání. Je zřejmé, že na zničení spojitého kusu paměti stačí, aby v něm byla jedna nepřesunutelná stránka; dobrá zpráva zde ale je ta, že jádro se již nyní snaží oddělit přesunutelné a nepřesunutelné stránky, takže nepřesunutelné stránky by v reálu měly být menším problémem, než by se mohlo zdát.

Spuštění shlukovacího algoritmu je možné dvěma způsoby. První je zapsat číslo uzlu do /proc/sys/vm/compact_node, což vyvolá shlukování na zadaném NUMA uzlu. Druhá možnost nastane, když se systému nepodaří alokovat stránku vyššího řádu; v takovém případě bude shlukování spuštěno jako preferovaná alternativa k uvolňování stránek přímým znovuzískáváním [reclaim]. Když není spuštěn explicitně, algoritmus shlukování se nevykonává; přesouvání stránek je drahé a pokud to není potřeba, je nejlepší se mu vyhnout.

Mel zkusil několik testů, které ukázaly, že když je shlukování povoleno, byl schopen alokovat přes 90 % systémové paměti jako obrovské stránky, přičemž se zároveň snížila nutnost znovuzískávat. Vypadá to jako užitečný kousek práce. Když ale jde o kód správy paměti, nikdy nelze snadno odhadnout dobu, která bude potřeba na začlenění do hlavní řady.

RCU řetězce

Na mechanismu sysctl se v nedávných vývojových cyklech hodně pracovalo, což vedlo k odstranění spousty kódu a omezení používání Velkého jaderného zámku [Big Kernel Lock]. Ukazuje se ale, že tato práce také zavedla nějaké jemné a velmi ojedinělé souběhy do práce s řetězci, které jsou exportovány do uživatelského prostoru. V reakci na to dal Andi Kleen dohromady nový koncept nazvaný „RCU řetězce“ [RCU strings], který k odstranění souběhů používá mechanismus čtení-kopírování-aktualizace [read-copy-update] a zároveň nezavádí do cesty čtení žádný zámek navíc.

Pomocí sysctl se spravuje mnoho řetězců. Příkladem budiž request_module(), kterou jaderný kód používá, aby od uživatelského prostoru vyžádal zavedení modulu. Volání request_module() vede na spuštění modprobe, ale nikdo nechce zadrátovat jméno ani umístění modprobe do jaderného kódu. Proto existuje sysctl proměnná /proc/sys/kernel/modprobe, která obsahuje umístění tohoto nástroje. Na téměř všech linuxových systémech bude nastavena na /sbin/modprobe, ale administrátor ji může změnit, pokud je potřeba.

Zvažme případ, kdy je request_module() voláno přesně ve stejnou chvíli, kdy se /proc/sys/kernel/modprobe mění z uživatelského prostoru. Je tak snadno možné, že request_module() skončí s cestou k modprobe, která je napůl změněná. Nejpravděpodobnější výsledek je selhání při pokusu o nahrání modulu, ale mohou se stát i horší věci. Takové situaci je nejlepší se vyhnout.

(Zde je vhodné poznamenat, že souběhy obecně nejsou považovány za potenciální bezpečnostní problém. Změna proměnných sysctl je privilegovaná operace, takže ji není možné provést z libovolného uživatelského účtu.)

Mechanismus čtení-kopírování-aktualizace zajišťuje, aby data – obzvláště často čtená, ale málokdy měněná data – zůstala při používání stabilní. Pro ochranu sysctl řetězců se tedy tento mechanismus zdá být ideálním řešením, protože tyto řetězce se s největší pravděpodobností za běhu systému vůbec měnit nebudou. RCU může být nicméně trochu složité použít; aby se věci trochu zjednodušily, byl navržen typ RCU řetězec.

RCU řetězec je vytvořen takto:

#include <linux/rcustring.h>

char *alloc_rcu_string(int size, gfp_t gfp);

Parametr size by měl být maximální velikost, kterou může řetězec mít – včetně nuly na konci.

Čtení řetězce se drží normálního vzoru pro RCU a používá se ukazatel na daný řetězec. Atomickému čtení – takovému, které nespí – stačí použít rcu_read_lock() a rcu_dereference(), čímž se dá najevo, že používá RCU chráněný ukazatel. Kód, který by spát mohl, musí použít jiné prostředky, protože řetězec by se mohl změnit, když kód neběží. V takovém případě je vytvořena kopie řetězce:

char *access_rcu_string(char **str, int size, gfp_t gfp);

Zde je str ukazatel na ukazatel na řetězec a size je velikost původně alokovaného řetězce. Použití strlen() k získání size je vážná chyba, protože se před vytvořením kopie může řetězec změnit. Nový řetězec je alokován pomocí kmalloc(); dané gfp jsou příznaky použité pro alokaci. Když už není potřeba, měl by být zkopírovaný řetězec uvolněn pomocí kfree().

Kód měnící RCU řetězec by měl použít alloc_rcu_string(), kterým se alokuje nahrazující řetězec, následně do něj zkopírovat data a poté použít rcu_assign_pointer(), kterým se nový řetězec zviditelní pro zbytek systému. Starý řetězec by měl být předán free_rcu_string(), která použije RCU a uvolní paměť, když se ví, že na daný řetězec už nemohou být žádné odkazy.

Řetězcové proměnné bývají pomocí sysctl exportovány použitím proc_dostring(). Aby lidem zjednodušil život, přidal Andi novou funkci proc_rcu_string(), která řeší většinu detailů exportování RCU řetězce. Jde o jednoduchou záležitost inicializace odpovídající struktury ctl_table ukazatelem na ukazatel na řetězec char ** a nastavení záznamu proc_handler na proc_rcu_string(). Počáteční hodnota řetězce může být konstanta v době překladu; od všeho ostatního se očekává, že to bude RCU řetězec.

Kód prošel několika koly revizí a pravděpodobně bude začleněn ve vývojovém cyklu 2.6.34.

Diskuse k tomuto článku

[stativ]

Se skoro až divím, že s defragmentací paměti takovýmto způsobem někdo přišel až teď…

[Martin Böhm]

Nevim, z jake nazorove i akademicke skoly je prekladatel, ale "sort" je ve vsech akademickych i odbornych kruzich vzdy prekladano jako "trideni". Ac (zcasti) nepresne, je to termin a ten by se mel takhle prekladat.

(Mimochodem Wikipedia tohle dela taky blbe, doporucuji se podivat napriklad do stare dobre ceske ucebnice programovani od pana docenta Topfera.)

[Ladicek]

Vždy určitě ne, u nás se říkalo normálně řazení. Ale holt plzeňská univerzita, no Wikipedie (aspoň ta česká) to podle mě říká stručně a jasně a správně.

[Martin Böhm]

Original research, takze spatne i podle jejich kriterii. Viz Topfer.

[Ladicek]

Dal jsem tomu asi dvě minuty (víc nehodlám) a uwarezit se mi to nepodařilo. Jakým způsobem docent Topfer vysvětluje, že mezi relacemi ekvivalence a uspořádání není rozdíl?

Co konkrétně považuješ za original research? Už jsem říkal, že u nás se normálně používalo slovo řazení. Můžeš se teda začít hádat, že jakási provinční univerzita není zdaleka tak významná jako přední světové zdravotnické orgranizace, pardon, MFF, , ale nedělal bych z toho takovou kovbojku.

Argumenty se najdou pro všechno i proti všemu. Přestávám mít rád argumenty.

[stativ]

To, že přednášející (předpokládám) používá název třídicí algoritmy neznamená, že je to jediný správný termín.

[Martin Böhm]

Ha ha, Topfer mi uz neprednasel par let, a predtim jsem tam taky vubec nechodil.

Jde spis o knizku, kterou napsal, a kterou aspon mi MFFaci (+ KSPaci) vidime jako jednu z hlavnich ucebnic algoritmizace (fuj slovo) u nas.

[cronin]

Daleko viac mi vadil preklad "compaction" (tusim, ze ten termin je v originali) ako "zhlukovanie", pretoze pod zhlukovanim sa mi vybavuje vyhradne "clustering", a to v zmysle matematickej statistiky a dolovania v datach, nie v zmysle IT.

Ale nakoniec, vsetci sme predsa pochopili, o co ide, tak sa povznesme nad drobne terminologcke nezrovnalosti a podakujme za dalsie skvele Jaderne noviny.

[trekker.dk]

Daleko viac mi vadil preklad "compaction"

To mě taky. Máš lepší nápad? Šup sem s ním.

[trekker.dk]

Představ si hromadu bordelu. Ty se do ní pustíš a začneš třídit, takže po chvíli práce máš sklo, papír a plasty, což jsou vlastně tři menší hromady bordelu.

Já se do ní pustím a za chvilku mi vzniknou Hospodářské noviny, igelitový sáček, Kapitál ((c) Marx), láhev od piva, víčko od PET lahve a láhev od vína - takže mám řadu, kde pozice každých dvou po sobě jdoucích položek je určena nějakým vztahem. V tomto případě jsem je seřadil podle abecedy.

[Martin Böhm]

Ja se nehadam, ze to je spatny preklad co do fakticnosti. Mozna dokonce i lepsi. Ale 'trideni' je uz (podle mne) dostatecne zazite a dostatecne zabydlene, ze nema smysl zavadet nosocistopleny.

[Martin Böhm]

Mimochodem, vsimni si, ze slovo "nosocistoplena" popisuje funkci kapesniku mnohem lepe nez slovo "kapesnik", ktere jen urcuje jeho pozici (kapesnik by klidne mohl byt treba nuz).

[Petr Tomášek]

Aneb kdybychom na to šli etymologicky, pak „třídit“ znamená „rozdělit do tříd“, kdežto „řadit“ značí „uspořádat do řady“ :-P

(Ale já vím, že jazyk „etymologicky“ nefunguje, takže je to vlastně jen taková blbost a intelektuální hříčka

[stativ]

Určitě? I v literatuře jsem se většinou setkal s pojmem řazení. Jako třídění beru (a přijde mi to i logičtější) případ, kdy prvky mezi sebou neporovnávám v ohledu který je „menší“ a který je „větší“ ale v ohledu zda patří do skupiny A_1, A_2…

[Martin Böhm]

V ktere literature? A hlavne: v literature "napsane" prekladatelem nebo programatorem?

[Martin Böhm]

Protoze v "literature" jsem videl i takove skvosty jako "hromada" pro "heap", prelozene zdrojaky (int hlavni(void)) a tak dale.

[stativ]

Protoze v "literature" jsem videl i takove skvosty jako "hromada" pro "heap", prelozene zdrojaky (int hlavni(void)) a tak dale.

Díky, tomu jsem se fakt zasmál

[stativ]

Pokud si vzpomínám, tak přinejmenším v nějaké knize od computer pressu jsem to viděl. Jinak schválně jsem si porovnal počet výsledků na „řadicí algoritmy“ a „třídicí algoritmy“ na Googlu. Zvláštní je, že „řadicí algoritmy“ mají ca 2x tolik výskytů… A další zajímavost – pro „třídicí algoritmy“ je podezřele velká množina stránky z MFF…

[Martin Böhm]

Pouzivat google jako etalon asi neni uplne to nejchytrejsi. Treba pomer slov "soft halda" vuci "mekka halda" je nejaky (u mne asi 270 000:100 000) ale to je uplne jedno, protoze ani jeden neni o "soft heaps". :o)

(Ja vim, soft heap tady nikdo nezna, trideni zna kazdy bakalar informatiky. Ale aspon trochu to doufam ten argument ilustruje.)

[stativ]

Uznávám, že Google není nejlepší ukazatel (teď navíc koukám, že jsem se přehlédl a „řadicí algoritmy“ mají jen ca o čtvrtinu víc výsledků). Ale rozhodně to ukazuje, že třídicí algoritmy nejsou jediný zažitý termín, což se mi zdá, že se tu snažíte dokázat. Všechno ukazuje na to, že je to jen jeden ze dvou používaných termínů. A osobně si myslím, že ten horší, protože nevystihuje pravý účel tak dobře.

PS. řazení nejsou soft heaps a zdá se, že výsledky jsou opravdu relevantní.

[lukyjoe]

Řazení je jeden ze způsobů třídění. Nemá smysl mluvit o dobytku, když máš na mysli jen a právě krávy. Tečka.

[Martin Böhm]

Řazení je jeden ze způsobů třídění.

A to jsi slysel kde?

[Petr Tomášek]

Kua, to se nedá číst. „Plechovka červů skládání LSM“? WTF? „LSM, který se háčkuje ... do funkcí“?

To si na to nemůžete pozvat skutečného překladatele?

[lukyjoe]

Já sice někdy zaváhám, ale obecně jsem s těmi překlady nadmíru spokojen. Někdy je potřeba vědět o čem je řeč, ale třeba v tom, co cituješ, nevidím problém. Každopádně se s námi klidně poděl o lepší a přesnější překlad s odůvodněním a redakce k němu jistě ráda přihlédne.

[Robert Krátký]

Navrhuji, abys na zkoušku přeložil pět dílů. Když se pod těmi články neobjeví žádný komentář kritizující úroveň překladu, zamyslím se nad tvým návrhem.

[trekker.dk]

Jů, měsíc volna (a výhledově ještě víc.) Já jsem pro (hlavně mi to ale řekněte včas )