John D. Heintz wrote:
Thanks for the response Edward. It has definitely helped clarify
things. I'm going to try the debugfs.reiser4 tool, and I've got a few
more questions below.
On 3/6/07, * Edward Shishkin* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
John D. Heintz wrote:
> Hello all,
>
> Can someone help explain to me the relationship between keys and
> objects/items/units? Specifically, I'm confused by the reality
that a
> single file (object?) is identified by one key,
This reality is incorrect. Key is assigned for a storage unit.
File is not a storage unit. Item is.
On-disk file includes different items, even items of different type
(for example, stat-data and extent pointers) which have different
key. However appropriate components of those keys are coincide.
Here "coincide" means that major and minor locality may be the same?
Yes.
> but the individual parts (stat_data, extends) each have their
own keys
> as well.
Right.
stat-data and extent pointer are items, and each item has a unique
key.
> How does one key lead to the others?
>
> Are there any detailed examples of keys available?
Mount an empty reiser4 partition to /mnt, write a file
echo "Hello World" > /mnt/foo && sync
then investigate this partition by debugfs.reiser4 -t
You will see various examples of items and keys.
Note, that terminology can be different: NPTR
(node pointer) means internal item. SD is stat-data
item, DIRITEM is compound directory item, etc.
Ask if something is unclear.
I plan on doing this shortly, thanks for the description. This is
probably exactly what I'm looking for.
> If the diagram from the whitepaper here:
> http://www.namesys.com/treepics/treepicswin/Blobs_Reiser4.gif
> < http://www.namesys.com/treepics/treepicswin/Blobs_Reiser4.gif>
could
> be annotated to contain samples for:
> * a single directory,
> * two small files,
> * a large file (2-3 extents)
> * the stat_data (and item keys)
> * twig nodes showing delimiting keys and extent pointers
> * formatted nodes showing directory entries, stat_data
> * also, plugin id at the unit, item, and object levels would help!
>
> I think that would be very helpful for people to understand how the
> tree and plugins work.
ok, I'll try to illustrate..
>
> I'm slogging through the code in my spare time, but I really hope
> someone already knows the answers and will post an explanation!
>
> The following statements in the V4 whitepaper led me to
realizing the
> storage layer was doing something with keys I didn't understand:
>
> "Everything in the tree has exactly one key."
Yeah, a bit clumsy phrase.. It would be better: "every object is
represented as a set of items, and every item has a unique key".
That makes much more sense.
>
> "These directory entries contain a name, and a key." (The Unix
> Directory Plugin)
Right.
Like other objects, directory is represented as a set of items of
special "compound directory item" type. Its format is defined in
reiser4/plugin/item/cde.h, see also comments at the beginning
of reiser4/plugin/item/cde.c
So every directory entry is represented on disk as a unit within
compound directory item.
> "...more precisely, since a key selects not just the file but a
> particular byte within a file,
Right.
For each file you can construct a unique key that will address a
particular byte within this file.
What would that key look like?
key_by_inode_and_offset_common() constructs such key,
@off is to specify byte's offset
I can imagine a key for the "file content" item. The bytes would be
units inside that item,
One-to-one correspondence unit<->byte takes place not for every item type.
It is so for tail items (FORMATTING_ID). But for extent pointers
(EXTENT_POINTER_ID) unit is a pointer to a large chunk of data.
Item's units are to perform lookup within an item.
but how does that offset fit within a key?
A special key components stays for offset.
For example, if you want to read some amount of bytes starting from some
offset, then construct a key passing this offset, and do
coord_by_key(). The
last one will return a coord which specify a unit that points to needed
chunk
of data. Extracting data is a business of ->read() method of item plugin,
which accepts found coord.
Or is this what the coord struct is all about?
coord is a position in the (storage) tree, which included all infrastructure
(locking, node pointers, etc) needed to travel within the tree. In the
example
above ->read() method will walk along the tree to pick out needed amount
of data.
Actually, things in Reiser4 are more fine grained, and items are
considered as a (fully ordered) set of smaller objects, so-called
item's units, so every unit has its own key and item's key is coincide
with the key of its first unit. This approach is convenient.
For example, units can be used to address a particular bytes within
a file built of tail items. It is more graceful way, then just having
an item to access its content (which in common case can be quite
complex) by some ugly macro (approach of reiserfs, v3)
> it returns that part of the key which is sufficient to select the
> file, and which is sufficient to allow the code to determine
what the
> full keys for those various parts when the byte offset and some
other
> fields (like item type) are added to the partial key to form a
whole
> key..."
>
> "The key can then be used by the tree storage layer to find
all the
> pieces of that which was named."
Reiser4 is a storage layer of global Reiser's project which
aims to add support for semi-structured data querying to the
file system namespace (more details about global project are
in whitepaper.html)
>
> "we can store just one key for the extent, and then we can
calculate
> the key of any byte within that extent."
It means we don't keep a key for each unit. Key of each unit
is calculated by its item key and unit's position in the item
(special method ->unit_key() of item plugin stands for this).
What should be kept in mind:
1) item is a "real" storage unit: its key is stored on disk.
2) item's unit is a "virtual" storage unit: its key is calculated.
>From the comments in key.h, it seems like a key is 24 bytes long. Are
these virtual keys the same or different things?
The same.
That is, what is different between a key to the file item and a key to
the 3rd byte in a file item?
"Key of item's byte is a wrong concept: it can be meaningless, if the
item has complex nature.
"Key of file's byte" is a good concept.
Suppose a regular file of size 10 consists of stat-data and 1 body item.
Let's consider following keys:
key1 is a key of file's body item;
key2 is a key of 3rd byte in this file.
Their offsets will be different: off2 == off1 + 2 == 2
Suppose, in the example above you want to read the file starting from
3rd byte. You need to construct a key2, pass it to coord_by_key(), which
returns coord that specifies some unit to start read from.
And again, only key1 is stored in the tree (I don't consider stat-data).
Perhaps, it would be better to say, that
item is a storage unit;
item's unit is a lookup unit.
>
> Thanks,
> John
>
> --
> John D. Heintz
> Principal Consultant
> New Aspects of Software
> Austin, TX
> (512) 633-1198
--
John D. Heintz
Principal Consultant
New Aspects of Software
Austin, TX
(512) 633-1198
