From 5a58f183112b6a9d6bc2e0a3531df60172cddda3 Mon Sep 17 00:00:00 2001 From: Alex Auvolat Date: Mon, 1 Dec 2014 21:10:35 +0100 Subject: Add version 2! --- doc/spec-2.html | 2015 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ doc/spec-2.pdf | Bin 0 -> 139916 bytes 2 files changed, 2015 insertions(+) create mode 100644 doc/spec-2.html create mode 100644 doc/spec-2.pdf diff --git a/doc/spec-2.html b/doc/spec-2.html new file mode 100644 index 0000000..a393467 --- /dev/null +++ b/doc/spec-2.html @@ -0,0 +1,2015 @@ + + + + + No title + + + + + + + + +
+ + + +
The NARP protocol specification +
+ + + +
A Generic Recursive Communication Protocol for + Networked Applications
+

+ In this document we explain the purpose and provide a draft + specification for the NARP protocol, a general-purpose networking + protocol destined to be used in many layers of a new operating system + and networking system. +

+

1Introduction

+

+ We begin by remarking that a basic operation in all computer operation + processes consists in naming objects and providing acces to these named + objects. Here are a few examples of naming in real use cases: +

+ +

+ We propose here a novel architecture with the purpose of unifying all + the naming happening at all levels of the system, with two base concepts + : objects and service. +

+ +

+ We suggest that a NARP service may be provided on any bidirectionnal + channel of communication supporting the (reliable) sending and recieving + of messages. In addition, NARP objects may implement such a send/recieve + interface ; therefore a NARP service can be channeled into an object. + Such a construction of using a NARP object to access a NARP service is a + fundamental operation that we call recursive multiplexing, or + just multiplexing. +

+

+ The NARP protocol is a client/server protocol meant to include a variety + of different operations that may or may not be implemented by a specific + NARP server. +

+

2High-level overview

+

2.1The basic operations on services and + objects

+

+ A NARP service is basically any object that implements the following + operations: +

+ +

+ A NARP object is basically any object that implements the following + operations : +

+ +

2.2The basics of the NARP protocol

+

+ Given any interface with send/recieve capabilities considered as an + assymetric (client/server) configuration, the following client messages + consitute the basics of the NARP protocol for providing a NARP service + on the interface: +

+ +

+ The server may also at any moment send a message, including: +

+ +

2.3Recursion

+

+ If an object is a NARP server, the messages sent to it and recieved from + it are messages of the NARP protocol. Otherwise, they are arbitrary. +

+

2.4Reverse object

+

+ Some NARP servers may support reverse object serving: the client creates + an object on the server and handles all the requests arriving to this + object (therefore the initial NARP server only serves as a relay between + the new server and its clients +

+

+
+
+

+ 1. Research is to be done on shortcutting mechanisms in + specific situations where too many levels of recursion cause a + performance issue. +

+
+
+
+

+ + + 1 + ). A client wishing to act as a reverse object server may use the + following commands: +

+ +

+ The server may in turn send the following messages concerning the server + object: +

+ +

+ Once a client is attached to the object, a classical send/recieved + interface is provided. +

+

+ Typically, the protocol exchanged over the object is NARP protocol, + therefore enabling the reverse server to provide its own namespace and + other functionnality. +

+

2.5Specific object types and associated + messages

+

2.5.1Objects are sockets

+

+ Sockets are the basis of the NARP protocol : attaching to an objects + opens a socket connection to the process serving the object, and when + the connection is accepted, basic send/recieve functionnality is + provided. See also the reverse object protocol described in section 2.4. +

+

2.5.2File objects

+

+ Small files may implement the following interface: +

+ +

+ Big files may implement the following interface: +

+ +

2.5.3User IO (terminals…)

+

+ Virtual terminals can be seen as objects implementing a simple + send/recieve semantic, where the data transmitted is unstructured (or + structured given a specific terminal data structure). More specific + interfaces can be defined for advanced terminals and GUIs. +

+

2.5.4Specific applications

+

+ Specific applications may define custom messages. Examples include: +

+ +

+ and many other applications yet to be invented. +

+

2.6Big messages

+

+ The message size in the NARP protocol is limited to 64kb, and + recommended not to exceed 4kb+header (4kb is the size of a memory page + on many machines). Therefore a possibility would be for the NARP + protocol to include a way to transmit big messages by fragmenting them + into small messages. Optionnal error correction may be included. This + can be useful for example when using put or get + on large files, or reads and writes of + big file portions. The recieving of a large fragmented message may have + a specific implementation allowing the reciever to work with the partial + data as soon as it starts arriving and not having to wait for the whole + message to be transmitted and buffered. Research is yet to be done on + this specific subject. +

