make sure the new MDMF extension field is forward-compatible and safe #1526

New issue

Closed

opened 2011-09-04 17:25:23 +00:00 by zooko · 16 comments

zooko commented

2011-09-04 17:25:23 +00:00

In #393 we've added "extension fields" to the MDMF caps. If I recall correctly, the original motivation was that future writers of MDMFs might want to include the K and segsize parameters in the cap itself (in addition to inside the share data) and future readers might want to take advantage of that information so that they don't need to do an extra round trip to learn that information by fetching some of the share data.

It is important that such future writers of MDMFs don't exclude older (v1.9) readers of MDMFs from being able to read those caps or even (gah!) cause them to get the wrong data or to incur an error when they try to read those caps. Therefore we need a way to include data in the caps which older (v1.9) readers will reliably and safely ignore (and still be able to read the file data correctly) but future readers can use if they want.

I thought we had decided to make a generic field for "extensions" in the MDMF caps, and not to make the current (1.9) reader or writer actually use this extension field yet. But the current code in trunk constrains that field instead of allowing it to be generically extensible, and it seems to try to use the numbers contained therein for its K and segsize values in some (?) cases.

The MDMF filecap format is currently defined as:

  URI:MDMF:$writekey:$fingerprint[(:$extension)*]

and all existing caps are created with two extension fields: the first is K (as an integer), the second is segsize (also as an integer). The intention is to allow additional extension fields to be added in the future, perhaps hints that could speed up a download.

But the current code first constrains each extension field to [contain only the characters 0-9 and :]source:trunk/src/allmydata/uri.py?annotate=blame&rev=5220#L31, and then it requires there to be [exactly two such fields]source:trunk/src/allmydata/mutable/filenode.py?annotate=blame&rev=5227#L120.

Future versions of MDMF writers can't use the extensions then, to communicate anything other than the currently defined K and segsize fields. They might allow some future use if each field can have a larger set of characters, and if there is space for messages that Tahoe-LAFS v1.9 readers will parse and then ignore.

I'd like to have this in 1.9 because then 1.9 will be tolerant of caps generated by future versions that have a different number of extension fields.

As for the use of that field to initialize the K and segsize values, I haven't read through the code carefully enough to see if it does that correctly and if it has good tests. This is potentially complicated.

What, for example, happens if the segsize indicated in the cap and the segsize indicated [in the version info]source:trunk/src/allmydata/mutable/filenode.py?annotate=blame&rev=5227#L1107 differ? Can the segsize or the K change in different versions of the same MDMF? (I'm pretty sure it can't, but if it can't then maybe the value in the cap should be the only place that K or segsize exist.) Does the current trunk MDMF reader actually really use this value? Scanning through the code, I don't think so but I'm not 100% sure yet.

There are three possibilities that I think we should consider for v1.9.0:

Proposal 1 (extension field for future use—currently unused)

1. a. Loosen the constraint-checking on the extension field in MDMF caps to allow a larger character class and have almost no constraints except those necessary for safe and easy parsing to find where the field begins and ends.
1. b. Eliminate all code which uses the contents of the extension field when reading.
1. c. Reconsider whether to populate the contents of that extension field with K:segsize when generating a URL. (The way K and segsize are encoded into the extension field has, of course, to fit into the constraints of the extension field. In addition to that, it should not consume the entire extension field, but should allow a safe and easy way for other fields to be added into the extension field such that they can be unambiguously parsed apart from the K and segsize fields.)
1. d. Think about whether this proposal will lead to unsafety/insecurity or forward-compatibility problems.

Proposal 2 (K and segsize in cap):

1. a. Define part of the MDMF cap to hold K and segsize. This is in fact exactly the same as the "extension field" in the current trunk, but we stop calling it the "extension field" and start calling it K and segsize.
1. b. Eliminate all code which uses K and segsize values from anywhere other than the cap when reading.
1. c. Think about whether this proposal will lead to unsafety/insecurity or forward-compatibility problems.

Proposal 3 (K and segsize in cap, plus an extension field):

Do all of Proposal 2 to encode K and segsize into the cap, and then also do proposal 1.a. to provide an extension field for future use.

