root/doc/jobs.txt

-*- outline -*-

Reasonably independent newpb sub-tasks that need doing. Most important come
first.

* decide on a version negotiation scheme

Should be able to telnet into a PB server and find out that it is a PB
server. Pointing a PB client at an HTTP server (or an HTTP client at a PB
server) should result in an error, not a timeout. Implement in
banana.Banana.connectionMade().

desiderata:

 negotiation should take place with regular banana sequences: don't invent a
 new protocol that is only used at the start of the connection

 Banana should be useable one-way, for storage or high-latency RPC (the mnet
 folks want to create a method call, serialize it to a string, then encrypt
 and forward it on to other nodes, sometimes storing it in relays along the
 way if a node is offline for a few days). It should be easy for the layer
 above Banana to feed it the results of what its negotiation would have been
 (if it had actually used an interactive connection to its peer). Feeding the
 same results to both sides should have them proceed as if they'd agreed to
 those results.

 negotiation should be flexible enough to be extended but still allow old
 code to talk with new code. Magically predict every conceivable extension
 and provide for it from the very first release :).

There are many levels to banana, all of which could be useful targets of
negotiation:

 which basic tokens are in use? Is there a BOOLEAN token? a NONE token? Can
 it accept a LONGINT token or is the target limited to 32-bit integers?

 are there any variations in the basic Banana protocol being used? Could the
 smaller-scope OPEN-counter decision be deferred until after the first
 release and handled later with a compatibility negotiation flag?

 What "base" OPEN sequences are known? 'unicode'? 'boolean'? 'dict'? This is
 an overlap between expressing the capabilities of the host language, the
 Banana implementation, and the needs of the application. How about
 'instance', probably only used for StorageBanana?

 What "top-level" OPEN sequences are known? PB stuff (like 'call', and
 'your-reference')? Are there any variations or versions that need to be
 known? We may add new functionality in the future, it might be useful for
 one end to know whether this functionality is available or not. (the PB
 'call' sequence could some day take numeric argument names to convey
 positional parameters, a 'reference' sequence could take a string to
 indicate globally-visible PB URLs, it could become possible to pass
 target.remote_foo directly to a peer and have a callable RemoteMethod object
 pop out the other side).

 What "application-level" sequences are available? (Which RemoteInterface
 classes are known and valid in 'call' sequences? Which RemoteCopy names are
 valid for targets of the 'copy' sequence?). This is not necessarily within
 the realm of Banana negotiation, but applications may need to negotiate this
 sort of thing, and any disagreements will be manifested when Banana starts
 raising Violations, so it may be useful to include it in the Banana-level
 negotiation.

On the other hand, negotiation is only useful if one side is prepared to
accomodate a peer which cannot do some of the things it would prefer to use,
or if it wants to know about the incapabilities so it can report a useful
failure rather than have an obscure protocol-level error message pop up an
hour later. So negotiation isn't the only goal: simple capability awareness
is a useful lesser goal.

It kind of makes sense for the first object of a stream to be a negotiation
blob. We could make a new 'version' opentype, and declare that the contents
will be something simple and forever-after-parseable (like a dict, with heavy
constraints on the keys and values, all strings emitted in full).

DONE, at least the framework is in place. Uses HTTP-style header-block
exchange instead of banana sequences, with client-sends-first and
server-decides. This correctly handles PB-vs-HTTP, but requires a timeout to
detect oldpb clients vs newpb servers. No actual feature negotiation is
performed yet, because we still only have the one version of the code.

* connection initiation

** define PB URLs

[newcred is the most important part of this, the URL stuff can wait]

A URL defines an endpoint: a pb.Referenceable, with methods. Somewhere along
the way it defines a transport (tcp+host+port, or unix+path) and an object
reference (pathname). It might also define a RemoteInterface, or that might
be put off until we actually invoke a method.

 URL = f("pb:", host, port, pathname)
 d = pb.callRemoteURL(URL, ifacename, methodname, args)

probably give an actual RemoteInterface instead of just its name