+

2.7Permissions

+

+ For each attached client the server may keep track of associated + permissions, and accept or reject requests according to those + permissions. The client may use an authentication command to gain + supplementary privileges on the server's ressources. The client may + request a token to delegate it's privileges on a given object to another + client. Advanced right management functionnalities are to be discussed. +

+

2.8Reliability concerns

+

+ The NARP protocol relies on the fact that when transmitting a message, + the other end will recieve it. It is nevertheless recommended that NARP + implementations support the repeating of messages if an expected + acknowlegment has not arrived after a given delay. +

+

2.9Example NARP servers

+

2.9.1Virtual NARP server (i.e. NARP + router)

+

+ This server implements a namespace where any client may create an empty + object and serve connections to it. Additionnaly, the server may + implement the possibility to create virtual files, virtual directories, + FIFO queues, etc. +

+

+ This server may be connected to other virtual NARP servers in order to + provide a global namespace accessible to all. Each virtual NARP server + acts as an endpoint into the network and may have functionnality for + routing the communications to objects to the clients that serve them. +

+

2.9.2NARP file server

+

+ This server simply implements access to a filesystem : listed ressources + are the same as the files present in a served directory, each of these + implements the filing protocol (served directly by the file server), and + the creation of files/directories may also be implemented. +

+

2.9.3NARP terminal/GUI server

+

+ Clients may create objects on the server ; each of these objects + correspond to a GUI window. Two interfaces may be implemented : text IO + (terminal) and graphical interaction. Advanced terminal interaction + features may be implemented at the protocol level, such as + auto-completion of commands or of text being edited… +

+

+ Suggestion for a third kind of window : the data sent by the client + corresponds to a description of the scene in a given markup language and + the server does the rendering. The client can also subscribed to events + such as clicking on an item or entering text. This possibility is to be + explored. +

+

2.9.4NARP e-mail and newsgroup server

+

+ Several features to be implemented: +

+ +

2.9.5NARP chat server

+ +

2.9.6NARP applicative server

+

+ TODO… +

+

3Specifics of the NARP protocol

+

3.1Protocol description format

+

+ A protocol message is given in the following form: +

+ + + + + + + + + + + + +
element typeelement typeelement type
element descriptionelement descriptionelement description
+

+ The following element types apply: +

+ +

3.2Basic message format

+

+ The basic format of a message is : +

+ + + + + + + + + + +
int16int16*
message sizemessage typepayload
+

+ We will abbreviate by “header” the first 32 bits (4 bytes) + of the message. The list of message types is given in section 3.7.1. +

+

+ Messages for communication with an attached ressource will have the + following format : +

+ + + + + + + + + + + + +
int16int16int32*
message sizemessage typeressource descriptor (handle)payload
+

+ Many client messages awating a response will have a message ID included + ; this message ID is an arbitrary number generated by the client and + used by the server when giving its response. The header then looks like + this: +

+ + + + + + + + + + + + +
int16int16int32*
message sizemessage typemessage IDpayload
+

3.3Message list for core NARP protocol

+

+ Client messages have an up arrow () next to their name, + while server messages have a down arrow (). +

+

+ The core NARP protocol is meant for small size and rapidity (so that + many layers can be encapsulated with minimal overhead), therefore no + acknowlegment is to be sent for recursive send/recieve messages. Other + messages usually imply some kind of action or getting of information, + therefore an acknowlegment or an error is usually sent as a response. +

+

+

Hello
+

+

+

+

+ + + + + + + + + + +
int32arr(int32)
headerversionlist of needed/provided interfaces
+ +

+
+
+

+ When a NARP connection is established, the client is always the + first to send a Hello message. The object may then + respond either with a Hello message indicating that + the requested interfaces can be provided, or with an + Error message. The two common error causes are + interface not implemented and incompatible + versions. +

+
+
+

+ For interface numbers : see table in section 3.7.3. +

+
+

+

+

Error
+

+

+

+

+ Generic error response message for any operation. +

+
+
+ + + + + + + + + + + + +
int32int32str
headerrequest IDerror IDerror string
+
+
+

+ Common error IDs are specified in section 3.7.2. +

+
+

+

+

Ack
+

+

+

+ + + + + + + + +
int32
headerrequest ID
+
+

+ +

+
+