[Zooko was talking below about slightly different versions of the proposals -- he wasn't sure whether the existing code included K and segsize, which in fact it does.]Note:

I think that Proposal 1 is the least likely to delay or destabilize Tahoe-LAFS v1.9 ~~especially if we leave out the optional 1.c. step~~. If v1.9 does not attempt to use the extension field in any way other than telling where it begins and ends, then future MDMF users will not have to worry that what they put in there will cause problems for old v1.9 users. By removing all the code that does anything with the extension field (aside from the regex which allows the extension field to be present in an MDMF cap), we can simplify the current 1.9 alpha code for easier review.

I'd like to hear your opinion about this! (Especially if you are Kevan, David-Sarah, or Brian.)

In #393 we've added "extension fields" to the MDMF caps. If I recall correctly, the original motivation was that future writers of MDMFs might want to include the `K` and `segsize` parameters in the cap itself (in addition to inside the share data) and future readers might want to take advantage of that information so that they don't need to do an extra round trip to learn that information by fetching some of the share data. It is important that such future writers of MDMFs don't exclude older (v1.9) readers of MDMFs from being able to read those caps or even (gah!) cause them to get the wrong data or to incur an error when they try to read those caps. Therefore we need a way to include data in the caps which older (v1.9) readers will reliably and safely ignore (and still be able to read the file data correctly) but future readers can use if they want. I thought we had decided to make a generic field for "extensions" in the MDMF caps, and not to make the current (1.9) reader or writer actually use this extension field yet. But the current code in trunk constrains that field instead of allowing it to be generically extensible, and it seems to try to use the numbers contained therein for its `K` and `segsize` values in some (?) cases. The MDMF filecap format is currently defined as: ``` URI:MDMF:$writekey:$fingerprint[(:$extension)*] ``` and all existing caps are created with two extension fields: the first is K (as an integer), the second is segsize (also as an integer). The intention is to allow additional extension fields to be added in the future, perhaps hints that could speed up a download. But the current code first constrains each extension field to [contain only the characters 0-9 and :]source:trunk/src/allmydata/uri.py?annotate=blame&rev=5220#L31, and then it requires there to be [exactly two such fields]source:trunk/src/allmydata/mutable/filenode.py?annotate=blame&rev=5227#L120. Future versions of MDMF writers can't use the extensions then, to communicate anything other than the currently defined K and segsize fields. They might allow some future use if each field can have a larger set of characters, and if there is space for messages that Tahoe-LAFS v1.9 readers will parse and then ignore. I'd like to have this in 1.9 because then 1.9 will be tolerant of caps generated by future versions that have a different number of extension fields. As for the use of that field to initialize the `K` and `segsize` values, I haven't read through the code carefully enough to see if it does that correctly and if it has good tests. This is potentially complicated. What, for example, happens if the `segsize` indicated in the cap and the `segsize` indicated [in the version info]source:trunk/src/allmydata/mutable/filenode.py?annotate=blame&rev=5227#L1107 differ? Can the `segsize` or the `K` change in different versions of the same MDMF? (I'm pretty sure it can't, but if it can't then maybe the value in the cap should be the *only* place that `K` or `segsize` exist.) Does the current trunk MDMF reader actually really use this value? Scanning through the code, I don't think so but I'm not 100% sure yet. There are three possibilities that I think we should consider for v1.9.0: Proposal 1 (extension field for future use—currently unused) * 1. a. Loosen the constraint-checking on the extension field in MDMF caps to allow a larger character class and have almost no constraints except those necessary for safe and easy parsing to find where the field begins and ends. * 1. b. Eliminate all code which uses the contents of the extension field when reading. * 1. c. Reconsider whether to populate the contents of that extension field with `K:segsize` when generating a URL. (The way `K` and `segsize` are encoded into the extension field has, of course, to fit into the constraints of the extension field. In addition to that, it should *not* consume the entire extension field, but should allow a safe and easy way for other fields to be added into the extension field such that they can be unambiguously parsed apart from the `K` and `segsize` fields.) * 1. d. Think about whether this proposal will lead to unsafety/insecurity or forward-compatibility problems. Proposal 2 (`K` and `segsize` in cap): * 2. a. Define part of the MDMF cap to hold `K` and `segsize`. This is in fact exactly the same as the "extension field" in the current trunk, but we stop calling it the "extension field" and start calling it `K` and `segsize`. * 2. b. Eliminate all code which uses `K` and `segsize` values from anywhere *other* than the cap when reading. * 2. c. Think about whether this proposal will lead to unsafety/insecurity or forward-compatibility problems. Proposal 3 (`K` and `segsize` in cap, plus an extension field): * Do all of Proposal 2 to encode `K` and `segsize` into the cap, and then also do proposal 1.a. to provide an extension field for future use. [Zooko was talking below about slightly different versions of the proposals -- he wasn't sure whether the existing code included K and segsize, which in fact it does.]Note: I think that Proposal 1 is the least likely to delay or destabilize Tahoe-LAFS v1.9 ~~especially if we leave out the optional 1.c. step~~. If v1.9 does not attempt to use the extension field in any way other than telling where it begins and ends, then future MDMF users will not have to worry that what they put in there will cause problems for old v1.9 users. By removing all the code that does anything with the extension field (aside from the regex which allows the extension field to be present in an MDMF cap), we can simplify the current 1.9 alpha code for easier review. I'd like to hear your opinion about this! (Especially if you are Kevan, David-Sarah, or Brian.)

zooko added the

labels 2011-09-04 17:25:23 +00:00

zooko added this to the 1.9.0 milestone 2011-09-04 17:25:23 +00:00

daira commented

2011-09-04 19:16:09 +00:00

Current trunk does put K and segsize into the extension field when generating caps (source:src/allmydata/mutable/filenode.py@5227#L702).

warner commented

2011-09-04 21:19:56 +00:00

also see #1509 ("MDMF filecaps should tolerate extra parameters"). This ticket contains more information than #1509, though, so if we close one as a dup, I'd close #1509.

kevan commented

2011-09-04 21:37:46 +00:00

Owner

I think that the code at the moment simply populates the k and segsize values -- it doesn't try to use them. Actually, aside from the restrictive nature of the extension fields at the moment, proposal 1 is what the current code does.

As I understand it, the extension fields are meant to advisory. That is, any part of Tahoe-LAFS that uses them to work with a file should tolerate cases in which they're wrong. So we'd treat the remote share's representation of the segsize, k, or whatever else we choose to stick in the cap as canonical, and defer to it in the event of an inconsistency.

I like the conservatism of precisely specified and restrictive extension fields; it makes me more comfortable with the idea of extension fields, since it's easier for me to reason about the form of a valid cap and feel confident that we haven't inadvertently allowed caps that we don't want to allow. It is kind of silly to add a restriction like that before we even start writing the code that might one day use the extensions, though, and my objection isn't anything more than a vague unease with the idea. I think that the code at the moment simply populates the k and segsize values -- it doesn't try to use them. Actually, aside from the restrictive nature of the extension fields at the moment, proposal 1 is what the current code does. As I understand it, the extension fields are meant to advisory. That is, any part of Tahoe-LAFS that uses them to work with a file should tolerate cases in which they're wrong. So we'd treat the remote share's representation of the segsize, k, or whatever else we choose to stick in the cap as canonical, and defer to it in the event of an inconsistency.

daira commented

2011-09-04 21:48:35 +00:00

For any future extensions, I would prefer each field to be labelled. A one-letter label as the first character of the field would probably be sufficient. The advantage of this is that if we decide that a particular field is no longer necessary, we can just omit it without making the parse ambiguous.

I'm a bit confused as to what optimizations are available from including K and segsize in the cap. Doesn't the downloader get K and segsize on the first round-trip anyway? Why would it be helpful to know them before that? For any future extensions, I would prefer each field to be labelled. A one-letter label as the first character of the field would probably be sufficient. The advantage of this is that if we decide that a particular field is no longer necessary, we can just omit it without making the parse ambiguous.

daira commented

2011-09-04 22:09:23 +00:00

[edited to merge in comments from the duplicate #1509, and take into account comment:386739.]Description

[edited to merge in comments from the duplicate #1509, and take into account [comment:386739](/tahoe-lafs/trac/issues/1526#issuecomment-386739).]Description

warner commented

2011-09-04 22:18:44 +00:00

on IRC just now, I concluded that a "k" hint is useful to the mapupdate step (so it can make a reasonable number of parallel DYHB/checkstring requests), but that the "segsize" hint isn't so useful.

Ideally, the hints would let us build a one-round-trip downloader. The share contains a bunch of static data (whose size depends upon "N" and the keysize, but not the current filesize), followed by the share data, finally followed by the block hash tree (which depends upon the current filesize). This order lets us grow the file without needing to move all the sharedata. So 1 RTT is really hard: you have to correctly guess where the block hash tree data is, which means knowing the filesize to within a segment, in addition to knowing the segsize.

So 2 RTT is a more reasonable goal: the first request tells you the current filesize and the offset table, which lets you make an accurate second request. For the current Retrieve code, the first request is done during the mapupdate phase, which gets the checkstring and offset table for each known share. Then the retrieve phase can make an accurate initial request, and return the first segment of data in just 2 RTT.

So anyways, I think "k" is a useful hint, but I'm no longer so sure about including "segsize". I think "k" is so useful that I'm willing to make it mandatory, or at least untagged, so the MDMF filecap would be URI:MDMF:$writekey:$verfkeyfingerprint[:$k][:$EXTNAME=$VALUE]*.

The downside of making "k" so non-optional is that a repairer/reencoder which changes the file's encoding (replacing every single share) would then cause the filecap's "k" value to be stale. The retrieve code only treats it as a hint, of course (includinging the mapupdate step but not e.g. decoding), so it couldn't hurt anything but efficiency (the mapupdate's first batch of requests might not be enough to find enough shares, and we'll have to wait for the first batch to return before we learn of the larger real "k" and send out a second batch). But I think that's not a significant issue.

on IRC just now, I concluded that a "k" hint is useful to the mapupdate step (so it can make a reasonable number of parallel DYHB/checkstring requests), but that the "segsize" hint isn't so useful. Ideally, the hints would let us build a one-round-trip downloader. The share contains a bunch of static data (whose size depends upon "N" and the keysize, but not the current filesize), followed by the share data, finally followed by the block hash tree (which depends upon the current filesize). This order lets us grow the file without needing to move all the sharedata. So 1 RTT is really hard: you have to correctly guess where the block hash tree data is, which means knowing the filesize to within a segment, in addition to knowing the segsize. So 2 RTT is a more reasonable goal: the first request tells you the current filesize and the offset table, which lets you make an accurate second request. For the current Retrieve code, the first request is done during the mapupdate phase, which gets the checkstring and offset table for each known share. Then the retrieve phase can make an accurate initial request, and return the first segment of data in just 2 RTT. So anyways, I think "k" is a useful hint, but I'm no longer so sure about including "segsize". I think "k" is so useful that I'm willing to make it mandatory, or at least untagged, so the MDMF filecap would be `URI:MDMF:$writekey:$verfkeyfingerprint[:$k][:$EXTNAME=$VALUE]*`. The downside of making "k" so non-optional is that a repairer/reencoder which changes the file's encoding (replacing every single share) would then cause the filecap's "k" value to be stale. The retrieve code only treats it as a hint, of course (includinging the mapupdate step but not e.g. decoding), so it couldn't hurt anything but efficiency (the mapupdate's first batch of requests might not be enough to find enough shares, and we'll have to wait for the first batch to return before we learn of the larger real "k" and send out a second batch). But I think that's not a significant issue.

warner commented

2011-09-07 06:47:46 +00:00

If we're really not using those hints at all right now, then the code changes to support this should be pretty simple. I think we may be parsing 'k' and 'segsize' and populating the Filenode with them, in which case it's possible for behavior to be affected, and we should change it to not pre-populate those values.

I'll figure out how to implement this: I think it means a test that the URI parser accepts (and equates) filecaps with extra stuff after the fingerprint (so URI:MDMF:$writekey:$fingerprint:blahblah), changes to the URI parser's regexp, and changes to the Filenode constructor (to not extract+populate the extension fields). It might also involve changes to the URI constructor, to not provide those fields either.

After talking with zooko on IRC, I'm in favor of making 1.9 tolerate and ignore everything past the fingerprint. That puts no constraints on the extension fields (although 1.10 or some later version might impose some, and including "k" will be the first extension I'd recommend). If we're really not using those hints at all right now, then the code changes to support this should be pretty simple. I think we may be parsing 'k' and 'segsize' and populating the Filenode with them, in which case it's possible for behavior to be affected, and we should change it to not pre-populate those values. I'll figure out how to implement this: I think it means a test that the URI parser accepts (and equates) filecaps with extra stuff after the fingerprint (so `URI:MDMF:$writekey:$fingerprint:blahblah`), changes to the URI parser's regexp, and changes to the Filenode constructor (to not extract+populate the extension fields). It might also involve changes to the URI constructor, to not provide those fields either.

zooko commented

2011-09-19 04:50:31 +00:00

Author

Kevan: I'd like to talk with you about this. Maybe a phone call would work better than trac comments. Maybe IRC.

warner was assigned by zooko

2011-09-19 04:50:31 +00:00

warner commented

2011-09-26 02:30:12 +00:00

Attachment no-extensions.diff (43052 bytes) added

tolerate-but-ignore extensions in MDMF filecaps: remove extension-handling code and tests

**Attachment** no-extensions.diff (43052 bytes) added tolerate-but-ignore extensions in MDMF filecaps: remove extension-handling code and tests

no-extensions.diff

42 KiB

Brian Warner <warner@lothar.com> commented

2011-10-01 23:37:24 +00:00

Owner

In changeset:416701e404c74a3e:

MDMF: remove extension fields from caps, tolerate arbitrary ones. Fixes #1526

The filecaps used to be produced with hints for 'k' and segsize, but they
weren't actually used, and doing so had the potential to limit how we change
those filecaps in the future. Also the parsing code had some problems dealing
with other numbers of extensions. Removing the existing fields and making the
parser tolerate (and ignore) extra ones makes MDMF more future-proof.

In changeset:416701e404c74a3e: ``` MDMF: remove extension fields from caps, tolerate arbitrary ones. Fixes #1526 The filecaps used to be produced with hints for 'k' and segsize, but they weren't actually used, and doing so had the potential to limit how we change those filecaps in the future. Also the parsing code had some problems dealing with other numbers of extensions. Removing the existing fields and making the parser tolerate (and ignore) extra ones makes MDMF more future-proof. ```

tahoe-lafs added the

r/fixed

label 2011-10-01 23:37:24 +00:00

Brian Warner <warner@lothar.com> closed this issue

2011-10-01 23:37:24 +00:00

Brian Warner <warner@lothar.com> commented

2011-10-07 19:39:47 +00:00

Owner

In [5393/ticket999-S3-backend]:

MDMF: remove extension fields from caps, tolerate arbitrary ones. Fixes #1526

The filecaps used to be produced with hints for 'k' and segsize, but they
weren't actually used, and doing so had the potential to limit how we change
those filecaps in the future. Also the parsing code had some problems dealing
with other numbers of extensions. Removing the existing fields and making the
parser tolerate (and ignore) extra ones makes MDMF more future-proof.

In [5393/ticket999-S3-backend]: ``` MDMF: remove extension fields from caps, tolerate arbitrary ones. Fixes #1526 The filecaps used to be produced with hints for 'k' and segsize, but they weren't actually used, and doing so had the potential to limit how we change those filecaps in the future. Also the parsing code had some problems dealing with other numbers of extensions. Removing the existing fields and making the parser tolerate (and ignore) extra ones makes MDMF more future-proof. ```

daira commented

2011-10-10 19:53:54 +00:00

In changeset:de00b277cc9adfb0:

interfaces.py: remove get_extension_params and set_extension_params methods from IMutableFileURI. refs #393, #1526

In changeset:de00b277cc9adfb0: ``` interfaces.py: remove get_extension_params and set_extension_params methods from IMutableFileURI. refs #393, #1526 ```

daira commented

2011-10-10 20:07:47 +00:00

In [5418/ticket999-S3-backend]:

interfaces.py: remove get_extension_params and set_extension_params methods from IMutableFileURI. refs #393, #1526

In [5418/ticket999-S3-backend]: ``` interfaces.py: remove get_extension_params and set_extension_params methods from IMutableFileURI. refs #393, #1526 ```

zooko commented

2011-10-17 17:51:05 +00:00

Author

I reviewed changeset:0716c496c8a39758 and it looks good to me (except see below). It has a net reduction of source code, which is always good.

One thing I noticed was that with this patch, if you have a cap with an extension field, and you parse it using [uri.py]source:trunk/src/allmydata/uri.py?annotate=blame&rev=5305 and then produce a cap from the resulting Python object, the cap produced will not have the extension on it. Could this be a problem if, in the future, someone sends a cap with an extension, and a user of Tahoe-LAFS v1.9 inputs that cap into their Tahoe-LAFS implementation? Regardless of whether their Tahoe-LAFS v1.9 will show the extension field in copies of the cap that it produces/exports/displays, it will certainly not use the extension field for anything, so the only question is whether it is okay for the Tahoe-LAFS v1.9 implementation to omit the extension, which it is ignoring, from productions/exports/displays of that cap.

Kevan: I would appreciate it if you would review this issue, and this patch, even though (or especially because) you earlier said you preferred the original behavior of parsing the extension field as a two-tuple of integers.

David-Sarah: I would appreciate it if you would review this because you did such a great job of reasoning about forward-compatibility in previous iterations.

I reviewed changeset:0716c496c8a39758 and it looks good to me (except see below). It has a net reduction of source code, which is always good. One thing I noticed was that with this patch, if you have a cap with an extension field, and you parse it using [uri.py]source:trunk/src/allmydata/uri.py?annotate=blame&rev=5305 and then produce a cap from the resulting Python object, the cap produced will not have the extension on it. Could this be a problem if, in the future, someone sends a cap with an extension, and a user of Tahoe-LAFS v1.9 inputs that cap into their Tahoe-LAFS implementation? Regardless of whether their Tahoe-LAFS v1.9 will *show* the extension field in copies of the cap that it produces/exports/displays, it will certainly not *use* the extension field for anything, so the only question is whether it is okay for the Tahoe-LAFS v1.9 implementation to omit the extension, which it is ignoring, from productions/exports/displays of that cap. Kevan: I would appreciate it if you would review this issue, and this patch, even though (or especially because) you earlier said you preferred the original behavior of parsing the extension field as a two-tuple of integers. David-Sarah: I would appreciate it if you would review this because you did such a great job of reasoning about forward-compatibility in previous iterations.

warner commented

2011-10-17 17:58:34 +00:00

I'm inclined to think that we should only be parsing caps with uri.py if we're about to consume them somehow, and never re-stringify them unless we've just created one (i.e. uploaded a new file). Then we won't be obligated to have uri.py retain information that it doesn't actually use.

Things like directory-listing should just dump the filecap strings.

In fact, I kind of regret having URI objects in the first place.. they're really just a was to encapsulate the parsing/serialization functions. Having a separate class has caused a lot of confusion in things like filenode.py's get_uri() method (does it return a string? a URI object?). So I'd like to reduce their use, and eventually get rid of them completely, somehow.

I'm inclined to think that we should only be parsing caps with `uri.py` if we're about to consume them somehow, and never re-stringify them unless we've just created one (i.e. uploaded a new file). Then we won't be obligated to have `uri.py` retain information that it doesn't actually use. Things like directory-listing should just dump the filecap strings. In fact, I kind of regret having URI objects in the first place.. they're really just a was to encapsulate the parsing/serialization functions. Having a separate class has caused a lot of confusion in things like `filenode.py`'s `get_uri()` method (does it return a string? a URI object?). So I'd like to reduce their use, and eventually get rid of them completely, somehow.

zooko commented

2011-10-17 18:52:19 +00:00

Author

Re: comment:386755 that sounds good! It means that code which is going to consume caps and later produce them again has to keep a verbatim copy of the (string) cap that they started with. But, this is a question of how storage and reproduction of caps should be implemented -- it is orthogonal to the question of whether that storage and reproduction should include or omit the extension field.

Re: [comment:386755](/tahoe-lafs/trac/issues/1526#issuecomment-386755) that sounds good! It means that code which is going to consume caps and later produce them again has to keep a verbatim copy of the (string) cap that they started with. But, this is a question of how storage and reproduction of caps should be implemented -- it is orthogonal to the question of whether that storage and reproduction should include or omit the extension field.