a pb.RemoteReference claims to provide access to zero-or-more
RemoteInterfaces. You may choose which one you want to use when invoking
callRemote.

TODO: decide upon a syntax for URLs that refer to non-TCP transports
 pb+foo://stuff, pby://stuff (for yURL-style self-authenticating names)

TODO: write the URL parser, implementing pb.getRemoteURL and pb.callRemoteURL
 DONE: use a Tub/PBService instead

TODO: decide upon a calling convention for callRemote when specifying which
RemoteInterface is being used.


DONE, PB-URL is the way to go.
** more URLs

relative URLs (those without a host part) refer to objects on the same
Broker. Absolute URLs (those with a host part) refer to objects on other
Brokers.

SKIP, interesting but not really useful

** build/port pb.login: newcred for newpb

Leave cred work for Glyph.

<thomasvs> has some enhanced PB cred stuff (challenge/response, pb.Copyable
credentials, etc).

URL = pb.parseURL("pb://lothar.com:8789/users/warner/services/petmail",
                  IAuthorization)
URL = doFullLogin(URL, "warner", "x8yzzy")
URL.callRemote(methodname, args)

NOTDONE

* constrain ReferenceUnslicer properly

The schema can use a ReferenceConstraint to indicate that the object must be
a RemoteReference, and can also require that the remote object be capable of
handling a particular Interface.

This needs to be implemented. slicer.ReferenceUnslicer must somehow actually
ask the constraint about the incoming tokens.

An outstanding question is "what counts". The general idea is that
RemoteReferences come over the wire as a connection-scoped ID number and an
optional list of Interface names (strings and version numbers). In this case
it is the far end which asserts that its object can implement any given
Interface, and the receiving end just checks to see if the schema-imposed
required Interface is in the list.

This becomes more interesting when applied to local objects, or if a
constraint is created which asserts that its object is *something* (maybe a
RemoteReference, maybe a RemoteCopy) which implements a given Interface. In
this case, the incoming object could be an actual instance, but the class
name must be looked up in the unjellyableRegistry (and the class located, and
the __implements__ list consulted) before any of the object's tokens are
accepted.

* security TODOs:

** size constraints on the set-vocab sequence

* implement schema.maxSize()

In newpb, schemas serve two purposes:

 a) make programs safer by reducing the surprises that can appear in their
    arguments (i.e. factoring out argument-checking in a useful way)

 b) remove memory-consumption DoS attacks by putting an upper bound on the
    memory consumed by any particular message.

Each schema has a pair of methods named maxSize() and maxDepth() which
provide this upper bound. While the schema is in effect (say, during the
receipt of a particular named argument to a remotely-invokable method), at
most X bytes and Y slicer frames will be in use before either the object is
accepted and processed or the schema notes the violation and the object is
rejected (whereupon the temporary storage is released and all further bytes
in the rejected object are simply discarded). Strictly speaking, the number
returned by maxSize() is the largest string on the wire which has not yet
been rejected as violating the constraint, but it is also a reasonable
metric to describe how much internal storage must be used while processing
it. (To achieve greater accuracy would involve knowing exactly how large
each Python type is; not a sensible thing to attempt).