+ Generic acknowlegment message for commands that require it. An + acknowlege implies the command has been sucessfully executed + (otherwise an error message is sent). +

+
+

+

+

Stat
+

+

+

+ + + + + + + + + + +
int32str
headerrequest IDfilename
+
+

+ +

+
+

+ The request ID is an ID decided by the client so that it can + identify the answer. +

+
+

+

+

StatR
Response to the + Stat message. +

+

+

+ + + + + + + + + + +
int32arr(int32)
headerrequest IDimplemented interface
+
+
+

+ Common interface numbers are to be found in section 3.7.3. +

+

+ If a Stat query on an object gives a certain list + of interfaces, then when connecting to the object at least all these + interfaces must be included in the server's Hello + message as supported interfaces. +

+
+
+

+ Note that some interface numbers correspond to actions that can be + done on the object from the connection where the object exists (e.g. + : symbolic link, directory), and others correspond to actions that + can be performed after attaching to the object (e.g. file, terminal, + …) +

+
+

+

+

List
+

+
+ + + + + + + + + + + + + + +
int32int32int32str
headerrequest IDfirst entry numbernumber of entries requestedbase path string
+
+

+

ListR
Response to the + List message. +

+

+

+

+ One message is passed for each entry in the requested range: +

+
+
+ + + + + + + + + + + + +
int32int32str
headerrequest IDentry numberentry name
+
+
+

+ After the directory has finished being enumerated, a supplementary + entry is given with entry number the last valid entry number plus + one and an empty entry name. This supplementary entry is only given + if its (ficious) entry number is included in the range requested by + the client. +

+
+

+

+ Possible extension : combine List and Stat so that when the answer to + List is given, information is also given on the object's implemented + interfaces. +

+

+

Attach
+

+
+ + + + + + + + + + +
int32str
headerrequest IDfilename
+
+

+

Attached
Response to the + Attach command. +

+

+

+ + + + + + + + + + +
int32int32
headerrequest IDhandle
+
+

+ +

+
+

+ (the handle, ie the ressource descriptor, is attributed by the + server) +

+
+

+

+

Send
+

+

+

+ + + + + + + + + + +
int32*
headerhandlepayload
+
+

+ +

+
+

+ This message does not expect a response. +

+
+

+

+

Recieve
+

+

+

+

+ Spontaneous server message indicating some data is sent by an + attached ressource. This message does not expect a response. +

+
+

+ +

+
+ + + + + + + + + + +
int32*
headerhandlepayload
+
+

+

+

Detach
+

+

+

+ + + + + + + + +
int32
headerhandle
+
+

+ +

+
+

+ This message does not expect a response. +

+
+

+

+

Detached
+

+

+

+

+ Spontaneous server message indicating the object has been detached. +

+
+

+ +

+
+ + + + + + + + +
int32
headerhandle
+
+

+

+

Create
+

+

+

+ + + + + + + + + + + + +
int32arr(int32)str
headerrequest IDneeded interfacespath
+
+

+ +

+
+

+ A create request is accompanied with a list of needed interfaces + that direct the server into creating the corresponding type of + object (e.g. an empty object to be served, a directory, a file, + …) +

+
+

+

+

Created
Response to the + Create command. +

+

+

+ + + + + + + + + + +
int32arr(int32)
headerrequest IDimplemented interfaces
+
+

+ +

+
+

+ Signals that the object has been created, and has corresponding + interfaces associated to it. +

+
+

+

+

Delete
+

+

+

+ + + + + + + + + + +
int32str
headerrequest IDpath
+
+

+ +

+
+

+ This message expects a standard Ack response + message. +

+
+

+

+

Link
+

+

+

+ + + + + + + + + + + + +
int32strstr
headerrequest IDdestination pathlink path
+
+
+

+ This message expects a standard Ack response + message. +

+

+ Semantics of the link object: +

+
+
+ +
+

+

+

ReadLink
+

+
+ + + + + + + + + + +
int32str
headerrequest IDpath
+
+

+

ReadLinkR
Response to the + ReadLink message. +

+

+

+ + + + + + + + + + +
int32str
headerrequest IDlink description
+
+

+ +

+
+

+ This will only return the first level of linking, ie the link data + directly associated to the link object. +

+
+

+

+

Rename
+

+

+

+ + + + + + + + + + + + +
int32strstr
headerrequest IDoriginal pathnew path
+
+

+ +

+
+

+ This message expects a standard Ack response + message. +

+
+

+

+

Serve
+

+

+

