Mazání dat uprostřed souboru

http://man7.org/linux/man-pages/man2/fallocate.2.html

Protože diskový soubor je sekvence bloků pevné délky. Potřeba smazat soubor by jen zřídkakdy vycházela tak, aby to padlo na hranici bloků. Tudíž by to nebyla efektivnější operace, než to udělat z user programu pomocí zkopírování soubory za mazaným oknem.

Pokud je třeba častěji mazat uprostřed souboru, dělá se to tak, že soubor se myšlení rozdělí do sekvence kratších binárních kousků, tzv. chunků. Ty se uloží do jednoho souboru, nebo každý zvlášť do zvláštního souboru. A na začátku, nebo uvnitř chunku je mapa, jak za sebou pokračují. Smazání chunku uprostřed souboru je pak triviální operace, jednouše změna jednoho pointeru (32, nebo 64 offsetu) v mapě jako ukazatele na další chunk v pořadí.

Operační systém obvykle neimplementuje věci, které se stejně efektivně dají udělat z user space. Stejně jako linux kernel neimplementuje třeba Newton-Rapsonovu metodu pro hledání kořenů rovnic.

Operační systémy zkrátka implementují takovou množinu operací se soubory, které dovolí efektivní práci z programu.

Funkci nazvanou třeba:

int ferase(int handle, off_t start, off_t size)

si můžete velmi snadno naprogramovat sám a používat.

Kromě toho operace smazání části souboru uprostřed se používá minimálně. Při návrhu struktur a algoritmů programu se lidé snaží takové operaci maximálně vyhnout, protože je velmi neefektivní a nedá se udělat rozumně zaručeně atomicky.

Miloslav Ponkrác

Mazání dat uprostřed souboru šlo dlouho jen jako "ražení děr", nicméně od 3.15 kernelu máme fallocate flag FALLOC_FL_COL­LAPSE_RANGE, který dodává chybějící funkcionalitu. :)

Zajímavé. A něco na přifouknutí bloků doprostředka by tam nebylo? :-)

Mozna tohle:

fcntl(2):

F_FREESP

Free storage space associated with a section of the
ordinary file fildes. The section is specified by a
variable of data type struct flock pointed to by arg.
The data type struct flock is defined in the
header (see fcntl.h(3HEAD)) and is described below. Note
that all file systems might not support all possible
variations of F_FREESP arguments. In particular, many
file systems allow space to be freed only at the end of
a file.

Konkretne treba ZFS tohle plne podporuje.

Tahle funkce by byla VELMI uzitecna pro editaci videi nebo muziky. Ve videu se ti stane velmi casto, ze potrebujes vystrihnout kus (treba reklamu). Ovsem v aktualnim stavu veci se vystrizeni jedne sekundy z prostredka rovna zkopirovani nekolika giga z jednoho mista disku na druhe.
Fragmentace neni problem, protoze mpeg podporuje vyplnovani mezer, takze kdyby bylo potreba vystrihnout napriklad 66000 bytes, tak 64kilo (65536) se vystrihne fyzicky a zbytek (464) se vyplni podle standardu mpegu.
Samozrejme zustava problem s atomicnosti teto operace, ale to by se dalo resit prehazovani bloku v souboru a hardlinkama = ve smyslu sdileni inodu mezi vice soubory.

Nejak takhle:
Mam file tvoreny inodama 10 11 12 13 14 15 16. Chci vystrihnout kus kolem bloku 13. Vyrobim novy file s inodama 10 11 20 15 16 - v inode 20 je zkopirovany zacatek inode 12 a konec inode 14 a vypln toho co zbylo do velikosti bloku. Az je to hotovo, prejmenuju puvodni file na ten novy. Tim se zrusi puvodni file a bloky 12 13 14 se uvolni, protoze je uz zadny dalsi file nepouziva. ostatni bloky zustanou alokovane.

Netusim, jestli tyhle operace nektery filesystem podporuje, ale predpokladam, ze jo. Vicemene staci, abych mel moznost zjistit ktere inody tvori muj puvodni file a abych mohl vyrobit novy file, kteremu ja reknu ze kterych inodu ma byt slozeny.
Ostatni operace ktere potrebuju jsou jenom seek, read a write, abych mohl vyrobit obsah toho meho inode 20 z minuleho prikladu.

Aha, tak to jsem rad, ze uz to je v jadru aspon od 3.15 (pro XFS), to jsem nevedel, ja jsem zatim zamrzl na longterm jadru 3.14

Stejne se divim, ze to implementovali az ted, po padesati letech ...

[2]: programatori se tomu vyhibaji prave proto, ze optimalne mazat data uprostred souboru nejde. Teda neslo, ted vidim ze uz to jde pres fallocate, jak nekteri poznamenali v komentarich, coz dany problem kompletne resi.

Napise nekdo jednoduchy tool, kraticky C zdrojak, ktery vezme jako parametr jmeno souboru, offset a length, a jen zavola ten fallocate() s parametrem pro collapse? To by bylo bomba :)