The idea is that someone who is worried about an attacker throwing a really
long string or an infinitely-nested list at them can ask the schema just what
exactly their current exposure is. The tradeoff between flexibility ("accept
any object whatsoever here") and exposure to DoS attack is then user-visible
and thus user-selectable.

To implement maxSize() for a basic schema (like a string), you simply need
to look at banana.xhtml and see how basic tokens are encoded (you will also
need to look at banana.py and see how deserialization is actually
implemented). For a schema.StringConstraint(32) (which accepts strings <= 32
characters in length), the largest serialized form that has not yet been
either accepted or rejected is:

  64 bytes (header indicating 0x000000..0020 with lots of leading zeros)
 + 1 byte (STRING token)
 + 32 bytes (string contents)
 = 97

If the header indicates a conforming length (<=32) then just after the 32nd
byte is received, the string object is created and handed to up the stack, so
the temporary storage tops out at 97. If someone is trying to spam us with a
million-character string, the serialized form would look like:

  64 bytes (header indicating 1-million in hex, with leading zeros)
+  1 byte (STRING token)
= 65

at which point the receive parser would check the constraint, decide that
1000000 > 32, and reject the remainder of the object.

So (with the exception of pass/fail maxSize values, see below), the following
should hold true:

 schema.StringConstraint(32).maxSize() == 97

Now, schemas which represent containers have size limits that are the sum of
their contents, plus some overhead (and a stack level) for the container
itself. For example, a list of two small integers is represented in newbanana
as:

 OPEN(list)
  INT
  INT
 CLOSE()

which really looks like:

 opencount-OPEN
  len-STRING-"list"
  value-INT
  value-INT
 opencount-CLOSE

This sequence takes at most:

 opencount-OPEN: 64+1
 len-STRING-"list": 64+1+1000  (opentypes are confined to be <= 1k long)
 value-INT: 64+1
 value-INT: 64+1
 opencount-CLOSE: 64+1

or 5*(64+1)+1000 = 1325, or rather:

  3*(64+1)+1000 + N*(IntConstraint().maxSize())

So ListConstraint.maxSize is computed by doing some math involving the
.maxSize value of the objects that go into it (the ListConstraint.constraint
attribute). This suggests a recursive algorithm. If any constraint is
unbounded (say a ListConstraint with no limit on the length of the list),
then maxSize() raises UnboundedSchema to indicate that there is no limit on
the size of a conforming string. Clearly, if any constraint is found to
include itself, UnboundedSchema must also be raised.

This is a loose upper bound. For example, one non-conforming input string
would be:

 opencount-OPEN: 64+1
 len-STRING-"x"*1000: 64+1+1000

The entire string would be accepted before checking to see which opentypes
were valid: the ListConstraint only accepts the "list" opentype and would
reject this string immediately after the 1000th "x" was received. So a
tighter upper bound would be 2*65+1000 = 1130.

In general, the bound is computed by walking through the deserialization
process and identifying the largest string that could make it past the
validity checks. There may be later checks that will reject the string, but
if it has not yet been rejected, then it still represents exposure for a
memory consumption DoS.

** pass/fail sizes

I started to think that it was necessary to have each constraint provide two
maxSize numbers: one of the largest sequence that could possibly be accepted
as valid, and a second which was the largest sequence that could be still
undecided. This would provide a more accurate upper bound because most
containers will respond to an invalid object by abandoning the rest of the
container: i.e. if the current active constraint is:

 ListConstraint(StringConstraint(32), maxLength=30)

then the first thing that doesn't match the string constraint (say an
instance, or a number, or a 33-character string) will cause the ListUnslicer
to go into discard-everything mode. This makes a significant difference when
the per-item constraint allows opentypes, because the OPEN type (a string) is
constrained to 1k bytes. The item constraint probably imposes a much smaller
limit on the set of actual strings that would be accepted, so no
kilobyte-long opentype will possibly make it past that constraint. That means
there can only be one outstanding invalid object. So the worst case (maximal
length) string that has not yet been rejected would be something like:

  OPEN(list)
   validthing [0]
   validthing [1]
    ...
   validthing [n-1]
   long-invalid-thing

because if the long-invalid thing had been received earlier, the entire list
would have been abandoned.

This suggests that the calculation for ListConstraint.maxSize() really needs
to be like
  overhead
  +(len-1)*itemConstraint.maxSize(valid)
  +(1)*itemConstraint.maxSize(invalid)

I'm still not sure about this. I think it provides a significantly tighter
upper bound. The deserialization process itself does not try to achieve the
absolute minimal exposure (i.e., the opentype checker could take the set of
all known-valid open types, compute the maximum length, and then impose a
StringConstraint with that length instead of 1000), because it is, in
general, a inefficient hassle. There is a tradeoff between computational
efficiency and removing the slack in the maxSize bound, both in the
deserialization process (where the memory is actually consumed) and in
maxSize (where we estimate how much memory could be consumed).

