Google's Summer of Code: Part III

FreeBSD/nsswitch and Caching

Nsswitch is an extremely useful subsystem that exists on UNIX platforms such as Linux, Solaris, and FreeBSD. It provides a flexible and convenient way to configure how name-service lookups are done. Nsswitch operates with two basic concepts—database and source. When users query the particular database (password, group, hosts, and so on) for information, nsswitch decides which source (files, NIS, LDAP) this information should be taken from. The basic idea of nsswitch is that hard-coded name-service lookup functions (getpw**, getgr**, gethost**, getaddrinfo, and the like) are never called directly. The function:

 nsdispatch(void *retval, 
  const ns_dtab dtab[], 
  const char *database, 
  const char *method_name, 
  const ns_src defaults[], …) 

is called instead. In turn, it dispatches the call to the appropriate sources.

FreeBSD nsswitch implementation supports various possible databases: password, groups, hosts, netgroups, and shells. In this project, we extended this list by adding services, rpc, protocols, OpenSSH, and Globus Grid Toolkit 4 databases. To add the support for the particular database, we had to implement several nsswitch sources for it, and then replace all hard-coded function calls with the nsdispatch calls.

To add the support for services, rpc, and protocols, we also had to change the interface of the corresponding internal reentrant libc functions to improve the compatibility with Linux/Solaris nsswitch implementations. We’ve changed the interfaces from the HP-UX style:

 int getservbyname_r(const char *name, 
  const char *proto, 
  struct servent *serv, struct

to Linux/Solaris style:

  int getservbyname_r(const char *name, 
  const char *proto, 
  struct servent *serv, char *buffer, 
  size_t bufsize, struct servent **result);

Because all nsswitch requests are passed through nsdispatch, it’s a great place to organize caching in a general way. Caching can significantly improve system performance. It’s useful for the services database, for example, because the /etc/services file becomes bigger and bigger, and getserv** functions become slower and slower.

We had to modify the nsdispatch code, so that it could process the “cache” source. Besides, marshaling and unmarshaling routines had been implemented for every nsswitch database type.

To make the cache, nsdispatch interacts with the caching daemon, which is built on top of the caching library (they were both developed during the “Summer of Code”). The caching library provides a simple interface for cache organization. It uses hash tables to store data and supports different policies, which are applied when cache size is exceeded. The caching daemon uses UNIX socket to communicate with libc to perform read/write operations.

The interesting feature of the caching daemon (and the caching library) is the multipart caching and the concept of sessions. This approach is very useful for getXXXent() functions. When the first call to getXXXent() is made, the write session is opened. If the setXXXent() or endXXXent() is called, the session is abandoned and all its data are freed. If the getXXXent() function indicates the successful end of a sequence, the session is gracefully closed and all session data are placed in the cache.

Userspace Filesystems Framework for NetBSD

Name: Antti Kantee
Contact: [email protected]
School: Helsinki University of Technology, Finland
Major: Graduate student, Computer Science
Project: Userspace Filesystems Framework for NetBSD
Project Page: http://netbsd-soc.sourceforge.net/projects/userfs/
Mentor: William Studenmund
Mentoring Organization: NetBSD Project (http://www.netbsd.org/)

A long time ago, the two competing paradigms for designing an operating system were the monolithic and microkernel approaches. While the performance benefits of monolithic kernels with direct access to memory are undeniable, microkernels have more beauty and theoretical appeal. Since these days everybody is using excessive hardware performance as an excuse to add bloat; it is only fair to use it to add something useful.

Implementing a filesystem in userspace is beneficial for several reasons:

• Development can take advantage of a faster bugfix-compile-restart cycle. Also, debugging is easier because it is possible to run the filesystem under a normal userspace symbolic debugger.
• The filesystem can access information that traditionally has been difficult to access from inside the kernel. A simple example could be a web site accessed over HTTP using a readily available HTTP library.
• The actual implementation does not necessarily have to be written in C. Of course, having a userspace API for C is only half the battle (but it’s the larger half).
• Leveraging existing application code written against the well-known libc filesystem API is made possible.

Producing a framework involved attaching a new filesystem to the kernel frameworks, creating a communication pipe to the userspace and a serialized representation of filesystem operations, and creating an API to which userspace implementations could attach.

Adding a new filesystem to the kernel side was mostly a question of leg work. However, one problem was having to think somewhat differently from the typical case: Usually, filesystems are implemented with a clear idea of the semantic effects of each vnode operation. But in this case, a “generic implementation” had to be devised.

Communication to the userspace was implemented as a device node, some ioctls, and argument structures. This is an area for future work that may possibly produce a framework for generic kernel upcalls.

The userspace API is dictated by the need to have an implementation backing each vfs and vnode operation. Also, the API aims to lift the burden of communication subroutines common to all filesystem implementations without restricting the potential for, say, an asynchronous implementation.

Currently, the framework is still very much in the infant prototyping stage. After the system is stress tested, hardened, and perfected, it would be interesting to investigate providing similar frameworks in NetBSD for other subsystems, such as networking stacks and device drivers.

gloox: A High-Level Jabber/XMPP Library for C++

Name: Jakob Schröter
Contact: [email protected]
School: University of Applied Sciences, Bremen, Germany
Major: Computer Science
Project: gloox
Project Page: http://camaya.net/gloox
Mentors: Peter Saint-Andre
Mentoring Organization: Jabber Software Foundation (http://www.jabber.org/)

gloox was born as part of a university project (XMPPGrid: A Grid Framework) that used Jabber/XMPP as a transport protocol. Because, at that time, there were no C++ XMPP libraries available that suited my needs, I decided to roll my own.

gloox (http://camaya.net/gloox) heavily uses the Observer Pattern. There are listeners ("handlers" in gloox-speak) for almost every imaginable event that can occur, from connection establishment to error conditions. After a connection has been established, everything is event driven, and simple applications, such as bots, can easily do without a mainloop or threads. On the other hand, gloox exposes the necessary interface to manually initiate fetching of data from the socket.

Right after the XML parser receives a complete stanza, it is parsed into a Stanza object that offers a convenient interface to take apart such an XML element. The respective handlers are then called based on the stanza's type.

The library offers classes to create regular clients as well as components. These only offer basic functionality, but can be extended with several included implementations of so-called Jabber Enhancement Proposals (JEPs) to create a full-featured client/component.

In general, using the library is as simple as:

• Creating a new Client or Component object.
• Creating and registering the desired handlers.
• Calling connect().

Most protocol enhancements follow a similar approach: They simply register as handlers for one of the Stanza types. For example, the Info/Query (IQ) mechanism of the XMPP spec is an important tool to control various aspects of a session. The basic syntax of IQ packets is always the same and different protocols are distinguished based on the payload of an IQ packet: The child element and its namespace. gloox offers a handler for these namespaces, which makes it extremely easy to implement every IQ-based protocol.

Additionally, handlers for the remaining XMPP packet types (called "stanzas" in XMPP) are included, along with a generic tag handler for protocols not using these defined stanza types.

While using these interfaces, the higher level layers offer handlers themselves, with data types tailored to their needs. This minimizes the need to know the XMPP protocol by heart if the included classes are used.

Even though it is defined in the XMPP IM spec, Roster Management is an example for such a higher level protocol. The RosterManager registers itself as a handler for IQ stanzas carrying "query" elements qualified by the jabber:iq:roster namespace. It can then add or remove items from a user's contact list, and react to incoming so-called roster pushes, an updated contact list item sent by the server.

The RosterManager offers clients a rich interface to be notified about any changes happening to the contact list. Events exist for adding and removing contacts, as well as for changes in subscription states.

The decision of using/activating one (or more) of the protocol enhancements is with the user of the library. The modular structure allows addition and removal of those enhancements at runtime. More JEPs can easily be implemented, usually by creating handlers for the respective XML namespaces a JEP uses. gloox is licensed under the GPL and commercial licenses are available.

Back to Top

SPARQL for Sesame

Name: Ryan Levering
Contact: [email protected]
School: Binghamton University
Major: Ph.D. candidate, Computer Science
Project: SPARQL for Sesame
Project Page: http://sparql.sourceforge.net/
Mentors: Giovanni Tummarello and Jeen Broekstra
Mentoring Organization: Semedia Semantic Web and Multimedia Group (http://semedia.deit.univpm.it/)

The initial goal of my project was to write a Java interpreter of the SPARQL query language for use in Sesame, an RDF data server. SPARQL, the first W3C standardized query language for the RDF data format, is a step toward standardization of the Semantic Web vision of W3C.

The language is reminiscent of SQL—users specify a series of set and value constraints on the data in the server:

SELECT ?title
WHERE { _:book :title ?title .
FILTER (?title != "Old Title") }

The server then returns data values that fit those constraints. However, RDF data is not relational and is usually visualized as a graph of data relationships. Therefore, queries are more akin to graph pattern matching, with variables being bound to certain matched parts of the graph.

The first design was a library of classes that processed the query from within the object structure created by parsing the query into an abstract syntax tree. This design, however, suffered from one of the common problems in OO programming—a dependence on inheritance for extension. To customize the interpreter for other servers, one had to subclass certain query objects and rebuild the library.

The final design uses a combination of design patterns to overcome this dependence. The main principle of the design is the separation of interpretation logic and query data, via prolific use of the Strategy pattern. Because abstract syntax trees lend themselves ideally to the Visitor pattern, a visitor is used at interpretation time to walk the AST query structure and bind logic to each part of the query, using an Abstract Factory to create the logic objects. Developers wishing to implement a customized query interpreter can shortcut the default logic using their own factory implementation to rewrite any part of the logic, without ever needing to recompile the main library. The primary efficiency penalty of the design is found in the data interface between the library and the server. Because most servers use a slightly different data object representation, every data value that is used by the interpreter has to be passed through its own adapter, which either passes on method calls or creates a new interpreter-compatible data value. For greater speed, the most computationally intensive set logic in the interpreter can be overridden to let servers do their own native data manipulation. Hopefully, the benefits of using a standardized specification library will allow server developers to focus more on the front-end server interfaces and underlying persistent storage and less on the particular quirks of this new query language.

TSC-I2: A Lightweight Implementation for Precision-Augmented Timekeeping

Name: Xun Luo
Contact: [email protected]
School: University of Illinois at Chicago
Major: Ph.D. candidate, Computer Science
Project: Timekeeping Using TSC Register
Project Page: http://tsc-xluo.sourceforge.net/
Mentors: Jeff Boote
Mentoring Organization: Internet2 (http://www.internet2.edu/)

The quality of timekeeping is critical for many network protocols and measurement tools. TSC-I2 (TSC-Internet2) ensures accuracy and precision by making TSC rate calibration a continuous process, thus the accuracy of interpolation parameters could be ensured, which in turn results in satisfying clock precision. TSC-I2 maintains a soft clock of its own, periodically comparing this clock to the system clock. During each comparison, it synchronizes itself with the system clock, and adjusts the interpolation rate based on the offset and rate errors regarding to system clock. Whenever the accuracy of the soft clock is ensured, TSC-I2 uses this clock to report time to the library user; otherwise, the system clock value is reported. The advantage of this design is that system clock is enhanced rather than substituted.

The clock discipline algorithm is enlightened by NTP. A state-machine-controlled PLL (Phase Lock Loop) traps the rate-induced phase difference between TSC clock and system clock. Rate wander is captured within one loop delay, and corrected in three to four following loops. To avoid incorrect recognition of noise as a rate-induced error, two filters—a popcorn filter and a spike detector—are used. There are two usage modes: DAEMON and CLIENT. In DAEMON mode, a standalone daemon takes charge of timekeeping, serving one or more clients. In CLIENT mode, the library creates a thread running within the hosting process. Thus, it minimizes the application's external dependency. There are also clear distinctions between TSC-I2 algorithms and its NTP counterparts, mainly due to the different natures of referencing sources. Readers interested in TSC-I2 internals can visit the project web site, where more details are illustrated.

TSC-I2, which is fully implemented in around 2000 lines of C, is fairly lightweight. It has been published under the Open Source License at http://tsc-xluo.sourceforge.net/. TSC-I2 currently supports IA32, AMD64, and Power PC architectures, as well as Linux, FreeBSD, Mac OS X, and Microsoft Windows.

DDJ