[8] ... http://man7.org/linux/man-pages/man1/fallocate.1.html

Ale to pridavani by me taky zajimalo.
Randolf

[9] odpovim si sam, vpodstete WIP. Patche pro fs.c, XFS a EXT4 jsou, ostatni ne.

[10] BTW: flag se jmenuje FALLOC_FL_INSER­T_RANGE

[11]: kde je ten flag FALLOC_FL_INSER­T_RANGE definovany? V falloc.h vidim jen FALLOC_FL_COL­LAPSE_RANGE

Tak to je důvod proč byly vymyšleny (relační) databáze. Reprezentace je ve formě stromu, ten ma koncove nody stejne velikosti jako je block na disku. A pak se to řeší stejně jako operace nad stromem.
I střihání videa, co si tak pamatuji, se řeší v databázi a to i dokonce i relační s extensema (frame je řádek, ten pak má další informace jako histogram).

[12] Existuji patche (http://linux-kernel.2935.n7.nabble.com/template/NamlServlet.jtp?macro=user_nodes&user=1498), ale v hlavnim stromu to asi zatim neni.

Randolf

[13] Ale i relacni DB resi jak spravovat misto a dochazi v nich k fragmentaci. Napriklad Oracle nema zaznamy pevne delky a uz z teto podstaty dochazi k fragmentaci atd.

6. ne tak zcela. Použije se index a kopírování se dělá jen jedno. jednoduše kopíruj od 0 do 11 a pak 16 až 25.

[3][8] Já bych na vašem místě počkal s nadšením pro fallocate, protože řeší kulové. Jen se potvrzuje to, co si myslím dávno, internet je plný „odborníků“, kteří „rozumnější“ všemu. V linuxové komunitě je takových „odborníků“ desetinásobek.

fallocate dokáže smáznout oblast, ale jen, pokud mu to dovolí jeho interní struktura. Tedy třeba jen pokud je offset a délka odstraňované oblasti zarovnaná na násobek diskového bloku (512 bajtů) nebo clusteru.

Funkce fallocate nijak nezaručuje, že je schopna odstranit libovolný rozsah souboru na libovolném offsetu. A pokud vámi zvolený rozsah nedokáže, tak hezky vrátí -1 a v errno najdete EINVAL.

Na to všechno byste přišli, kdybyste alespoň elementárně prošli manuálovou stránku k fallocate.

[13][15]
Přesně tak, jak už jsem psal výš, pokud potřebujete významněji editovat a odstraňovat a přidávat bloky dovnitř souboru, pak se to rozhodně nedělá na souborové úrovni, ale pomocí stromů a stránek. Tak, jak to dělá databáze.

Fragmentace je jiná věc, a ta v tomto případě vadí méně. Protože primárně nejde o fragmentaci, ale o rychlost souborových operací.

A jak je ze sw inženýrství známo, výběr vhodné datové struktury přináší raketové urychlení, než bezhlavé a fanatické trvání na jednom způsobu, například mít video či data v jednom souboru a dělat úpravy délky vprostřed.

[18] Pro takový settopbox je fallocate ideální řešení. Není nutno implementovat komplikované datové struktury místo pouhého dumpování streamu do souboru, jen kvůli tomu, že si uživatel chce později vystřihnout v nahrávce reklamu :-)

[17] Mirku, nevim, proc se do nas hned navazis. Samozrejme, ze jsem si to prosel, a je mi jasne, ze to neni vsemocne, ale je to krok spravnym smerem. Pro konkretni ucely je to uzitecne. Samozrejme, ze je treba splnit mnoho podminek (pouziti spravneho souboroveho systemu, pohlidat si spravne zarovnani na bloky, atd.) Taky je treba posoudit, zda je pro danou aplikaci akceptovatelna velka fragmentace, ktera castym pouzitim vznika.

Nechapu, proc mas pocit, ze jsme si to neprecetli a ze jsme neschopni. To je jako bychom nasli nove implementovany malloc a Ty bys nam rekl: "no jo, ale vy jste neschopni, protoze jste si neprecetli, ze nefunugje, pokud Vam dosla alokovatelna pamet, a co teprve kdyz je fragmentovana, to se pak chova uplne nepredvidatene." To si pak od Tebe horoskopy delat nenechame :)

Randolf

[20] Já se do nikoho nenavážím. Řešení s fallocate není jenom všemocné, ale ve valné většině případů dokonce zcela nefunkční a fallocate jen ohlásí chybu. Zkuste si to, volejte fallocate, dejte mu různé meze a zjistíte, že v 99,9 % případů fallocate zahlásí, že to neumí. A to ani s tím správným souborvým systémem.

Pomíjím to, že použítím fallocate tímto způsobem vytváříte program, který bude fungovat jen na určitém souborovém systému, jen někdy, a taky musí duben a zároveň středa a ještě dojít ke trigonu Jupitera s Proximou Centauri. Pokud nebudou všechny tyto podmínky splněny, bude mít program problém.