Anyway, maxSize() and maxDepth() (which is easier: containers add 1 to the
maximum of the maxDepth values of their possible children) need to be
implemented for all the Constraint classes. There are some tests (disabled)
in test_schema.py for this code: those tests assert specific values for
maxSize. Those values are probably wrong, so they must be updated to match
however maxSize actually works.

* decide upon what the "Shared" constraint should mean

The idea of this one was to avoid some vulnerabilities by rejecting arbitrary
object graphs. Fundamentally Banana can represent most anything (just like
pickle), including objects that refer to each other in exciting loops and
whorls. There are two problems with this: it is hard to enforce a schema that
allows cycles in the object graph (indeed it is tricky to even describe one),
and the shared references could be used to temporarily violate a schema.

I think these might be fixable (the sample case is where one tuple is
referenced in two different places, each with a different constraint, but the
tuple is incomplete until some higher-level node in the graph has become
referenceable, so [maybe] the schema can't be enforced until somewhat after
the object has actually finished arriving).

However, Banana is aimed at two different use-cases. One is kind of a
replacement for pickle, where the goal is to allow arbitrary object graphs to
be serialized but have more control over the process (in particular we still
have an unjellyableRegistry to prevent arbitrary constructors from being
executed during deserialization). In this mode, a larger set of Unslicers are
available (for modules, bound methods, etc), and schemas may still be useful
but are not enforced by default.

PB will use the other mode, where the set of conveyable objects is much
smaller, and security is the primary goal (including putting limits on
resource consumption). Schemas are enforced by default, and all constraints
default to sensible size limits (strings to 1k, lists to [currently] 30
items). Because complex object graphs are not commonly transported across
process boundaries, the default is to not allow any Copyable object to be
referenced multiple times in the same serialization stream. The default is to
reject both cycles and shared references in the object graph, allowing only
strict trees, making life easier (and safer) for the remote methods which are
being given this object tree.

The "Shared" constraint is intended as a way to turn off this default
strictness and allow the object to be referenced multiple times. The
outstanding question is what this should really mean: must it be marked as
such on all places where it could be referenced, what is the scope of the
multiple-reference region (per- method-call, per-connection?), and finally
what should be done when the limit is violated. Currently Unslicers see an
Error object which they can respond to any way they please: the default
containers abandon the rest of their contents and hand an Error to their
parent, the MethodCallUnslicer returns an exception to the caller, etc. With
shared references, the first recipient sees a valid object, while the second
and later recipient sees an error.


* figure out Deferred errors for immutable containers

Somewhat related to the previous one. The now-classic example of an immutable
container which cannot be created right away is the object created by this
sequence:

        t = ([],)
        t[0].append((t,))

This serializes into (with implicit reference numbers on the left):