+ + + + + + + + + + + + +
int32strarray(int32)
headerrequest IDpathannounced interfaces
+
+
+

+ This message is a request for the client to be a reverse server to + an object. The response message to this message is an + Attached message. The handle attributed to the + served object is known as the server handle and is used in + the Incoming and Detach messages. +

+

+ To stop serving an object, the client simply sends a + Detach command on the server handle. The semantics + is that all connections that have been openned through the + reverse-served object are preserved when the object stops being + served, and an individual Detach message must be + sent to all of them if we want to close them. +

+
+
+

+ The announced interfaces serves to answer + Stat messages on the object while we are serving + it. +

+
+

+

+

Incoming
+

+

+

+ + + + + + + + + + +
int32int32
headerserver handleclient hande
+
+

+ +

+
+

+ This message is sent by the server when another client wishes to + attach to an object reverse-served by this client. The server handle + is the one given as a response to the Serve + message. The client handle is a handle associated to the connection. + The reverse server may reject the connection by issuing a + Detach command on the client handle, or may accept + it using the Accept message given below. +

+
+

+

+

Accept
+

+

+

+ + + + + + + + +
int32
headerclient handle
+
+

+ +

+
+

+ Once a connection has been accepted, the reverse server may at any + moment close it by sending a Detach command on the + corresponding client handle. +

+
+

+

+

Unbox
+

+

+

+ + + + + + + + + + + + +
int32int32int32
headerrequest IDouter handleinner handle
+
+
+

+ Consider the handle outer handle as a NARP protocol + service, and associate a handle in the outer layer to the handle of + the inner layer with handle inner handle. +

+

+ Example : in connection A we have a connection open on handle 5 + which contains NARP data that we will call B, and in connection B we + have another connection open on handle 7. Issuing a Unbox(id, 5, 7) + request on A will lead to the server creating a handle (say 12) + where sending corresponds to sending a message to handle 7 on + connection B, and such that all messages recieved on handle 5 (ie on + connection B) are filtered and messages whose destination is handle + 7 on connection B are removed from the stream and issued on handle + 12 of connection A instead. +

+

+ The answer to such a request is an Attached + response giving a handle to the unboxed connection. +

+
+
+

+ Systematically unboxing open connections may lead in some cases to + the network infrastructure being able to do simplifications in the + interconnections. In other cases it may result to useless overhead + on the server side : in such a case the server may refuse an unbox + request. +

+
+

+

+

Plug
+

+

+

+ + + + + + + + + + + + +
int32int32int32
headerrequest IDhandle Ahandle B
+
+
+

+ Ask the server to redirect all messages recieved on handle A to + handle B and all mesages recieved on handle B to handle A. The + messages recieved on either handle are not sent to the client + anymore. +

+
+
+

+ The answer messages are standard + Ack/Error messages. +

+
+

+

+

Unplug
+

+

+

+ + + + + + + + + + + + +
int32int32int32
headerrequest IDhandle Ahandle B
+
+

+ +

+
+

+ Undoes a plugging. +

+
+

+

3.4Big message protocol

+

+ To be defined. Is it really usefull? What role exactly does it have? Can + it implement repetition in the case where the message hasn't been + acknowledge? … +

+

3.5Authentification and rights managment + commands

+

+

Authenticate
+

+

+

+ + + + + + + + + + + + +
int32int32*
headermessage IDauthentification methodauthentification data
+
+
+

+ Used to gain access using credentials (user/password, token, + …). Response messages are standard Ack on + success or Error on failure. Autentification + methods include : +

+
+
+ +
+

+

+

NewToken
+

+

+

+ + + + + + + + + + +
int32str
headermessage IDpath
+
+

+ +

+
+

+ Requests the server to create an authentication token for accessing + a given object with the privileges of the connected client. Once the + token has been returned, it may be transmitted to another client so + that that client will use it to gain same access to the object. +

+
+

+

+

NewTokenR
Response to the + NewToken message. +

+
+ + + + + + + + + + +
int32str
headermessage IDtoken
+
+

+ TODO : request account creation, manage user groups and ACLs, … +

+

3.6TODO

+ +

3.7Table of IDs

+

+ The tables presented in this section give the number associated to the + message types. These tables are the reference on the subject ; any + information found somewhere else is wrong if it is not the same as found + here. This is for protocol version 1. +

+

3.7.1Message types

+

+

Base protocol
+