Ne, není to řešení, a je to krok špatným směrem. Ba tím nejhorším. Namísto volby správných datových struktur a správného způsobu uložení dat, což je jediný správný krok, se snažíte používat to, co byste neměli dělat jinak, než v naproté nouzi.

Diskové soubory mají svůj způsob uložení, a ten má svá omezení. Správným směrem je neznásilňovat, ale navrhnout způsob uložení dat programu tak, aby neměly problémy s věcmi, které drhnou.

Namísto správného řešení problému si tu všichni myslí, že všechno se řeší rambovským způsobem najít větší kladivo, a pokud to nejde, najít ještě větší kladivo. S tímto přístupem je dobré kopat kanály, ale proboha neprogramujte. Dělejte ochranku, nebo někd,e kde je důležité jít proti zdi, ale nedělejte duševní práci.

Základem správného programování je správný návrh datových struktur a to včetně způsobu uložení na disku. Takový, který je pro daný problém nejefektivnější. Namísto potřeby častého mazání okna uprostřed souboru je třeba řešit: „Proč mám tak blbě navržené struktury, že takovou neefektivní operaci často potřebuji. Jak bych to měl udělat jinak, abych nepotřeboval mazat uprostřed souboru, a nebo jenom velmi výjimečně.“

A pokud už se maže uprostřed souboru okno, tak použít poněkud stabilnější způsob, který funguje i jindy, než v dubnu, a udělat to trochu robustněji, tedy nepoužít fallocate.

Víc k tomu nemám co říci. Styl: „Nejde-li to silou, půjdu to ještě větší silou“ vám zaručí, že velmi rychle skpončíte jako neschopní programátoři.

[19] Ne, fallocate není řešení ani pro vystřihnutí souboru.

fallocate je funkce pro ty, kteří vědí, co dělají. Na pro ty, kteří hledají kladivo, protože programovat neumí.

fallocate je funkce pro ty, kteří vhodně navrhnou datové struktury. Zjistí si informace o velikosti clusteru na disku, granularitě ukládání dat na disk a další a přizpůsobí tomu strukturu. Tedy ideálně pro databázové výojáře, nebo pro ty, kteří přizpůsobí diskové soubory granularitě přirozených diskových bloků. Neznalec by měl zapomenout, že nějaká fallocate existuje, nepomůže mu – nepatří do jeho rukou.

Neznalec by si měl imnplementovat vlastní funkci, které smaže okno uprostřed souboru pěkně po staru. Tedy překopíruje data v souboru od (start_block + erase_size) na pozici (start_block) a na konci pekně nastaví souborové ukazovátko handle na (old_size - erase_size) a hezky na tomto místě ukončí soubor.

Funkce fallocate je pro ty, co se přizpůsobí, tedy polopaticky řečeno, navrhnou struktury na disku správně. V jiných rukách nadělá fallocate pouze škodu. Nepoužívejte ji pro běžné souborové operace, ani tehdy, pokud nic neznáte a jste začátečníci. Není to funkce pro vás.

Nejsem nějaký expert na fs, ale neměl by tohle teoreticky fs umět?
Přece by stačilo nalézt bloky, který obsahuje to co chceme smazat. Vytvořit si nový blok, ve kterým bude to, co z těch bloků nechceme odstraňovat. A pak stačí změnit ukazatele bloků tak, aby se ty staré zahodili a nahradil je ten nový.
Akorát na tyhle akce budou potřeba použít funkce na defragmentaci, nebo přímý přístup na disk.

[23] Ale Mlho... o funkci fallocate se tu již dobrý týden bavíme.
[22] "Ne, fallocate není řešení ani pro vystřihnutí souboru."
Právě z toho důvodu - mazání dat ve videu - byla zavedena... viz příslušné mailing listy.

No já tedy nevím, ale i smazání bloku uprostřed souboru bych řešil jeho kompletním překopírováním bez odstraněných bloků. Pokud toho mám smazat víc, tak si jen sestavím soupis odstraňovaných míst a nakonec to uložím do nového souboru.

Proč?

1. Co když operace uprostřed selže? (elektřina, HW chyba, pád OS, whatever)
2. Co když uživatel smazal něco, co nechtěl?
3. Dneska pořád někdo zápasí s místem na disku?
4. Nehledě na to, že přepisování souboru posouváním bloků rozhodně není atomická záležitost

Jinak pro vážnější operace se opravdu dělá to, že se soubor rozdělí na spoustu menších souborů a s těma se pak pracuje. Tam ani nemusí být ten předmětný chunk pevné velikosti. Další možností je "interní FS" (prostě FS realizovaný uvnitř pracovního souboru na míru potřebě i třeba s možností mazat uprostřed)

[25] Samozřejmě se najdou případy, kdy to má smysl dělat složitě. A také případy, kdy ne. Číst a zapisovat gigabajty dat, když by stačily jen kilobajty. Nebo vymýšlet důmyslné datové struktury pro provedení operací, které umí zhruba udělat i filesystém.
4) To snad hrozí jen u FAT, ostatní fs mají aspoň nějaké žurnálování, a i když se nežurnáluje všechno, tak zrovna metadata ano.