[0] OPEN(tuple)
[1]  OPEN(list)
[2]   OPEN(tuple)
[3]    OPEN(reference #0)
      CLOSE
     CLOSE
    CLOSE

In newbanana, the second TupleUnslicer cannot return a fully-formed tuple to
its parent (the ListUnslicer), because that tuple cannot be created until the
contents are all referenceable, and that cannot happen until the first
TupleUnslicer has completed. So the second TupleUnslicer returns a Deferred
instead of a tuple, and the ListUnslicer adds a callback which updates the
list's item when the tuple is complete.

The problem here is that of error handling. In general, if an exception is
raised (perhaps a protocol error, perhaps a schema violation) while an
Unslicer is active, that Unslicer is abandoned (all its remaining tokens are
discarded) and the parent gets an Error object. (the parent may give up too..
the basic Unslicers all behave this way, so any exception will cause
everything up to the RootUnslicer to go boom, and the RootUnslicer has the
option of dropping the connection altogether). When the error is noticed, the
Unslicer stack is queried to figure out what path was taken from the root of
the object graph to the site that had an error. This is really useful when
trying to figure out which exact object cause a SchemaViolation: rather than
being told a call trace or a description of the *object* which had a problem,
you get a description of the path to that object (the same series of
dereferences you'd use to print the object: obj.children[12].peer.foo.bar).

When references are allowed, these exceptions could occur after the original
object has been received, when that Deferred fires. There are two problems:
one is that the error path is now misleading, the other is that it might not
have been possible to enforce a schema because the object was incomplete.

The most important thing is to make sure that an exception that occurs while
the Deferred is being fired is caught properly and flunks the object just as
if the problem were caught synchronously. This may involve discarding an
otherwise complete object graph and blaming the problem on a node much closer
to the root than the one which really caused the failure.

* adaptive VOCAB compression

We want to let banana figure out a good set of strings to compress on its
own. In Banana.sendToken, keep a list of the last N strings that had to be
sent in full (i.e. they weren't in the table). If the string being sent
appears more than M times in that table, before we send the token, emit an
ADDVOCAB sequence, add a vocab entry for it, then send a numeric VOCAB token
instead of the string.

Make sure the vocab mapping is not used until the ADDVOCAB sequence has been
queued. Sending it inline should take care of this, but if for some reason we
need to push it on the top-level object queue, we need to make sure the vocab
table is not updated until it gets serialized. Queuing a VocabUpdate object,
which updates the table when it gets serialized, would take care of this. The
advantage of doing it inline is that later strings in the same object graph
would benefit from the mapping. The disadvantage is that the receiving
Unslicers must be prepared to deal with ADDVOCAB sequences at any time (so
really they have to be stripped out). This disadvantage goes away if ADDVOCAB
is a token instead of a sequence.

Reasonable starting values for N and M might be 30 and 3.

* write oldbanana compatibility code?

An oldbanana peer can be detected because the server side sends its dialect
list from connectionMade, and oldbanana lists are sent with OLDLIST tokens
(the explicit-length kind).


* add .describe methods to all Slicers

This involves setting an attribute between each yield call, to indicate what
part is about to be serialized.


* serialize remotely-callable methods?

It might be useful be able to do something like:

 class Watcher(pb.Referenceable):
     def remote_foo(self, args): blah

 w = Watcher()
 ref.callRemote("subscribe", w.remote_foo)

That would involve looking up the method and its parent object, reversing
the remote_*->* transformation, then sending a sequence which contained both
the object's RemoteReference and the appropriate method name.

It might also be useful to generalize this: passing a lambda expression to
the remote end could stash the callable in a local table and send a Callable
Reference to the other side. I can smell a good general-purpose object
classification framework here, but I haven't quite been able to nail it down
exactly.

* testing

** finish testing of LONGINT/LONGNEG

test_banana.InboundByteStream.testConstrainedInt needs implementation

** thoroughly test failure-handling at all points of in/out serialization

places where BananaError or Violation might be raised

sending side:
 Slicer creation (schema pre-validation? no): no no
  pre-validation is done before sending the object, Broker.callFinished,
  RemoteReference.doCall
  slicer creation is done in newSlicerFor

 .slice (called in pushSlicer) ?
 .slice.next raising Violation
 .slice.next returning Deferrable when streaming isn't allowed
 .sendToken (non-primitive token, can't happen)
 .newSlicerFor (no ISlicer adapter)
 top.childAborted

receiving side:
 long header (>64 bytes)
 checkToken (top.openerCheckToken)
 checkToken (top.checkToken)
 typebyte == LIST (oldbanana)
 bad VOCAB key
 too-long vocab key
 bad FLOAT encoding
 top.receiveClose
 top.finish
 top.reportViolation
 oldtop.finish (in from handleViolation)
 top.doOpen
 top.start
plus all of these when discardCount != 0
OPENOPEN

send-side uses:
 f = top.reportViolation(f)
receive-side should use it too (instead of f.raiseException)

** test failure-handing during callRemote argument serialization

** implement/test some streaming Slicers

** test producer Banana

* profiling/optimization

Several areas where I suspect performance issues but am unwilling to fix
them before having proof that there is a problem:

** Banana.produce

This is the main loop which creates outbound tokens. It is called once at
connectionMade() (after version negotiation) and thereafter is fired as the
result of a Deferred whose callback is triggered by a new item being pushed
on the output queue. It runs until the output queue is empty, or the
production process is paused (by a consumer who is full), or streaming is
enabled and one of the Slicers wants to pause.

Each pass through the loop either pushes a single token into the transport,
resulting in a number of short writes. We can do better than this by telling
the transport to buffer the individual writes and calling a flush() method
when we leave the loop. I think Itamar's new cprotocol work provides this
sort of hook, but it would be nice if there were a generalized Transport
interface so that Protocols could promise their transports that they will
use flush() when they've stopped writing for a little while.

Also, I want to be able to move produce() into C code. This means defining a
CSlicer in addition to the cprotocol stuff before. The goal is to be able to
slice a large tree of basic objects (lists, tuples, dicts, strings) without
surfacing into Python code at all, only coming "up for air" when we hit an
object type that we don't recognize as having a CSlicer available.

** Banana.handleData

The receive-tokenization process wants to be moved into C code. It's
definitely on the critical path, but it's ugly because it has to keep
calling into python code to handle each extracted token. Maybe there is a
way to have fast C code peek through the incoming buffers for token
boundaries, then give a list of offsets and lengths to the python code. The
b128 conversion should also happen in C. The data shouldn't be pulled out of
the input buffer until we've decided to accept it (i.e. the
memory-consumption guarantees that the schemas provide do not take any
transport-level buffering into account, and doing cprotocol tokenization
would represent memory that an attacker can make us spend without triggering
a schema violation). Itamar's CLineReceiver is a good example: you tokenize
a big buffer as much as you can, pass the tokens upstairs to Python code,
then hand the leftover tail to the next read() call. The tokenizer always
works on the concatenation of two buffers: the tail of the previous read()
and the complete contents of the current one.

** Unslicer.doOpen delegation

Unslicers form a stack, and each Unslicer gets to exert control over the way
that its descendents are deserialized. Most don't bother, they just delegate
the control methods up to the RootUnslicer. For example, doOpen() takes an
opentype and may return a new Unslicer to handle the new OPEN sequence. Most
of the time, each Unslicer delegates doOpen() to their parent, all the way
up the stack to the RootUnslicer who actually performs the UnslicerRegistry
lookup.

This provides an optimization point. In general, the Unslicer knows ahead of
time whether it cares to be involved in these methods or not (i.e. whether
it wants to pay attention to its children/descendants or not). So instead of
delegating all the time, we could just have a separate Opener stack.
Unslicers that care would be pushed on the Opener stack at the same time
they are pushed on the regular unslicer stack, likewise removed. The
doOpen() method would only be invoked on the top-most Opener, removing a lot
of method calls. (I think the math is something like turning
avg(treedepth)*avg(nodes) into avg(nodes)).

There are some other methods that are delegated in this way. open() is
related to doOpen(). setObject()/getObject() keep track of references to
shared objects and are typically only intercepted by a second-level object
which defines a "serialization scope" (like a single remote method call), as
well as connection-wide references (like pb.Referenceables) tracked by the
PBRootUnslicer. These would also be targets for optimization.

The fundamental reason for this optimization is that most Unslicers don't
care about these methods. There are far more uses of doOpen() (one per
object node) then there are changes to the desired behavior of doOpen().

** CUnslicer

Like CSlicer, the unslicing process wants to be able to be implemented (for
built-in objects) entirely in C. This means a CUnslicer "object" (a struct
full of function pointers), a table accessible from C that maps opentypes to
both CUnslicers and regular python-based Unslicers, and a CProtocol
tokenization code fed by a CTransport. It should be possible for the
python->C transition to occur in the reactor when it calls ctransport.doRead
python->and then not come back up to Python until Banana.receivedObject(),
at least for built-in types like dicts and strings.