CSC/ECE 517 Fall 2014/final design doc M1450 navr: Difference between revisions

From Expertiza_Wiki
Jump to navigation Jump to search
No edit summary
 
(67 intermediate revisions by 3 users not shown)
Line 19: Line 19:
The main objectives of this experimentation project is improving the layout to graphics rendering - to optimize for power efficiency and maximize parallelism. <ref> https://www.mozilla.org/en-US/research/projects/ </ref>
The main objectives of this experimentation project is improving the layout to graphics rendering - to optimize for power efficiency and maximize parallelism. <ref> https://www.mozilla.org/en-US/research/projects/ </ref>


=== Purpose ===
== Background ==


The purpose of this project is to introduce the support related to sessionstorage and localstorage in Servo Broswer, for this we have to create Storage structure and allow web pages to store data in the Servo memory space.
=== [http://html.spec.whatwg.org/multipage/webstorage.html#webstorage Web Storage] ===
The web storage specification defines the means by which a web application can store string key/value pairs in a browser and later retrieve them for use.<ref>https://developer.mozilla.org/en-US/docs/Web/Guide/API/DOM/Storage</ref> It supports persistent data storage, similar to [http://en.wikipedia.org/wiki/HTTP_cookie cookies] but with a greatly enhanced capacity and no information stored in the [http://en.wikipedia.org/wiki/List_of_HTTP_headers HTTP request header].<ref>http://en.wikipedia.org/wiki/Web_storage</ref> There are two types of web storage: [http://html.spec.whatwg.org/multipage/webstorage.html#dom-localstorage local storage] and [http://html.spec.whatwg.org/multipage/webstorage.html#dom-sessionstorage session storage].


=== Background ===
Browsers that support web storage have the global variables 'sessionStorage' and 'localStorage' declared at the [http://developer.mozilla.org/en-US/docs/Web/API/Window?redirectlocale=en-US&redirectslug=DOM%2Fwindow window] level. The following JavaScript code gives an example of how to use web storage:


Persistent storage on the web is used by many services such as the popular Disqus commenting interface. Implementing this important specification in Servo will allow stateful web applications to run, and will help expose any architectural problems that Servo's radical design may cause.
'''sessionStorage'''
<pre>
// Store value on browser for duration of the session
sessionStorage.setItem('key', 'value');
// Retrieve value (gets deleted when browser is closed and re-opened)
alert(sessionStorage.getItem('key'));
</pre>
 
'''localStorage'''
<pre>
// Store value on the browser beyond the duration of the session
localStorage.setItem('key', 'value');
// Retrieve value (persists even after closing and re-opening the browser)
alert(localStorage.getItem('key'));
</pre>
 
== Project Description ==
 
As part of our [http://github.com/servo/servo/wiki/Storage-student-project project], we have to implement the web storage specification in the Servo browser. Implementing this important specification in Servo will allow stateful web applications to run, and will help expose any architectural problems that Servo's radical design may cause. <ref> https://github.com/servo/servo/wiki/Storage-student-project</ref>
 
== Requirement Analysis <ref>https://github.com/servo/servo/wiki/Storage-student-project</ref> ==
 
In order to introduce the support for session storage and local storage in the Servo Browser, we have to create the Storage structure and allow web pages to store data in the Servo memory space.
 
Below is a overview of the various steps identified as part of requirement analysis:
 
'''Storage Interface'''
* We have to create the Storage interface and its stub implementation.
* This interface is used by the web pages to communicate to the web storage.


== Architecture ==
'''WindowSessionStorage Interface'''
* We have to create the WindowSessionStorage interface which will return a Storage instance.
* A web page will use this interface to access its session storage.


[[File:task.jpg]]
'''WebStorageTask'''
* We have to create a Storage Task which will be used to store all the web storage data.
* This is a separate thread which starts when browser starts.
* The class implementing the Storage interface uses it to store and retrieve the actual data.


'''Communication Channel'''
* It provides the means to communicate to the separate thread 'WebStorageTask'.
* We need to define a message-passing interface for reading and writing stored data for a particular browser tab and use it in the implementation of Storage interface to communicate to WebStorageTask.


The Architecture comprises of a Storage Task which will be responsible to hold all the data that the web page requests to save. This happens via Channels in Rust, which implements a Sender Receiver protocol, the task is runnning in the background and waits to receive the data sent from the web page.
'''Notification Event'''
* We need to notify the respective browser tab when the value of a stored data is changed so that other browser objects which may be using this data can take appropriate action.


=== Architecture Explained ===
'''Web Storage Tests'''
*Each box represents a Rust task.
* We need to pass as many [http://github.com/servo/web-platform-tests/tree/servo/webstorage tests] as possible.
*Blue boxes represent the primary tasks in the browser pipeline.
* These tests are part of the web storage specification. Any browser implementing the web storage interface must pass as many tests as possible out of these.
*Gray boxes represent tasks auxiliary to the browser pipeline.
 
*White boxes represent worker tasks. Each such box represents several tasks, the precise number of which will vary with the workload.
'''WindowLocalStorage Interface'''
*Dashed lines indicate supervisor relationships.
* We need to implement the WindowLocalStorage interface which behaves slightly different from the WindowSessionStorage interface.
*Solid lines indicate communication channels.
* This will provide the interface to access browser's local storage.


== Requirement Analysis <ref>https://github.com/servo/servo/wiki/Storage-student-project</ref> ==


As part of our [http://github.com/servo/servo/wiki/Storage-student-project project], we have to implement the [http://html.spec.whatwg.org/multipage/webstorage.html#webstorage Web Storage] specification in Servo. Implementing this important specification in Servo will allow stateful web applications to run, and will help expose any architectural problems that Servo's radical design may cause. <ref> https://github.com/servo/servo/wiki/Storage-student-project</ref>
== Implementation ==


Below is a high level overview of the various steps that need to be carried out to achieve this:
The implementation of the project was divided into the following milestones :
* '''Create and stub the Storage WebIDL interface defined in the spec :''' This milestone involved the initial creation of the Storage interface on which the entire project is based. The storage web idl was created as defined in the specifications : https://html.spec.whatwg.org/multipage/webstorage.html#storage-2


* Create the Storage interface and its stub implementation.
* '''Create and stub the WindowSessionStorage WebIDL interface defined in the spec, making it return a Storage instance''' : Once the Storage interface was created, we had to implement the interface to actually define the functions which were a part of the interface. Here we extended the Storage interface to specialize it as Session Storage interface namely WindowSessionStorage. The methods in this interface were then further implemented in Storage.rs which was made to return a Storage instance to the web page or application requiring the support of sessionstorage.
* Create the WindowSessionStorage interface making it return a Storage instance.
* Create a Storage Task which will be used to contain all stored data.
* Define a message-passing interface for reading and writing stored data for a particular browser tab.
* Use the Storage task in the implementation of Storage.
* When the value of a stored data is changed, notify its respective browser tab.
* Pass as many tests as possible.
* Implement the WindowLocalStorage interface which behaves slightly different from the WindowSessionStorage interface.


== Data Design ==
* '''Create a storage task (similar to the resource task) which will contain all stored data''' : The actual data is stored in a background task known as Storage Task, A task in rust terms is nothing but a thread which can run in the background keep polling until it is required, it does so by looping over a channel until a request comes its way. The Storage task contains a HashMap of TreeMap. The Hashmap is used to store the storage data for all the sites. Its keys represent the origin of the request (determined from the URL it is coming from). There is an entry in the HashMap for each different origin. The respective value represents the storage data for the site. This site specific data is stored as a TreeMap which maintains the <key , value> pair in a ordered fashion. Thus the storage task contains the actual data structure which holds all the values and the Storage.rs acts as a mediator between the object and the data stored in the task.


===  Data Description ===
* '''Define a message-passing interface for reading and writing stored data for a particular origin''': The Storage object requires a medium to delegate the functions to storage task where the actual implementation takes place. This is done using [http://doc.rust-lang.org/std/comm/fn.channel.html Channels]. There are 2 major channels. First one is the one which the storage task creates and keeps on listening for any the request. The other is when the storage object wants to get some data from the task. The Storage object creates a temporary channel on which it listens for any reply by the Storage task. This is how the message-passing interface has been implemented in the given milestone.


''The following are the data structures that will be used.''
* '''Store a channel to the storage task in the Page structure that sends messages from the previous interface, and make use of it in the implementation of Storage''': The storage object requires to know the channel on which the task is looping in order to send it requests for get, set or other functions. This is done by storing the channel that the storage task creates in the Page Structure which acts as a common object between these 2. Hence, by passing the created channel to the page structure it can now be accessed and utilized by the Storage object in order to delegate the methods onto the storage task and communicate.


'''Storage''' | TreeMap<String,String>
== Architecture <ref>https://github.com/servo/servo/wiki/Design</ref>==
[[File:task.jpg]]


'''UrlMap''' | TreeMap<String,TreeMap<String,String>>
=== Architecture Explained ===
*Each box represents a Rust task.
*Blue boxes represent the primary tasks in the browser pipeline.
*Gray boxes represent tasks auxiliary to the browser pipeline.
*White boxes represent worker tasks. Each such box represents several tasks, the precise number of which will vary with the workload.
*Dashed lines indicate supervisor relationships.
*Solid lines indicate communication channels.


== Component Design ==
== Component Design ==
[[File:servo.jpg]]
[[File:servo.jpg]]
=== Task ===
 
There will be a Storage Task which will be responsible to hold all the data that the web page requests to save. This happens via Channels in Rust, which implements a Sender Receiver protocol. The task is runnning in the background and waits to receive the data sent from the web page.
 
=== Task <ref>http://doc.rust-lang.org/guide-tasks.html</ref>===
Rust provides safe concurrent abstractions through a number of core library primitives. This guide will describe the concurrency model in Rust, how it relates to the Rust type system, and introduce the fundamental library abstractions for constructing concurrent programs.
Rust provides safe concurrent abstractions through a number of core library primitives. This guide will describe the concurrency model in Rust, how it relates to the Rust type system, and introduce the fundamental library abstractions for constructing concurrent programs.


Line 86: Line 130:
</pre>
</pre>


=== Channel ===
=== Channel <ref>http://doc.rust-lang.org/guide-tasks.html</ref>===
Now that we have spawned a new task, it would be nice if we could communicate with it. For this, we use channels. A channel is simply a pair of endpoints: one for sending messages and another for receiving messages.
Now that we have spawned a new task, it would be nice if we could communicate with it. For this, we use channels. A channel is simply a pair of endpoints: one for sending messages and another for receiving messages.


Line 102: Line 146:
</pre>
</pre>


== Design patterns ==
== Data Design ==


We will be using "Delegation Pattern" in our project. The Storage interface is used by web applications to access the Web Storage provided by the browser. However, the actual data is stored somewhere else(Database/FileSystem/Memory). So, it makes sense to create another class which will maintain the actual stored data. The Storage class can then delegate the task of storing/retrieving data to this class. We will create a class "WebStorageTask" for this purpose.
===  Data Description ===
 
''The following data structure has been used ''
 
'''StorageTask''' | HashMap<String, TreeMap<DomString,DomString>>
 
== Design Pattern ==
 
We have used the '''"Delegation Pattern"''' in our project. The Storage interface is used by web applications to access the web storage provided by the browser. However, the actual data is stored somewhere else(Servo Memory Space). So, it makes sense to create another class which should maintain the actual stored data. The Storage class can then delegate the task of storing/retrieving data to this class. We have created a class "StorageTask" for this purpose.
 
Also we are using an '''"Observer Pattern"''' where the Storage task runs in the background and observes the commands issued using a channel. It keeps on listening to changes on a port and as soon as it receives a message i.e. sees a call towards it, it performs the required function.


== UML diagrams (Eg use case diagram, class diagrams) ==
== UML Diagrams ==


[[File:Flow_Chart_Storage.png]][[File:Use_Case_Storage.jpg|right]]
=== Flow Chart ===
[[File:Flow_Chart_Storage.png]]
 
1. First, we need to build rust and servo. <br/>
2. Generate the corresponding WebIDL bindings - Storage.webidl <br/>
3. Define Storage.rs which has the actual code for creating the storage object. <br/>
4. Call the receiver via a channel- this is actually used for creating an instance for each unique URL. <br/>
5. Build the servo again. <br/>
 
=== Use Case Diagram ===
[[File:Use_Case_-_Storage.png‎]]
 
1. Here the user can open multiple domains( multiple URL's).<br/>
2. Thereby the user will be creating multiple storage instances.<br/>
3. An user can traverse deep into the website but the storage instance is same for that URL.<br/>
4. The user can reopen the domain for a later period.<br/>


== Proposed Test Cases ==
== Proposed Test Cases ==


To test the session storage in servo, we will be implementing the storage tasks. Some of the test cases for reference are:  
Some of the test cases which will be used to validate our changes are as follows:
* Clear session storage
 
* Set items in sessions storage
* Allow a web page to clear its session storage ''i.e. storage.clear() function should work''
* Get stored items from session storage
* Allow a web page to store an item in its session storage ''i.e. test storage.setitem(key,value)''
* Check the number of items storage in session storage
* Allow a web page to retrieve stored items from its session storage ''i.e. test storage.getitem(key)''
* On removing the item from storage, it should be inaccessible
* Do not allow a web page to retrieve stored items from the session storage of a web page in another domain ''i.e. try to access elements by forging url
* Check if out of range indexes give error
* Check the number of items stored in session storage i.e storage.count()''
* Access for out of range arguments as keys should return null
* On removing an item from storage, it should be inaccessible ''i.e check if storage.remove(key) is functional''
* Get an error on exceeding the limit of session storage
* Should return null as value for a key not present in the session storage ''i.e. test storage.getitem(key) for non-existent key''
* Should give an error on exceeding the space limit of session storage ''i.e check for available memory on each command''


You can find the detailed list of test cases at [https://github.com/servo/web-platform-tests/tree/servo/webstorage Webstorage Tests]
The complete list of test cases can be found [http://github.com/servo/web-platform-tests/tree/servo/webstorage here].


== Further Readings ==
== Further Readings ==

Latest revision as of 05:00, 4 December 2014

Implement Window.sessionStorage

This is the design document for the task Implement Window.sessionStorage for the Mozilla research project Servo.

Introduction

Rust

Rust is a modern systems programming language focusing on safety and speed to build reliable and efficient systems <ref> http://doc.rust-lang.org/nightly/intro.html </ref>. It accomplishes the goals of memory safe without using garbage collection and it supports concurrency and parallelism in building platforms.

Rust’s lightweight task mechanism also promises to allow fine-grained isolation between browser components, such as tabs and extensions, without the need for expensive runtime protection schemes, like operating system process isolation. <ref> https://www.mozilla.org/en-US/research/projects/ </ref>

Servo

Mozilla Research team is currently working on an experimental project to develop a new Web browser engine "Servo", that is capable of supporting a variety of current and next generation of hardware like mobile devices, multi-core processors and high-performance GPUs. Servo builds on top of Rust to provide a secure and reliable foundation. It is currently developed on 64 bit devices.<ref> https://www.mozilla.org/en-US/research/projects/ </ref>

The main objectives of this experimentation project is improving the layout to graphics rendering - to optimize for power efficiency and maximize parallelism. <ref> https://www.mozilla.org/en-US/research/projects/ </ref>

Background

Web Storage

The web storage specification defines the means by which a web application can store string key/value pairs in a browser and later retrieve them for use.<ref>https://developer.mozilla.org/en-US/docs/Web/Guide/API/DOM/Storage</ref> It supports persistent data storage, similar to cookies but with a greatly enhanced capacity and no information stored in the HTTP request header.<ref>http://en.wikipedia.org/wiki/Web_storage</ref> There are two types of web storage: local storage and session storage.

Browsers that support web storage have the global variables 'sessionStorage' and 'localStorage' declared at the window level. The following JavaScript code gives an example of how to use web storage:

sessionStorage

// Store value on browser for duration of the session
sessionStorage.setItem('key', 'value');
 
// Retrieve value (gets deleted when browser is closed and re-opened)
alert(sessionStorage.getItem('key'));

localStorage

// Store value on the browser beyond the duration of the session
localStorage.setItem('key', 'value');
 
// Retrieve value (persists even after closing and re-opening the browser)
alert(localStorage.getItem('key'));

Project Description

As part of our project, we have to implement the web storage specification in the Servo browser. Implementing this important specification in Servo will allow stateful web applications to run, and will help expose any architectural problems that Servo's radical design may cause. <ref> https://github.com/servo/servo/wiki/Storage-student-project</ref>

Requirement Analysis <ref>https://github.com/servo/servo/wiki/Storage-student-project</ref>

In order to introduce the support for session storage and local storage in the Servo Browser, we have to create the Storage structure and allow web pages to store data in the Servo memory space.

Below is a overview of the various steps identified as part of requirement analysis:

Storage Interface

  • We have to create the Storage interface and its stub implementation.
  • This interface is used by the web pages to communicate to the web storage.

WindowSessionStorage Interface

  • We have to create the WindowSessionStorage interface which will return a Storage instance.
  • A web page will use this interface to access its session storage.

WebStorageTask

  • We have to create a Storage Task which will be used to store all the web storage data.
  • This is a separate thread which starts when browser starts.
  • The class implementing the Storage interface uses it to store and retrieve the actual data.

Communication Channel

  • It provides the means to communicate to the separate thread 'WebStorageTask'.
  • We need to define a message-passing interface for reading and writing stored data for a particular browser tab and use it in the implementation of Storage interface to communicate to WebStorageTask.

Notification Event

  • We need to notify the respective browser tab when the value of a stored data is changed so that other browser objects which may be using this data can take appropriate action.

Web Storage Tests

  • We need to pass as many tests as possible.
  • These tests are part of the web storage specification. Any browser implementing the web storage interface must pass as many tests as possible out of these.

WindowLocalStorage Interface

  • We need to implement the WindowLocalStorage interface which behaves slightly different from the WindowSessionStorage interface.
  • This will provide the interface to access browser's local storage.


Implementation

The implementation of the project was divided into the following milestones :

  • Create and stub the WindowSessionStorage WebIDL interface defined in the spec, making it return a Storage instance : Once the Storage interface was created, we had to implement the interface to actually define the functions which were a part of the interface. Here we extended the Storage interface to specialize it as Session Storage interface namely WindowSessionStorage. The methods in this interface were then further implemented in Storage.rs which was made to return a Storage instance to the web page or application requiring the support of sessionstorage.
  • Create a storage task (similar to the resource task) which will contain all stored data : The actual data is stored in a background task known as Storage Task, A task in rust terms is nothing but a thread which can run in the background keep polling until it is required, it does so by looping over a channel until a request comes its way. The Storage task contains a HashMap of TreeMap. The Hashmap is used to store the storage data for all the sites. Its keys represent the origin of the request (determined from the URL it is coming from). There is an entry in the HashMap for each different origin. The respective value represents the storage data for the site. This site specific data is stored as a TreeMap which maintains the <key , value> pair in a ordered fashion. Thus the storage task contains the actual data structure which holds all the values and the Storage.rs acts as a mediator between the object and the data stored in the task.
  • Define a message-passing interface for reading and writing stored data for a particular origin: The Storage object requires a medium to delegate the functions to storage task where the actual implementation takes place. This is done using Channels. There are 2 major channels. First one is the one which the storage task creates and keeps on listening for any the request. The other is when the storage object wants to get some data from the task. The Storage object creates a temporary channel on which it listens for any reply by the Storage task. This is how the message-passing interface has been implemented in the given milestone.
  • Store a channel to the storage task in the Page structure that sends messages from the previous interface, and make use of it in the implementation of Storage: The storage object requires to know the channel on which the task is looping in order to send it requests for get, set or other functions. This is done by storing the channel that the storage task creates in the Page Structure which acts as a common object between these 2. Hence, by passing the created channel to the page structure it can now be accessed and utilized by the Storage object in order to delegate the methods onto the storage task and communicate.

Architecture <ref>https://github.com/servo/servo/wiki/Design</ref>

Architecture Explained

  • Each box represents a Rust task.
  • Blue boxes represent the primary tasks in the browser pipeline.
  • Gray boxes represent tasks auxiliary to the browser pipeline.
  • White boxes represent worker tasks. Each such box represents several tasks, the precise number of which will vary with the workload.
  • Dashed lines indicate supervisor relationships.
  • Solid lines indicate communication channels.

Component Design

There will be a Storage Task which will be responsible to hold all the data that the web page requests to save. This happens via Channels in Rust, which implements a Sender Receiver protocol. The task is runnning in the background and waits to receive the data sent from the web page.

Task <ref>http://doc.rust-lang.org/guide-tasks.html</ref>

Rust provides safe concurrent abstractions through a number of core library primitives. This guide will describe the concurrency model in Rust, how it relates to the Rust type system, and introduce the fundamental library abstractions for constructing concurrent programs.

Tasks provide failure isolation and recovery. When a fatal error occurs in Rust code as a result of an explicit call to panic!(), an assertion failure, or another invalid operation, the runtime system destroys the entire task. Unlike in languages such as Java and C++, there is no way to catch an exception. Instead, tasks may monitor each other to see if they panic.

Tasks use Rust's type system to provide strong memory safety guarantees. In particular, the type system guarantees that tasks cannot induce a data race from shared mutable state.

// Generate some state locally
let child_task_number = generate_task_number();

spawn(proc() {
    // Capture it in the remote task
    println!("I am child number {}", child_task_number);
});

Channel <ref>http://doc.rust-lang.org/guide-tasks.html</ref>

Now that we have spawned a new task, it would be nice if we could communicate with it. For this, we use channels. A channel is simply a pair of endpoints: one for sending messages and another for receiving messages.

The simplest way to create a channel is to use the channel function to create a (Sender, Receiver) pair. In Rust parlance, a sender is a sending endpoint of a channel, and a receiver is the receiving endpoint.

let (tx, rx): (Sender<int>, Receiver<int>) = channel();

spawn(proc() {
    let result = some_expensive_computation();
    tx.send(result);
});

some_other_expensive_computation();
let result = rx.recv();

Data Design

Data Description

The following data structure has been used

StorageTask | HashMap<String, TreeMap<DomString,DomString>>

Design Pattern

We have used the "Delegation Pattern" in our project. The Storage interface is used by web applications to access the web storage provided by the browser. However, the actual data is stored somewhere else(Servo Memory Space). So, it makes sense to create another class which should maintain the actual stored data. The Storage class can then delegate the task of storing/retrieving data to this class. We have created a class "StorageTask" for this purpose.

Also we are using an "Observer Pattern" where the Storage task runs in the background and observes the commands issued using a channel. It keeps on listening to changes on a port and as soon as it receives a message i.e. sees a call towards it, it performs the required function.

UML Diagrams

Flow Chart

1. First, we need to build rust and servo.
2. Generate the corresponding WebIDL bindings - Storage.webidl
3. Define Storage.rs which has the actual code for creating the storage object.
4. Call the receiver via a channel- this is actually used for creating an instance for each unique URL.
5. Build the servo again.

Use Case Diagram

1. Here the user can open multiple domains( multiple URL's).
2. Thereby the user will be creating multiple storage instances.
3. An user can traverse deep into the website but the storage instance is same for that URL.
4. The user can reopen the domain for a later period.

Proposed Test Cases

Some of the test cases which will be used to validate our changes are as follows:

  • Allow a web page to clear its session storage i.e. storage.clear() function should work
  • Allow a web page to store an item in its session storage i.e. test storage.setitem(key,value)
  • Allow a web page to retrieve stored items from its session storage i.e. test storage.getitem(key)
  • Do not allow a web page to retrieve stored items from the session storage of a web page in another domain i.e. try to access elements by forging url
  • Check the number of items stored in session storage i.e storage.count()
  • On removing an item from storage, it should be inaccessible i.e check if storage.remove(key) is functional
  • Should return null as value for a key not present in the session storage i.e. test storage.getitem(key) for non-existent key
  • Should give an error on exceeding the space limit of session storage i.e check for available memory on each command

The complete list of test cases can be found here.

Further Readings

Learning Rust by Examples: http://rustbyexample.com/
Javascript as Servo's Garbage Collector: http://blog.mozilla.org/research/2014/08/26/javascript-servos-only-garbage-collector/

References

<references/>