9 ms·
How do I delete bytes from the beginning of a file? (2010)
- ALittleLight 7y agoI'm not sure I really understood this. If you wanted to delete 10 bytes, couldn't you just read a sector, then copy the sector back sector[10:]? Edit: then delete the last ten bytes.
- mehrdadn 7y agoYou'd have to do this for every sector in the file or increase potential fragmentation. Alternatively they could support an offset in the beginning, but it might wear out the decide much faster due to lack of alignment. In either case though I feel the capability would be nice to have regardless...
- tom_ 7y agoEach sector is a fixed size.
- memling 7y agoAt first blush, I don't think this would work quite right because the last ten bytes of the sector would have some content (e.g., zero bytes or some other data from the original sector).
- gnulinux 7y agoWhat happens to the last 10 bytes of that sector?
- maxxxxx 7y agoDoes the whole sector thing still make sense for SSDs? Do they still work by sector or can every byte be addressed directly?
- pstrateman 7y agoThe "native" sector size of an SSD is the erasure block size, typically 64KiB.
- vardump 7y agoI'm fairly sure SSD erase block sizes are more like 2 MB or more. Even 8 MB wouldn't surprise me anymore.
- rpearl 7y agocurrent SSDs are page/block oriented, but that's likely to change. (See intel's relatively recent Optane).
- throwaway98434 7y agoThe unix filesystem api doesn't provide a way to interact with sectors. The primitives are files and the methods available are writing more data, or truncating. There is no function provided for shifting the byte offset of data in a file. You can write an entirely new file, of course, but the question has an implicit goal of doing this efficiently.
- Thorrez 7y agoOnly the last sector is allowed to be partially filled. Every other sector must be fully filled.
- deleted 7y ago[deleted]
- tyingq 7y agoSee fallocate() for Linux/ext4. http://man7.org/linux/man-pages/man2/fallocate.2.html http://man7.org/linux/man-pages/man2/fallocate.2.html
- maxxxxx 7y agoIt looks like this will zero out data but not remove.
- andoma 7y agoIt will remove if you use FALLOC_FL_COLLAPSE_RANGE
- maxxxxx 7y agoBut: " A filesystem may place limitations on the granularity of the operation, in order to ensure efficient implementation. Typically, offset and len must be a multiple of the filesystem logical block size, which varies according to the filesystem type and configuration. If a filesystem has such a requirement, fallocate() fails with the error EINVAL if this requirement is violated." Seems it's limited.
- andoma 7y agoCorrect, my bad. Did some tests and AFAICT neither EXT4, XFS nor BTRFS allows arbitrary byte ranges here.
- deleted 7y ago[deleted]
- minaguib 7y agoI've written a quick tutorial on linux sparse files/fallocate and effect on different writers/readers: https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c343fa https://gist.github.com/minaguib/1cbe29922b06d50755a2f580b8c...
- LanceH 7y agoReading this, I couldn't help but try to find the rhythm of a poem to match the formatting.
- CodeMage 7y agoIt reminded me of "Hyperion" and "The Fall of Hyperion" by Dan Simmons. The way an AI called Ummon communicates with humans is rendered in a similar fashion.
- ameliaquining 7y agoI was reminded of "The Story of Mel" (https://www.cs.utah.edu/~elb/folklore/mel.html https://www.cs.utah.edu/~elb/folklore/mel.html), which was originally written as prose but got mutated through Usenet linebreaks into something that wound up looking like free verse, and is now remembered as such.
- thrower123 7y agoI realized I haven't been to Raymond's blog since this new layout was applied. It was a little jarring - it seems very stark and sterile, and there are a lot of 404'd links. I suspect it got hit in the MSDN blog purge that happened a little while back, unfortunately.
- justinc8687 7y agobr { display: none; } fixed it for me...
- blt 7y agoI guess Raymond uses a line oriented editor like vim, and the original line breaks have been preserved. If you use one line per clause, it's much easier to change sentence and paragraph structures without having to seek around by the word.
- oblio 7y agoVim's not line oriented... at least as far I know. ed/ex, now those are line oriented. But I wouldn't call vim line oriented. Unless you also want to call Notepad line oriented, since you can use Shift + End to do operations on an entire line :D
- newnewpdro 7y agoThe filesystem just needs a concept of a file start offset. The initial value is 0, if you wanted to support truncating at the head, you just add to this offset the amount truncated. In a sector-based filesystem, whenever this offset goes far enough into the file that crosses sector boundaries, you reclaim those sectors as free space. When it lands within a sector somewhere, that sector is pinned and you waste some space. The problem is more that the userspace APIs don't expose well-supported mechanisms for doing this. Implementing it at the filesystem level is trivial.
- cjhanks 7y agoI can think of a cool case for this. What if you have an append-only system which is making remote backups. One service is writing the activity log append only, a second service is reading that, check-pointing, and then truncating the head of the file when the check-point has been committed. No need to do the tricky file-swap trickery.
- firethief 7y agoJournaling filesystems do that internally.
- dmitrygr 7y agoCuriously enough. PalmOS's file streams supported this very feature: delete as i read. As you read bytes from the start of the file, they'd be deleted. You were allowed to have a concurrent writer appending to the end.
- userbinator 7y agoAs you read bytes from the start of the file, they'd be deleted. You were allowed to have a concurrent writer appending to the end. Also known as a named pipe.
- cjhanks 7y agoKind of, a pipe has a limit of 16 pages which is usually 64kb.
- bagels 7y agoIs this a problem that really needs a solution? I can't recall any times where this would have been useful to me or think of a situation where it'd be a deal breaker. I could contrive a bunch of other operations that are inefficient on file systems like this (remove every other byte from the file, why not?), but doesn't mean that literally any idea we can think up should be supported by the file system apis.
- buckminster 7y agoOne place this would be useful is a DVR. You want to record the last n hours of video and discard anything older. And it's not inefficient. It just requires a lot of careful engineering that's probably not worth the bother.
- frei 7y agoIt's unnecessary to create a filesystem-level support I think, since you could make a circular buffer holding a video stream in a file with some constant size that is approximately n hours of video. With some clever tricks you could even keep the format compatible with existing video container formats.
- eps 7y agoOr just use a set of files, each holding N minutes with, perhaps, some overlap + an index file. No real need to over-engineer things here.
- taffer 7y agoFilesystem design and operating system design is full of these kinds of questions. From Unix and Windows we are used that we can insert and delete the end of a file and that we can read, write and seek anywhere in the file, but a filesystem could potentially do much more: Inserting/deleting at the beginning or inserting/deleting in the middle. Deleting at the beginning of a file would be handy for queues or logs and inserting and deleting in the middle is a common operation for text editors. There are even more questions you could ask: - Why not have tabular files that allow indexed access? - Do we need hierarchical directories or do we need directories at all? - What about adding tags to files? - Why having a filesystem at all?
- derefr 7y agoI've often thought it would be useful (especially for software that manages container or archive file-formats, or for databases) to have exposed to the user a file-system object that operates like a file, but which—instead of being exposed by OS as a seekable byte stream that can be appended/truncated on one end—is exposed by syscalls as a vector of arbitrary, non-uniformly-sized extents, where the user is expected to ask the OS to pre-allocate extent buffers (think mmap(2) with anonymous private disk pages), and then, separately, stuff those into this vector object (which would be an operation almost exactly like hard-linking an existing file into a directory, in terms of its time and space complexity.) Of course, for most filesystems (and especially ones with sparse-file support, and especially ones with copy-on-write support), such an on-disk data structure is exactly what's already underlying the byte-stream abstraction. So this would just be a passthrough to allow people to directly manipulate that data structure. (In the process probably breaking certain preconditions the filesystem relies on, though, so it would need to track these "low-level extent vectors" as a separate filesystem object type. Programs would still be able to use regular file-abstraction syscalls on them, though.) Interestingly, despite filesystems themselves not exposing the lower-level extent-vector abstractions, in some other systems that have file-stream-like abstractions, you can operate on "files" this way. Postgres's BLOBs, for example, are seekable byte-streams, which also (at least theoretically) allow you to insert into the middle of them. (I say theoretically because it's not an implemented API, but it's not exactly hidden from the user, either. BLOBs just get broken out into records in a table representing their extents; you can rewrite the keys of said records in that table to do whatever low-level operations you like.) Or, for another example, S3 and its competitors let you arbitrarily compose objects as “components” of other virtual objects, which then read back as the concatenation of the objects they contain. (Sadly you don’t get any other vector-manipulation ops than this, but if you keep references to the leaf extents around, that’s often enough to rebuild your extent-vectors any time they change.) Also, of course, back on the real filesystem, you can just manage your "vector of parts of a file" as multiple files in a directory, and then abstract over that directory that by using a FUSE server which exposes a view where the files are one contiguous file.
- EvanAnderson 7y agoThat sounds a lot like RMS files in the VMS operating system.
- burfog 7y agoDeleting from the beginning, and the more general problem of deletion and insertion at arbitrary offsets, is very difficult to solve. Due to file mapping APIs like mmap, MMU limitations make the situation difficult. It isn't even clear if the mappings should slide or not, and what the alignment requirements for mappings might be if an insertion or deletion is not a multiple of the page size. No common filesystem has data structures that are suitable for deleting an arbitrary number of bytes from the beginning, and very few filesystems have data structures that are suited to block-aligned deletions. Hans Reiser was working on it. He created a killer filesystem called ReiserFS, which offered efficient storage of data smaller than a disk block. He was working on an API and filesystem layout for arbitrary insertions and deletions when his work got interrupted by a death in his family. Perhaps he can get back to it starting May 2020, when he might have a chance to take a break from Correctional Training Facility.
- Swizec 7y agoOh wow he’s getting out in less than a year already? Or is that just his first chance for parole?
- mises 7y ago2021, actually: https://law.stackexchange.com/questions/16180/what-is-hans-reisers-earliest-release-date https://law.stackexchange.com/questions/16180/what-is-hans-r... That's just the earliest he's eligible for parole. The interesting question will be if people are still okay accepting commits from a murderer. Most businesses don't want to hire felons; even though we ostensibly have the concept of "pay the penalty and start again", felonies tend to be too egregious. I wonder what the Linux maintainers will do with respect to that.
- mattgrice 7y ago"work got interrupted by a death in his family?" He was found guilty of 1st degree murder of his wife.
- zorpner 7y agoHe created a killer filesystem... The principle of charity requires that I assume this is the most macabre, driest sense of humor I've ever encountered. Damn.
- davidork 7y agodunno about windows, but in llinux its fairly simple. I've had to do do this a lot of this sort of thing on big disk images my friend made with some weird program that pads the start of everything with 512 bytes of some random crap. dd skip=10 iflag=skip_bytes if=original.file of=first10ktrimmed.file despite being old, and the amount of insanely horrible things you can do when you mess up the syntax or mistype something using it, dd is fucking amazing. to be fair, its not directly editing the file, but making a copy with the first 10k skipped. you could have a jump/pointer that points to the shortened first block of the file and then at the end of that, a pointer/jump to pick up where the rest of the file continues, but you'd wind up with misalignment and fs fragmentation.
- CrowFly 7y agoLinux doesn't implement sparse files.
- fl0wenol 7y agoYes it does? The details are file system specific and if they support mmap then it's also likely there's a page alignment requirement but that's not atypical.
- LeoPanthera 7y agoNot only does it do so, but dd directly supports sparse files, using the "sparse" conv symbol.
- cortesoft 7y agoThis really isn't solving the problem posed by the author, though. Copying the file is a completely different thing; for one, it will require double the space and take a lot longer. What if you need to chop the first 10 bytes from a file that is more than half your disk?
- eps 7y ago_Copying_ what you want from a file is trivial on any OS. The question is to how to trim the file head _in place_.
- burmecia 7y agoAnother approach I can think of is using rolling hash (https://en.wikipedia.org/wiki/Rolling_hash https://en.wikipedia.org/wiki/Rolling_hash) to split file to different size of chunks, those chunks can be saved on different sectors which don’t need to be continuous. The file keeps a list of indexes for all those chunks, just like inode did for blocks. When insert some bytes in the beginning of file, thanks for the rolling hash, most likely only the first several chunks need to be re-chunk and re-hash, thus the change is localised and can be cheaply done, all the rest chunks still untouched. When this combined with append-only storage, things are even easier because it only needs to deal with bytes around that beginning, and the update chunk index list in file. This approach is already implemented in ZboxFS (https://github.com/zboxfs/zbox https://github.com/zboxfs/zbox) to do content-based deduplication.
- oblio 7y agoI swear that everytime someone posts a generic Microsoft blog entry, I automatically think: "oldnewthing". I hovered over the link, and there it was. Raymond Chen is a machine, the T-1000 of Windows development. I've never developed Windows applications using C++ and I still read his blog articles.
- JulianMorrison 7y agoTo delete from the beginning of a file, overwrite offset 0 from offset n, 1 from n+1 and so on, and then truncate it when the read offset hits EOF.
- gpvos 7y agoI didn't get the "minus 100 points" reference, but it was not hard to find it on the web: https://blogs.msdn.microsoft.com/ericgu/2004/01/12/minus-100-points/ https://blogs.msdn.microsoft.com/ericgu/2004/01/12/minus-100...
- fjfaase 7y agoWhy would you want to delete bytes from the beginning of a file? A file should be seen as a low-level data structure with a limited set of operations. If you want to implement a more complex data structure with a wider range of operations, there are usually multiple ways of implementing this on a low-level data structure with a limited set of operations. This is basically what a lot of software engineering is about. If you want to implement an array of bytes with delete and insert operations, there are many ways you could implement this on a low-level file. Which way is the best depends on so many other factors. Do you want undo-redo functionality, transaction properties, distributed access, and so on?
- posix_me_less 7y agoBecause sometimes I want to remove old and irrelevant lines in a logfile but want to retain the recent lines. > A file should be seen as a low-level data structure with a limited set of operations. Why should? For many people, a file is a basic way to permanently store data. Changing the data at any point of the file should be easy.
- fjfaase 7y agoActually, most file systems let you randomly read and write to files. Usually, they implement this by reading and writing blocks (of 256 bytes or a multiple). One could create file systems with more advanced operations, but most likely, these will be based on the more primitive operations. For example, to add the function to remove 10 bytes from the start of the file, one could read the whole file, block-by-block, and move the data 10 bytes. For a large log file, this will take a long time. Another solution is to have a begin of file offset for all files, this means that some additional information need to be stored with every the file and that this information needs to be accessed with all file operations, resulting in some performance loss for all file operations. Existing programs that access files as blocks of a certain size, might see significant performance penalties when the offset is not a multiple of the block size, because reading the data from one block, needs to read two actual blocks from the underlying medium. If you often want to strip a logfile from old data, a solution might be to create new logfiles at a regular intervals and delete old logfiles. Or maybe even better, use a database to store the log messages. Gives you query functionality and allows you to perform more advanced operations, as removing certain types of log messages.
- vkaku 7y agoTheoretically, if the number of bytes to be removed were a multiple of FS data block size (usually an inode size), it should be possible to unlink that inode as well, and rewrite the metadata. It probably involves fewer shifts and fewer bytes/time wasted. In general, if you intend to create structures that allow one to reduce file size, reclaim the data, defragment - that sort of thing, a rewrite/coalesce happens to be the viable solution. In general, if allowed to increase, fragmentation will worsen with time.