Bill Kelly
3/4/2007 5:42:00 PM
Hi,
I'd like to create Ruby bindings for a library that may or
may not exist yet.
What I'd like to be able to do, is make an arbitrary number
of insert/delete (cut/paste) style edits on huge binary
files (> 4 GB). There should be minimal overhead for
initially "opening" the file, and the inserts and
deletes should be very fast, until the changes are finally
committed.
(Further, on commit, if the edits to the file did not cause
existing data to be shifted to different offsets--i.e. the
edits changed some existing bytes but did not shift the
file contents, then the commit should be optimized by just
patching/updating the changed parts of the file, rather than
rewriting the whole file.)
If anyone knows of an open source (non-GPL) library that
already does this sort of thing, that would be fantastic.
If not, here's how I'm thinking of implementing it. If
anyone has thoughts on better ways to implement it, feedback
is welcome.
* * *
For the sake of illustration, let's consider a Hex editor
implemented on top of this library, performing a very
simple insert operation:
We have a 10 GB file, and we want to run the Hex editor
and jump to about 5 GB into the file, and insert a byte
(shifting the remaining 5GB up by one byte.)
From the user's point of view, there should be no delay
when opening the file, jumping ahead 5GB and inserting
the byte. The user should see a view representing the
edited data, and there should be no delays until the edits
are actually committed (Save key pressed.)
* * *
What I figure on doing is mmap'ing a swap file, and
accessing the swap file in getpagesize()-sized blocks.
I have four kinds of block types in mind for the pagefile:
- directory block (the zeroth block, contains offset-ptrs
to the first data block, and first free block)
- free block (points to next free block if any)
- virtual data block (represents arbitrary-length span
of data in original file)
- edit data block (holds literal data pasted by the user)
Initially, the page file would consist of the directory
block, and a single virtual data block representing the
entirety of the original file.
As edits are made, the virtual data block will be split,
and a linked list of virtual- and edit- data blocks will
be formed, which if walked linearly, represent the edited
version of the file.
In our hex-editing example with the insertion of one byte
midway through the 10GB file, we'd see something like this:
(Note: 10GB == 0x280000000)
Initially,
blk#
0 [dir] [<0001><0000>_______________________________]
1 [virt] [<0000><0000>(000000000)(27fffffff)_________]
The <nnnn> values represent block offsets within the pagefile.
(Not sure if they will be 32- or 64- bit quantities.)
In the case of the [dir] block, the <0001> points to the first
in a linked list of data blocks, and the <0000> would point
to the first in a linked list of free blocks, but there
aren't any free blocks initially.
In the case of the [virt] block, the <0000><0000> are next/prev
pointers in a doubly linked list of virtual- and edit- blocks.
The (mmmmmmmmmmm) values in the [virt] block represent 64-bit
offsets into the original file. (The remainder of the virtual
block is unused.)
So our page file starts off simply representing the entirety
of the original file.
When our hex-editing user inserts a byte at the 5GB point,
our virtual block will be split, and an edit block containing
the literal byte from the user will be inserted, as follows:
(Note: the user inserted a byte with value 42, ASCII '*'.)
blk#
0 [dir] [<0001><0000>_______________________________]
1 [virt] [<0002><0000>(000000000)(13fffffff)_________]
2 [edit] [<0003><0001>(001)*_________________________]
3 [virt] [<0000><0002>(140000000)(27fffffff)_________]
If we walk the list of data blocks linearly, we see the
first 5GB of the original file, the single byte inserted
by the user, and finally the remaining 5GB of original
file.
Since edit blocks hold literal data, they can hold up
to (getpagesize() - n) bytes, where n is the overhead
for the linked list ptrs and length count.
Anyway: it seems to me this structure should allow me to
handle arbitrary inserts/deletes with good speed. And with
a little logic to handle coalescing neighboring edit blocks
we should be able to avoid ending up with a bunch of
partially-full edit blocks linked together wasting space.
* * *
Anyway--if you made it this far, thanks very much for
your interest!
If anyone has thoughts about weak points of this design or
how to improve it, your feedback is most welcome.
This will be my first project actually using mmap, even
though I've wanted to have a reason to use it for a
decade or two now. :-)
One concern: I hope that mmap is pretty fast, as my naive
approach would be to change which block in the page file
I'm "looking at" very often.
Regards,
Bill