+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
message id idmessage id id
Hello010000Stat / StatR1010010
Error10001List / ListR1110011
Ack10002Create / Created1210012
Delete13
Attach / Attached510005Rename14
Send / Recieve610006Link15
Detach / Detached710007ReadLink / + ReadLinkR1610016
Serve8
Incoming10008Unbox20
Accept9Plug21
Unplug22
+
+

+

Authentication & privileges
+

+
+ + + + + + + + + + + + + + +
message id id
Authenticate30
NewToken / + NewTokenR3110031
+
+

3.7.2Error messages

+
+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
idcause
1Incompatible versions
2Command/interface not implemented
3Invalid request (e.g. : out of bounds)
4Invalid handle
5Attach request rejected
6Action impossible because object is in use (cannot + delete, …)
7No such object (invalid path)
8Could not resolve link
9Incorrect credentials
10Unauthorized
+
+

3.7.3Object interfaces

+
+

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
idnamemust implement messages
0servableServe, Accept, + Incoming
1enumerableList, ListR
2is symlinkReadLink, + ReadLinkR
9non-NARP insideonce attached, inside data is arbitrary
10NARP serviceonce attached, inside data is a NARP service (ie has + objects, …)
11NARP unboxonce attached, Unbox command + supported
12NARP plugonce attached, Plug and + Unplug commands supported
20fileonce attached, file semantics
21terminalonce attached, terminal semantics
22graphics windowonce attached, GUI semantics
+ +

+
+

+

Servable
This interface specifies that the object is + currently an empty object waiting for someone to issue a + Serve command on it, providing it with an + implementation of some interfaces. +

+

+

non-NARP inside
This interfaces indicates that once + attached to the object, the messages sent/recieved to it are not + supposed to be NARP format but any arbitrary format. If this interface + is not specified, then it is expected that the messages transmitted will + follow the general NARP protocol (message format, standard + hello/ack/error messages). +

+

+

NARP service
This interface indicates that once + attached to the object, one can have access to a new NARP namespace + where at least the following operations are supported : + Stat, Attach, Send, + Recieve, Detach. Additionnal messages + may or may not be supported. +

+

4Architecture of a NARP implementation in + OCaml or Haskell

+

+ An asynchronous implementation can be easily programmed in functionnal + languages such as OCaml or Haskell, using closures as continuations for + what to do when a (response) message arrives. +

+

+ TODO +

+

5Using NARP to design an Operating System

+

+ When designing the NARP protocol, we had in mind that it would be + possible to use it in a new operating system design at many levels : + access to devices, process management, memory management, filesystems, + IPC, GUI, … +

+

+ Kernel helpers could be developped so that a part of the NARP + multiplexing and demultiplexing takes place in kernel land, before + messages are passed to userspace. For instance, this would allow the + simplification of useless mux-demux chains taking place on the same + machine. The mux-demux helper can be implemented via the + Unbox protocol message, handled at the level of the + root stream of NARP communication with the kernel. Another possible + helper would be to map a virtual memory region to a NARP ressource + implementing a standard filing protocol, much like memory mapped files + in standard OSes (only this would work with arbitrary ressources). +

+

+ In this section we will develop on a concrete proposal for a NARP-based + operating system. +

+

5.1Architecture of the OS

+

+ The basic primitive of the system being message-passing, the system + looks a lot like a micro-kernel. Only the message format has a complex + semantic and the communication layer is not really “simple”. + Furthermore, the system has device drivers, file system and networking + running as kernel-mode processes, making the kernel more monolithic (but + still having a micro-kernel spirit). It should be easy to make any user + mode process run as a kernel mode process instead, for the sake of + performance (eg : graphical server & compositor). +

+

+ The kernel land is divided in three major parts, with strict dependency + order: +

+ +

+ User processes are restricted to syscalls that call level 1 primitives. +

+

+ Here are a few basic principles for the design of these three levels : +

+ +

5.2Steps of the developpment of the OS

+
    +
  1. +

    + Develop level 0 completely and with cleanest possible design +

    +
  2. +
  3. +

    + Develop level 1 with only basic funcionnality +

    +
  4. +
  5. +

    + Develop some basic applications in level 2 : display, keyboard, mini + kernel shell, mini file system, … +

    +
  6. +
  7. +

    + Improve level 1 with more complex stuff ; try to quickly attain a + complete level 1 +

    +
  8. +
  9. +

    + Work on the rest of the stuff +

    +
  10. +
+ + \ No newline at end of file diff --git a/doc/spec-2.pdf b/doc/spec-2.pdf new file mode 100644 index 0000000..231858b Binary files /dev/null and b/doc/spec-2.pdf differ -- cgit v1.2.3