-
Notifications
You must be signed in to change notification settings - Fork 321
Click Under the Hood
The following page explains how Click actually works under the hood. The explanation is initially based on single-threaded, user-level click; we discuss multi-threaded and kernel mode Click in later sections of this document. Also note that line numbers might differ slightly depending on which source version you have.
This document assumes you have read the Click SOSP paper or the Click thesis. Three dots in code excerpts ("...") denote that irrelevant lines of code have been omitted. Numbers beginning with a plus ("+") sign denote line numbers.
This section gives a brief introduction to the internals of Click that is necessary in order to understand the sections that follow it.
A Click router (where a router could be a firewall, NAT, or any other packet processing unit) contains a class called Master (lib/master.cc and include/click/master.hh. This master contains, among other things, two other classes. The first of these is Router (lib/router.cc and include/click/router.hh) which holds information about the actual configuration once it has been parsed from the .click file. The second is a set of RouterThread instances (lib/routerthread.cc and include/click/routerthread.hh. As their name suggests, these constitute the running threads of a Click router (in the case of single-threaded Click only a single thread exists).
Click schedules the router’s CPU with a task queue (depending on the values of some #DEFINEs the queue of tasks may be implemented as a heap or a linked list). Each router thread runs a loop that processes the task queue one element at a time. The task queue is scheduled with the flexible and lightweight stride scheduling algorithm. Tasks are simply elements that would like special access to CPU time. Thus, elements are Click’s unit of CPU scheduling as well as its unit of packet processing. An element should be on the task queue if it frequently initiates push or pull requests without receiving a corresponding request. For example, an element that polls a device driver should be placed on the task queue; when run, it would remove packets from the driver and push them into the configuration. However, most elements are never placed on the task queue. They are implicitly scheduled when their push or pull methods are called. Once an element is scheduled, either explicitly or implicitly, it can initiate an arbitrary sequence of push and pull requests, thus implicitly scheduling other elements.
Finally, it is worth pointing out that the basic unit of communication between elements is the Packet, defined in include/click/packet.hh. This is the object that most element execution methods expect to receive and/or output.
In this section we give a more detailed introduction to how elements are scheduled to run in Click. As mentioned, Click uses tasks (essentially elements) as its basic unit of scheduling; tasks are defined in include/click/task.hh. Not all elements need to be scheduled: many of them will be implicitly scheduled when a scheduled element calls them. Exactly which elements are scheduled and which are implicitly called depends on the elements themselves. To make the discussion more concrete, imagine the following simple Click configuration file:
FromDevice("eth0")
-> Strip(14)
-> CheckIPHeader(BADSRC 18.26.4.255 2.255.255.255 1.255.255.255)
-> Queue
-> ToDevice("eth0");
In this case, FromDevice's initialize method uses the ScheduleInfo class to periodically schedule itself. Strip, CheckIPHeader and Queue do not do so, as they are all implicitly called when FromDevice executes. In greater detail, when FromDevice is scheduled to run, its selected method is called which in turn makes a call to output(0).push(p). Since in our case this element is connected to Strip, this call essentially causes the simple_action callback of Strip to run. This method's returning of a Packet object triggers execution of the callback of the next element down the line in the configuration, in this case CheckIPHeader. This element's callback is also simple_action, which once again causes execution of Queue's callback method (enq) to run when it returns a packet.
At this point the execution chain finishes and control returns to the scheduler. At the other end of the configuration, ToDevice also schedules itself to run periodically. When its callback run_task runs, it pulls a packet from the queue, sends it out a physical interface and returns control back to the scheduler. Periodic scheduling is not the only way for elements to schedule themselves: InfiniteSource, for instance, schedules itself once during initialization, and re-schedules itself each time its callback is executed (up to the number of packets it's supposed to generate). As can be seen, different elements have different callbacks (although there's a limited number of them); we will explain how these get used later on in this document.
The listing below gives an overview of the Click source tree. Note that the listing is not complete, limiting itself to showing directories relevant to this document's discussion.
.
|-- conf // various Click configuration files
|-- drivers // drivers with Click extensions (for polling)
|-- elements // the actual Click elements
|-- etc // patch and other miscellaneous files
|-- include
| `-- click // base Click header files
|-- lib // base Click cpp files
|-- linuxmodule // Click linux kernel mode files
`-- userlevel // Click user level files
The process begins when the install binary is executed (click for user-level, click-install for the kernel-based version). The source for this is found in userlevel/click.cc, and the main is found in line 421; here's an excerpt:
static Router *router;
...
int
main(int argc, char **argv)
{
click_static_initialize();
...
router = parse_configuration(router_file, file_is_expr, false, errh);
...
router->master()->thread(0)->driver();
}In this abbreviated excerpt we can see that running a Click router consists of doing a bit of initialization, parsing the given router configuration, and running the router thread (the 0 in thread(0) is because we're running single-threaded Click; the multi-threaded version would look slightly different). We will now explain each of these stages in greater detail.
The click_static_initialize function, found in userlevel/click.cc +442 is simple:
...
cp_va_static_initialize();
...
Router::static_initialize();
...
click_export_elements();The first function initializes element parameter types and the second one router parameters. The third call warrants a closer look, as it takes care of populating a data structure with the names and other information about all available elements. The function is automatically defined during the build process in the file [userlevel/elements.cc][]:
#include <click/config.h>
#include <click/package.hh>
#include "../elements/standard/delayshaper.hh"
#include "../elements/threads/spinlockrelease.hh"
#include "../elements/test/listtest.hh"
... (many other elements) ...
beetlemonkey(uintptr_t heywood)
{
switch (heywood) {
case 0: return new AdjustTimestamp;
case 1: return new AggregateCounter;
case 2: return new AggregatePacketCounter;
... (many other elements) ...
case 259: return new ToRawSocket;
case 260: return new ToSocket;
case 261: return new UMLSwitch;
default: return 0;
}
}
void
click_export_elements()
{
(void) click_add_element_type_stable("AdjustTimestamp",beetlemonkey,0);
... (many other elements) ...
(void) click_add_element_type_stable("ToRawSocket", beetlemonkey, 259);
(void) click_add_element_type_stable("ToSocket", beetlemonkey, 260);
(void) click_add_element_type_stable("UMLSwitch", beetlemonkey, 261);
CLICK_DMALLOC_REG("nXXX");
}As shown, the file defines the elements that are available, includes their
header files and assigns numbers to each of the elements. In turn, the
function click_add_element_type_stable is called; this function is once again
defined in lib/driver.cc, +399:
extern "C" int
click_add_element_type_stable(const char *ename,
Element *(*func)(uintptr_t),
uintptr_t thunk)
{
assert(ename);
if (Lexer *l = click_lexer())
return l->add_element_type(String::make_stable(ename),
func,
thunk);
else
return -99;
}This function in turn adds the element to the lexer (used to parse Click configuration files) by calling add_element_type with the element's name, a pointer to its class, and the element code "type" (an integer). The function is itself defined in lib/lexer.cc +836:
int
Lexer::add_element_type(const String &name, ElementFactory factory, uintptr_t thunk,
bool scoped)
{
int tid = _element_types.size();
_element_types.push_back(ElementType());
_element_types[tid].factory = factory;
_element_types[tid].thunk = thunk;
_element_types[tid].name = name;
_element_types[tid].next = _last_element_type |
(scoped ? (int)ET_SCOPED : 0);
if (name)
_element_type_map.set(name, tid);
_last_element_type = tid;
return tid;
}where the relevant data structures are defined in [i]nclude/click/lexer.hh][], +153, as:
struct ElementType {
ElementFactory factory;
uintptr_t thunk;
String name;
int next;
};
HashTable<String, int> _element_type_map;
Vector<ElementType> _element_types;At the end of all of these calls the lexer has a data structure called
_element_types containing element names, (integer) types and factories. In
addition, the lexer also keeps a separate hash _element_type_map mapping
element names to their integer types.
The process begins once again in the main of userlevel/click.cc (+588) with a
call to parse_configuration (+303):
static Router *
parse_configuration(const String &text, bool text_is_expr, bool hotswap,
ErrorHandler *errh)
{
Master *master = (router ? router->master() : new Master(nthreads));
Router *r = click_read_router(text, text_is_expr, errh, false, master);
if (!r)
return 0;
...
return r;The function is straightforward, receiving a Click configuration in the form
of a string and delegating most of the work to click_read_router, defined in
lib/driver.cc +481:
Router *
click_read_router(String filename,
bool is_expr,
ErrorHandler *errh,
bool initialize,
Master *master)
{
...
// read file
String config_str;
if (is_expr) {
config_str = filename;
filename = "config";
} else {
config_str = file_string(filename, errh);
if (!filename || filename == "-")
filename = "<stdin>";
}
...
RequireLexerExtra lextra(&archive);
int cookie = l->begin_parse(config_str, filename, &lextra, errh);
while (l->ystatement())
/* do nothing */;
Router *router = l->create_router(master ? master : new Master(1));
l->end_parse(cookie);
...
if (initialize)
if (errh->nerrors() > before || router->initialize(errh) < 0) {
delete router;
return 0;
}
return router;The function calls begin_parse on the lexer to initialize some basic
variables and then calls ystatement (defined in lib/lexer.cc +1798),
which calls yconnection (lib/lexer.cc +1435) and which, in turn,
subsequently calls yelement (lib/lexer.cc +1163) on each of the elements:
bool
Lexer::yelement(Vector<int> &result, bool in_allowed)
{
...
*resp = get_element(e->name,
e->type >= 0 ? e->type : e->decl_type,
e->configuration,
e->filename,
e->lineno);
...We omit almost all of this function's implementation since its details are
largely unimportant for our purposes, What is important is the call to
get_element, whose implementation is in lib/lexer.cc +993:
int
Lexer::get_element(String name, int etype, const String &conf,
const String &filename, unsigned lineno)
{
...
_c->_element_names.push_back(name);
_c->_element_configurations.push_back(conf);
if (!filename && !lineno) {
_c->_element_filenames.push_back(_file._filename);
_c->_element_linenos.push_back(_file._lineno);
} else {
_c->_element_filenames.push_back(filename);
_c->_element_linenos.push_back(lineno);
}
_c->_elements.push_back(etype);
_c->_element_nports[0].push_back(0);
_c->_element_nports[1].push_back(0);
return eid;
}The related data structures are defined in [include/click/lexer.hh][], +170:
Compound *_c;
with Compound being defined in lib/lexer.cc +117:
class Lexer::Compound : public Element { public:
...
private:
HashTable<String, int> _element_map;
Vector<int> _elements;
Vector<String> _element_names;
Vector<String> _element_configurations;
Vector<String> _element_filenames;
Vector<unsigned> _element_linenos;
Vector<int> _element_nports[2];
int _anonymous_offset;
Vector<Router::Connection> _conn;
friend class Lexer;
}As shown, get_element populates _c with information about the actual
elements in the configuration file. Finally, recall from the listing of
click_read_router the call to create_router, defined in lib/lexer.cc +1933:
Router *
Lexer::create_router(Master *master)
{
Router *router = new Router(_file._big_string, master);
if (!router)
return 0;
...
// add elements to router
Vector<int> router_id;
for (int i = 0; i < _c->_elements.size(); i++) {
int etype = _c->_elements[i];
if (etype == TUNNEL_TYPE)
router_id.push_back(-1);
else if (Element *e = (*_element_types[etype].factory)
(_element_types[etype].thunk)) {
int ei = router->add_element(e,
_c->_element_names[i],
_c->_element_configurations[i],
_c->_element_filenames[i],
_c->_element_linenos[i]);
router_id.push_back(ei);
} else {
_errh->lerror(_c->element_landmark(i),
"failed to create element %<%s%>",
_c->_element_names[i].c_str());
router_id.push_back(-1);
}
}
...
// expand connections to router
int pre_expanded_nc = _c->_conn.size();
for (int i = 0; i < pre_expanded_nc; i++) {
int fromi = router_id[ _c->_conn[i][1].idx ];
int toi = router_id[ _c->_conn[i][0].idx ];
if (fromi < 0 || toi < 0)
add_router_connections(i, router_id);
}
// use router element numbers
for (Connection *cp = _c->_conn.begin(); cp != _c->_conn.end(); ++cp) {
(*cp)[0].idx = router_id[(*cp)[0].idx];
(*cp)[1].idx = router_id[(*cp)[1].idx];
}
// sort and add connections to router
click_qsort(_c->_conn.begin(), _c->_conn.size());
for (Connection *cp = _c->_conn.begin(); cp != _c->_conn.end(); ++cp)
if ((*cp)[0].idx >= 0 && (*cp)[1].idx >= 0)
router->add_connection((*cp)[1].idx,
(*cp)[1].port,
(*cp)[0].idx,
(*cp)[0].port);
// add requirements to router
for (int i = 0; i < _requirements.size(); i += 2)
router->add_requirement(_requirements[i], _requirements[i+1]);
return router;
}The main thing to take away from this listing is that a new Router variable is instantiated and initialized with the string of the configuration file and the Master instance given to the function (recall that Master contains a Router instance and potentially several RouterThread instances). Another equally important point is that it is here that elements are actually instantiated, specifically in the call:
Element *e = (*_element_types[etype].factory)(_element_types[etype].thunk)
The first part of the call, (*_element_types[etype].factory), resolves to
the function beetlemonkey (recall listing for userlevel/elements.cc), to which
we essentially pass as a parameter an integer representing the element type
(this corresponds to _element_types[etype].thunk). The function beetlemonkey
then returns a new element depending on the type given as a parameter. Going
back to create_router, the function also places calls to add_element and
add_connection, which populate private data member variables of Router
regarding the router's configuration (the following listing is from
include/click/router.hh, +227):
Vector<Element*> _elements;
Vector<String> _element_names;
Vector<String> _element_configurations;
Vector<String> _element_landmarks;
Vector<Connection> _conn;
Vector<String> _requirements;The last step before actually running the router is to initialize the elements
themselves. To do so, recall the bottom of the listing click_read_router:
one of the last lines makes a call to router->initialize, defined in
lib/router.cc +1043:
int
Router::initialize(ErrorHandler *errh)
{
...
for (int ord = 0; ord < _elements.size(); ord++) {
if ((r = _elements[i]->configure(conf, &cerrh)) < 0) {
element_stage[i] = Element::CLEANUP_CONFIGURE_FAILED;
all_ok = false;
if (cerrh.nerrors() == before) {
if (r == -ENOMEM)
cerrh.error("out of memory");
else
cerrh.error("unspecified error");
}
}
else
element_stage[i] = Element::CLEANUP_CONFIGURED;
}
...
if (all_ok) {
_state = ROUTER_PREINITIALIZE;
initialize_handlers(true, true);
for (int ord = 0; all_ok && ord < _elements.size(); ord++) {
...
if (_elements[i]->initialize(&cerrh) >= 0)
element_stage[i] = Element::CLEANUP_INITIALIZED;
else {
if (cerrh.nerrors() == before && !_elements[i]->cast("Error"))
cerrh.error("unspecified error");
element_stage[i] = Element::CLEANUP_INITIALIZE_FAILED;
all_ok = false;
}
}
}The reason this code fragment is important is because it takes care of calling each element's configure and initialize methods, in that order. Elements use the first method to receive configuration information (i.e., the parameters given to an element in a Click configuration file). The second is used to initialize the element, including whether it should schedule itself to run or not (recall the section on scheduling at the beginning of this document). With all of this in place, the Master object, and the Router object it contains, have all the information needed to start running the router.
The process begins in userlevel/click.cc’s main with a call to
router->master()->thread(0)->driver() (in the case of single-threaded
Click), which is implemented in lib/routerthread.cc +513:
void
RouterThread::driver()
{
const volatile int * const stopper = _master->stopper_ptr();
int iter = 0;
...
driver_loop:
if (*stopper == 0) {
// run occasional tasks: timers, select, etc.
iter++;
_master->run_signals(this);
if ((iter % _iters_per_os) == 0)
run_os();
bool run_timers = (iter % _master->timer_stride()) == 0;
if (run_timers) {
_master->run_timers(this);
}
}
// run task requests (1)
if (_pending_head) // uintptr_t, from include/master.hh +103
process_pending();
run_tasks(_tasks_per_iter); // _tasks_per_item set to 128 on linux
// check to see if driver is stopped
if (*stopper > 0) {
driver_unlock_tasks();
bool b = _master->check_driver();
driver_lock_tasks();
if (!b)
goto finish_driver;
}
goto driver_loop;
finish_driver:
driver_unlock_tasks();
}The basic idea of this function is simple enough: infinitely stay in the
driver_loop until the function _master->check_driver(), which returns
whether there are any routers running in the master, returns false. Ignoring
calls to yield execution to the OS (run_os) or running timers
(_master->run_timers(this)), most of the work is carried out by the
run_tasks call, defined in lib/routerthread.cc +342:
inline void
RouterThread::run_tasks(int ntasks)
{
...
Task *t;
for (; ntasks >= 0; --ntasks) {
t = task_begin();
if (t == this)
break;
t->fast_remove_from_scheduled_list();
...
// 21.May.2007: Always set the current thread's pass to the current
// task's pass, to avoid problems when fast_reschedule() interacts
// with fast_schedule() (passes got out of sync).
_pass = t->_pass;
t->_status.is_scheduled = false;
t->fire();
...
}
}
This function runs a set number of tasks (set to 128 on linux). In each
iteration, it removes the first task from the list, and sets (in
fast_remove_from_scheduled_list) the next task as the current task to run.It
then calls the task's fire method, defined in include/click/task.hh +554:
inline void
Task::fire()
{
...
if (!_hook)
(void) ((Element*)_thunk)->run_task(this);
else
(void) _hook(this, _thunk);
...
}with the various variables shown having the following definitions in include/click/task.hh:
// defines TaskCallback as a pointer to a function returning bool
// and taking Task *, void * as parameters
typedef bool (*TaskCallback)(Task *, void *);
TaskCallback _hook;
void *_thunk;In short, if an element's callback is run_task, fire directly calls that
method, passing the element (the task) as a parameter. If, on the other hand,
the element uses a different callback, the function pointer _thunk,
representing the callback, is called with the task and the _thunk pointer as
parameters.
How are these callbacks initialized? This depends on the element in question, but just to give an example consider InfiniteSource, whose definition can be found in elements/standard/infinitesource.cc. Its constructor (+30) is defined as follows:
InfiniteSource::InfiniteSource()
: _packet(0), _task(this)
{
}The line _task(this) causes a call to one of the Task constructors found in
include/click/task.hh +289:
inline
Task::Task(Element* e)
: _prev(0), _next(0),
_should_be_scheduled(false), _should_be_strong_unscheduled(false),
_pass(0), _stride(0), _tickets(-1),
_hook(0), _thunk(e),
_thread(0), _home_thread_id(-1),
_owner(0), _pending_nextptr(0)
{
}The important part here is _thunk(e): this void * pointer gets set equal to
the element, and it's precisely this pointer which will be used to run the
element's run_task callback when this task/element is scheduled (recall the
listing of the fire method above).
So far we have explained how schedulable elements schedule themselves and how their callbacks are called. We have yet to describe how implicitly-scheduled elements (those than run when scheduled elements call them) are actually executed. The details can vary depending on the Click configuration in use and the elements in it, but the basic concepts should be the same irrespectively. Given this, it helps to use a sample Click configuration to drive the rest of the explanation (this listing comes from conf/test.click):
InfiniteSource(DATA \<00 00 c0 ae 67 ef 00 00 00 00 00 00 08 00
45 00 00 28 00 00 00 00 40 11 77 c3 01 00 00 01
02 00 00 02 13 69 13 69 00 14 d6 41 55 44 50 20
70 61 63 6b 65 74 21 0a>, LIMIT 5, STOP true)
-> Strip(14)
-> Align(4, 0) // in case we're not on x86
-> CheckIPHeader(BADSRC 18.26.4.255 2.255.255.255 1.255.255.255)
-> Print(ok)
-> Discard;
The actual parameters passed to the various elements are irrelevant for our purposes; this configuration simply generates 5 packets, prints their contents and discards them. Note that for the explanation below all listings for a particular element refer to the .cc file found under the elements directory and its sub-directories.
Before we begin, it is worth pointing out that by and large Click uses three callbacks for implicitly-scheduled elements, including default implementations; these are defined in lib/element.cc:
void
Element::push(int port, Packet *p)
{
p = simple_action(p);
if (p)
output(port).push(p);
}
Packet *
Element::pull(int port)
{
Packet *p = input(port).pull();
if (p)
p = simple_action(p);
return p;
}
Packet *
Element::simple_action(Packet *p)
{
return p;
}The process begins as explained before, with InfiniteSource using
ScheduleInfo to periodically schedule itself. When it is scheduled, its
run_task method runs (+109):
bool
InfiniteSource::run_task(Task *)
{
if (!_active || !_nonfull_signal)
return false;
int n = _burstsize;
if (_limit >= 0 && _count + n >= (ucounter_t) _limit)
n = (_count > (ucounter_t) _limit ? 0 : _limit - _count);
for (int i = 0; i < n; i++) {
Packet *p = _packet->clone();
if (_timestamp)
p->timestamp_anno().assign_now();
output(0).push(p);
}
_count += n;
if (n > 0)
_task.fast_reschedule();
else if (_stop && _limit >= 0 && _count >= (ucounter_t) _limit)
router()->please_stop_driver();
return n > 0;
}As can be seen, this method calls output(0).push(p). In this case, the next
element down the line is Strip. Since its class doesn't have a push method
implemented, the default method in the Element superclass is called instead,
which in turns calls Strip::simple_action and output(port).push(p).
The next element is Align. This time, Align does implement a push method, so it is called:
void
Align::push(int, Packet *p)
{
output(0).push(smaction(p));
}Ignoring the details of smaction, this element then calls CheckIPHeader's
push method. Since it doesn't define one, once again the default provided by
Element is used. The next element is Print, which once again relies on the
default push method. Finally, the Discard element provides its own push
method:
void
Discard::push(int, Packet *p)
{
_count++;
p->kill();
}This method simply kills the packet and releases any memory allocated to it.
At this point the execution chain started by InfiniteSource's
output(0).push(p) is finished, and the process will repeat 4 more times
corresponding to the remaining packets to generate (see for loop in the
listing of the element's run_task method).
Once the remaining packets are generated and processed, run_task returns
control to the scheduler. In most configurations the scheduler would then
schedule the next task. In this particular one, no more tasks are left to run,
so the router process finishes and quits.
In this section we describe how Click works when run in kernel mode. The process begins with a different executable called click-install. This command can take a number of arguments, but in the simplest case takes the name of a file containing a Click configuration, as in the user-level case. The command is defined in tools/click-install/click-install.cc, and its main looks as follows (+301):
int
main(int argc, char **argv)
{
click_static_initialize();
...
RouterT *r = read_router(router_file, file_is_expr, nop_errh);
...
// install Click module if required
if (access(clickfs_packages.c_str(), F_OK) < 0) {
// find and install proclikefs.o
StringMap modules(-1);
if (read_active_modules(modules, errh) && modules["proclikefs"] < 0) {
String proclikefs_o =
clickpath_find_file("proclikefs.ko", "lib", CLICK_LIBDIR, errh);
install_module(proclikefs_o, String(), errh);
}
String click_o =
clickpath_find_file("click.ko", "lib", CLICK_LIBDIR, errh);
// install it in the kernel
String options;
if (threads > 1)
options += "threads=" + String(threads);
if (greedy)
options += " greedy=1";
if (!accessible)
options += " accessible=0";
if (uid != 0)
options += " uid=" + String(uid);
if (gid != 0)
options += " gid=" + String(gid);
if (cpu != -1)
options += " cpu=" + String(cpu);
install_module(click_o, options, errh);
// make clickfs_prefix directory if required
if (access(clickfs_dir.c_str(), F_OK) < 0 && errno == ENOENT) {
if (mkdir(clickfs_dir.c_str(), 0777) < 0)
errh->fatal("cannot make directory %s: %s",
clickfs_dir.c_str(),
strerror(errno));
}
// mount Click file system
int mount_retval = mount("none", clickfs_dir.c_str(), "click", 0, 0);
...
String clickfs_config = clickfs_prefix + String("/config");
// write flattened configuration to CLICKFS/config
int exit_status = 0;
{
String config_place = (hotswap ? clickfs_hotconfig : clickfs_config);
int fd = open(config_place.c_str(), O_WRONLY | O_TRUNC);
String config = r->configuration_string();
int pos = 0;
while (pos < config.length()) {
ssize_t written = write(fd,
config.data() + pos,
config.length() - pos);
if (written >= 0)
pos += written;
else if (errno != EAGAIN && errno != EINTR)
errh->fatal("%s: %s", config_place.c_str(), strerror(errno));
}
int retval = close(fd);
}
}As with userlevel Click, this function begins by calling the
click_static_initialize method that initializes some basic variables such as
parameter types, and a list of which elements are available. Also like in
user-level Click, the function then parses the router configuration. Here's
where things start to differ. In order to run in kernel mode, Click needs to
be loaded as a kernel module. In addition, Click in kernel mode uses entries
in the Linux /proc filesystem in order to, among others, implement the
elements' read and write handlers. This system is implemented as another
kernel module called proclikefs. Starting a router in kernel mode consists,
then, of inserting the proclikefs kernel module (via the install_module
method), mounting that filesystem (see call to mount above) and inserting the
actual Click kernel module (again, via the install_module method). The
install_module method is found at +196:
static void
install_module(const String &filename, const String &options,
ErrorHandler *errh)
{
String cmdline = "/sbin/insmod ";
if (output_map)
cmdline += "-m ";
cmdline += filename;
if (options)
cmdline += " " + options;
int retval = system(cmdline.c_str());
if (retval != 0)
errh->fatal("'%s' failed", cmdline.c_str());
}Calling this method on our setup results in the system calls /sbin/insmod /usr/local/lib/proclikefs.ko and /sbin/insmod /usr/local/lib/click.ko. The
proclikefs.ko module is defined in linuxmodule/proclikefs.c, and the actual
Click filesystem in linuxmodule/clickfs.cc, though we will skip any detailed
explanation of how it works. The Linux kernel module main program is defined
in linuxmodule/module.cc, with execution beginning, as with all Linux kernel
modules, with the init_module function (+279):
extern "C" int
init_module()
{
// C++ static initializers
NameInfo::static_initialize();
cp_va_static_initialize();
// default provisions
Router::static_initialize();
NotifierSignal::static_initialize();
// thread manager, sk_buff manager, config manager
click_init_sched(ErrorHandler::default_handler());
skbmgr_init();
click_init_config();
// global handlers
Router::add_read_handler(0,
"packages",
read_global,
(void *) (intptr_t) h_packages);
Router::add_read_handler(0,
"meminfo",
read_global,
(void *) (intptr_t) h_meminfo);
Router::add_read_handler(0,
"cycles",
read_global,
(void *) (intptr_t) h_cycles);
Router::add_read_handler(0,
"errors",
read_errors,
0,
HANDLER_DIRECT);
Router::add_read_handler(0,
"messages",
read_messages,
0,
HANDLER_DIRECT);
...
init_clickfs();
return 0;
}Here once again the process starts with cp_va_static_initialize. Note that
this call had been done at the beginning of this section already. The
difference is that the first time it was done by the click-install tool, while
this time it is being run by the Click kernel module. The next line worth
pointing out is the call to click_init_sched, defined in linuxmodule/sched.cc
+340:
void
click_init_sched(ErrorHandler *errh)
{
...
click_master = new Master(1);
for (int i = 0; i < click_master->nthreads(); i++) {
RouterThread *thread = click_master->thread(i);
pid_t pid = kernel_thread
(click_sched, thread, CLONE_FS | CLONE_FILES | CLONE_SIGHAND);
...
}
...
}As shown, this function creates a new Master object and adds RouterThreads to
it (only one in our case, since we have single-threaded Click). For each of
the threads it creates a kernel thread by calling kernel_thread and setting
click_sched as its callback function; this function is defined in
linuxmodule/sched.cc +81:
static int
click_sched(void *thunk)
{
RouterThread *rt = (RouterThread *)thunk;
...
printk("<1>click: starting router thread pid %d (%p)\n",
current->pid,
rt);
// add pid to thread list
SOFT_SPIN_LOCK(&click_thread_lock);
if (click_thread_tasks)
click_thread_tasks->push_back(current);
SPIN_UNLOCK(&click_thread_lock);
// driver loop; does not return for a while
rt->driver();
// release master (preserved in click_init_sched)
click_master->unuse();
// remove pid from thread list
SOFT_SPIN_LOCK(&click_thread_lock);
if (click_thread_tasks)
for (int i = 0; i < click_thread_tasks->size(); i++) {
if ((*click_thread_tasks)[i] == current) {
(*click_thread_tasks)[i] = click_thread_tasks->back();
click_thread_tasks->pop_back();
break;
}
}
printk("<1>click: stopping router thread pid %d\n", current->pid);
SPIN_UNLOCK(&click_thread_lock);
return 0;
}This function essentially invokes the thread's router and calls its driver function which actually runs the router (an explanation of the driver function appears in the user-level Click section above). When the router finishes, control returns and click_sched performs a bit of clean-up before returning.
So far we installed the click.ko and proclikefs modules, set up kernel
threads and set them running. However, we have not yet told the router to
actually install a particular Click configuration. For this we need to go back
to the listing of click-install's main method. After the modules are
inserted, the click-install tool takes care of writing the string
representing the Click configuration to /proc/click/config.
When the entry is written to, its read handler gets called. Where is this
handler set-up? The call to click_init_config in the listing of init_module
above starts off the process; click_init_config is defined in
linuxmodule/config.cc +171:
void
click_init_config()
{
lexer = new Lexer;
Router::add_read_handler(0, "classes", read_classes, 0);
Router::add_write_handler(0, "config", write_config, 0);
Router::add_write_handler(0, "hotconfig", write_config, (void *)1);
Router::set_handler_flags(0, "config",
HANDLER_WRITE_UNLIMITED |
Handler::RAW |
Handler::NONEXCLUSIVE);
Router::set_handler_flags(0, "hotconfig",
HANDLER_WRITE_UNLIMITED |
Handler::RAW |
Handler::NONEXCLUSIVE);
click_config_generation = 1;
current_config = new String;
click_export_elements();
}Of particular interest to this discussion is the line related to the "config"
entry, for which the function write_config is set as its handler. This
function is found in linuxmodule/config.cc +157:
static int
write_config(const String &s, Element *, void *thunk, ErrorHandler *)
{
click_clear_error_log();
int retval = (thunk ? hotswap_config(s) : swap_config(s));
return retval;
}As in this case thunk is 0 (see call to add_write_handler above),
swap_config is called (linuxmodule/config.cc +118):
static int
swap_config(const String &s)
{
kill_router();
if (Router *router = parse_router(s)) {
if (router->initialize(click_logged_errh) >= 0)
router->activate(click_logged_errh);
install_router(s, router);
return (router->initialized() ? 0 : -EINVAL);
} else {
install_router(s, 0);
return -EINVAL;
}
}Just as in the userlevel Click case, this function calls parse_router in order
to parse the router configuration and return a Router object. The function
then installs the router by calling install_router(s, router), found in
linuxmodule/config.cc +94:
static void
install_router(const String &config, Router *r)
{
click_config_generation++;
click_router = r;
if (click_router)
click_router->use();
*current_config = config;
}with click_router defined in linuxmodule/module.cc +37 as follows:
Router *click_router = 0;If all of these operations were successful, the click-install tool finishes and exits, leaving the kernel threads to run the actual Click router. The click-uninstall tool can then be used to remove these Click threads from the kernel.
Note that this section refers to kernel-mode multi-threaded Click, multi-threading in user level is currently marked as experimental.
To enable multi-threading, the first thing that's needed is to add an option to the configure script before building Click:
./configure --enable-multithread[=N]
When running Click configurations, an extra parameter needs to be given to the click-install tool:
click-install -t 8 test.click
where -t specifies the number of desired threads. The relevant bits in
tools/click-install/click-install.cc are shown below:
#define THREADS_OPT 309
static const Clp_Option options[] = {
#if FOR_LINUXMODULE
{ "threads", 't', THREADS_OPT, Clp_ValUnsigned, 0 },
#endif
};
int
main(int argc, char **argv)
{
int threads = 1;
while (1) {
int opt = Clp_Next(clp);
switch (opt) {
#if FOR_LINUXMODULE
case THREADS_OPT:
threads = clp->val.u;
if (threads < 1) {
errh->error("must have at least one thread");
goto bad_option;
}
break;
#endif
}
}
#if FOR_LINUXMODULE
String options;
if (threads > 1)
options += "threads=" + String(threads);
install_module(click_o, options, errh);
...
}The main function parses the "t" command-line parameter and adds it to a
string of options which is passed to the Click kernel module when it is
installed (essentially the install_module function generates a string
consisting of /sbin/insmod /usr/local/lib/click.ko threads=N). From the
discussion in the previous section we know that control will now pass to
linuxmodule/module.cc's init_module, which will in turn call
linuxmodule/sched.cc's click_init_sched, +340:
void
click_init_sched(ErrorHandler *errh)
{
#if HAVE_MULTITHREAD
click_master = new Master(click_parm(CLICKPARM_THREADS));
...
for (int i = 0; i < click_master->nthreads(); i++) {
click_master->use();
RouterThread *thread = click_master->thread(i);
thread->set_greedy(greedy);
pid_t pid = kernel_thread
(click_sched, thread, CLONE_FS | CLONE_FILES | CLONE_SIGHAND);
if (pid < 0) {
errh->error("cannot create kernel thread for Click thread %i!",
i);
click_master->unuse();
}
}
}Note that only the parts relevant to multi-threading are shown above. This
part is pretty simple, and limits itself to using the CLICKPARM_THREADS macro
(defined in linuxmodule/moduleparm.h) to retrieve the number of threads given
to the module as a parameter and using it as an argument to one of the Master
constructors (lib/master.cc +62):
Vector<RouterThread*> _threads; // <-- from include/click/master.hh
Master::Master(int nthreads)
: _routers(0)
{
for (int tid = -1; tid < nthreads; tid++)
_threads.push_back(new RouterThread(this, tid));
}The Master object now has ''N'' RouterThreads, each with its own thread id.
Going back to the listing of click_init_sched, the function now runs through
the threads in Master and launches a kernel thread for each of them, setting
click_sched as their callback function. This function is defined at +81 as:
static int
click_sched(void *thunk)
{
RouterThread *rt = (RouterThread *)thunk;
#ifdef CONFIG_SMP
int mycpu = click_parm(CLICKPARM_CPU);
if (mycpu >= 0) {
mycpu += rt->thread_id();
if (mycpu < num_possible_cpus() && cpu_online(mycpu))
set_cpus_allowed(current, cpumask_of_cpu(mycpu));
else
printk("<1>click: warning: cpu %d for thread %d offline\n",
mycpu,
rt->thread_id());
}
#endif
printk("<1>click: starting router thread pid %d (%p)\n",
current->pid,
rt);
// add pid to thread list
SOFT_SPIN_LOCK(&click_thread_lock);
if (click_thread_tasks)
click_thread_tasks->push_back(current);
SPIN_UNLOCK(&click_thread_lock);
// driver loop; does not return for a while
rt->driver();
// release master (preserved in click_init_sched)
click_master->unuse();
// remove pid from thread list
SOFT_SPIN_LOCK(&click_thread_lock);
if (click_thread_tasks)
for (int i = 0; i < click_thread_tasks->size(); i++) {
if ((*click_thread_tasks)[i] == current) {
(*click_thread_tasks)[i] = click_thread_tasks->back();
click_thread_tasks->pop_back();
break;
}
}
printk("<1>click: stopping router thread pid %d\n", current->pid);
SPIN_UNLOCK(&click_thread_lock);
return 0;
}The first lines of code are there to pin (i.e., assign) the thread to a CPU.
The CLICKPARM_CPU is a parameter that can be given to click-install to
specify which CPU a configuration should run on. The function calls
set_cpus_allowed to pin the current task to the mycpu cpu (we're omitting
a lot of details about these calls, including the variable current which is
a struct task_struct * of the current task, to improve readability). The
function then calls the thread's driver() function in order for the Click
configuration to run. After it finishes some clean-up is done and the router
thread finishes.
As described so far, when a thread runs it pulls a task (i.e., a schedulable Click element) and runs it; another thread pulls the next task and so forth. This means that we don't have much control over which threads run which parts of a Click configuration. This is especially important when we start making performance experiments and pinning particular threads to CPU cores. In fact, Click provides an element called StaticThreadSched that allows us to assign specific schedulable elements to specific threads. Here's how one instance of such an element might look like in a Click configuration file:
StaticThreadSched(fd0 0, td0 0,
fd1 1, td0 1,
fd2 2, td3 2,
fd3 3, td2 3);
This configuration has four network interfaces (split into fd=FromDevice?
and td=ToDevice? elements). A pair of FromDevice/ToDevice? is assigned to a
thread id (the second argument in each pair), for a total of four threads.
This allows us to later on, for instance, assign each of the four threads to
different CPU cores in order to improve performance.
How does this element actually do its work? To see this, it is worth having a look at its implementation in elements/threads/staticthreadsched.cc:
int
StaticThreadSched::configure(Vector<String> &conf, ErrorHandler *errh)
{
Element *e;
int preference;
for (int i = 0; i < conf.size(); i++) {
if (cp_va_space_kparse(conf[i], this, errh,
"ELEMENT", cpkP+cpkM, cpElement, &e,
"THREAD", cpkP+cpkM, cpInteger, &preference,
cpEnd) < 0)
return -1;
...
_thread_preferences[e->eindex()] = preference;
}
_next_thread_sched = router()->thread_sched();
router()->set_thread_sched(this);
return 0;
}
int
StaticThreadSched::initial_home_thread_id(Element *owner, Task *task,
bool scheduled)
{
int eidx = owner->eindex();
if (eidx >= 0 && eidx < _thread_preferences.size()
&& _thread_preferences[eidx] != THREAD_UNKNOWN)
return _thread_preferences[eidx];
if (_next_thread_sched)
return _next_thread_sched->initial_home_thread_id(owner,
task,
scheduled);
else
return THREAD_UNKNOWN;
}Before going further it is worth pointing out that StaticThreadSched
inherits not only from Element, but also from ThreadSched
(include/click/standard/threadsched.hh) which is essentially an empty
"interface" class mandating the implementation of the initial_home_thread_id
function above. As shown in the listing, configure reads each [ELEMENT
THREAD_ID] pair, populating the _thread_preferences data structure (of type
vector<int>). The eindex() function returns the element's index within its
router; this acts as an id. The configure function finishes by setting the
element's router's scheduler to this (this is possible because, as mentioned,
StaticThreadSched inherits from ThreadSched).
So far we've explained the configure function. In order to show how
initial_home_thread_id is used we need to start at a schedulable element, for
instance InfiniteSource, whose initialize method is as follows:
int
InfiniteSource::initialize(ErrorHandler *errh)
{
if (output_is_push(0)) {
ScheduleInfo::initialize_task(this, &_task, errh);
_nonfull_signal = Notifier::downstream_full_signal(this, 0, &_task);
}
return 0;
}This method calls ScheduleInfo's initialize_task, defined in
elements/standard/scheduleinfo.cc +117:
void
ScheduleInfo::initialize_task(Element *e, Task *task, bool schedule,
ErrorHandler *errh)
{
int tickets = query(e, errh);
if (tickets > 0) {
task->initialize(e, schedule);
task->set_tickets(tickets);
}
}This function calls Task's initialize method, defined in [lib/task.cc][] +191:
void
Task::initialize(Element *owner, bool schedule)
{
Router *router = owner->router();
int tid = router->initial_home_thread_id(owner, this, schedule);
_thread = router->master()->thread(tid);
_owner = owner;
...
_status.home_thread_id = _thread->thread_id();
_status.is_scheduled = schedule;
if (schedule)
add_pending();
}This is where the actual work is done. In particular, the function first
retrieves the schedulable element's router, calling initial_home_thread_id
on it. Since we had changed the router's scheduler to be the
StaticThreadSched element, this call will resolve to
StaticThreadSched::initial_home_thread_id, which will return the thread id
corresponding to the owner element (i.e., the assignment we had given as
parameter to the StaticThreadSched element in the Click configuration file).
The function then retrieves the thread corresponding to the thread id and sets
it as the running thread.
Lastly, we haven't talked about setting CPU affinities, i.e., how threads are assigned to CPU cores. Click largely leaves this up to the OS. Under Linux, users can install a Click configuration and then set affinities afterwards, either through command-line tools like taskset or by calling the sched_setaffinity and sched_getaffinity functions. If no affinities are set, the OS will decide the assignment. Another way would be to write a new Click element to configure this; no such element exists yet.
In order to run Click in polling mode, a modified network driver is needed, which generally limits things to an Intel card. Patched versions of the Intel drivers are provided within the Click source tree under the drivers sub-directory. The first thing to do is to insert the modified driver's kernel module. Once this is done, create a Click configuration that uses the element PollDevice instead of the usual FromDevice. That's it!
To do: perhaps a description of which modifications are needed for a driver to work with Click in polling mode, as well as a detailed description of the PollDevice element.
The Click functions and definitions related to memory allocation operations are found in include/click/glue.hh and lib/glue.cc. glue.hh defines the following:
# include <linux/malloc.h>
# include <linux/vmalloc.h>
# define CLICK_LALLOC(size) (click_lalloc((size)))
# define CLICK_LFREE(p, size) (click_lfree((p), (size)))
extern "C" {
void *click_lalloc(size_t size);
void click_lfree(volatile void *p, size_t size);
}This file includes the standard Linux headers for malloc and vmalloc and sets
up a couple of macro definitions: CLICK_LALLOC resolves to lib/glue.cc's
click_lalloc function and CLICK_LFREE to its click_lfree, both covered below.
Most of the interesting bits are in lib/glue.cc, which begins by defining some
variables and macros:
uint32_t click_dmalloc_where = 0x3F3F3F3F;
size_t click_dmalloc_curnew = 0;
size_t click_dmalloc_totalnew = 0;
size_t click_dmalloc_failnew = 0;
struct task_struct *clickfs_task;
# define CLICK_ALLOC(size) kmalloc((size), (current == clickfs_task ?
GFP_KERNEL : GFP_ATOMIC))
# define CLICK_FREE(ptr) kfree((ptr))This code sets up some simple variables to keep track of memory allocation and
potential leaks. For instance, click_dmalloc_curnew is used to report any
potential leaks when the Click Linux kernel module exits (linuxmodule/module.cc
+333):
extern "C" void
cleanup_module()
{
extern size_t click_dmalloc_curnew; /* glue.cc */
...
if (click_dmalloc_curnew) {
printk("<1>click error: %d outstanding news\n",
click_dmalloc_curnew);
click_dmalloc_cleanup();
}
}The macros shown simply replace calls to CLICK_ALLOC and CLICK_FREE with
calls to Linux's kmalloc and kfree, respectively. Further down the same file
we find definitions for the new and delete operators:
void *
operator new(size_t sz) throw ()
{
click_dmalloc_totalnew++;
if (void *v = CLICK_ALLOC(sz)) {
click_dmalloc_curnew++;
return v;
} else {
click_dmalloc_failnew++;
return 0;
}
}
void *
operator new[](size_t sz) throw ()
{
click_dmalloc_totalnew++;
if (void *v = CLICK_ALLOC(sz)) {
click_dmalloc_curnew++;
return v;
} else {
click_dmalloc_failnew++;
return 0;
}
}
void
operator delete(void *addr)
{
if (addr) {
click_dmalloc_curnew--;
CLICK_FREE(addr);
}
}
void
operator delete[](void *addr)
{
if (addr) {
click_dmalloc_curnew--;
CLICK_FREE(addr);
}
}Since kmalloc and its corresponding CLICK_ALLOC should only be used to
allocate relatively small amounts of memory, Click provides alternate
functions:
extern "C" {
# define CLICK_LALLOC_MAX_SMALL 131072
void *
click_lalloc(size_t size)
{
void *v;
click_dmalloc_totalnew++;
if (size > CLICK_LALLOC_MAX_SMALL)
v = vmalloc(size);
else
v = CLICK_ALLOC(size);
if (v) {
click_dmalloc_curnew++;
} else
click_dmalloc_failnew++;
return v;
}
void
click_lfree(volatile void *p, size_t size)
{
if (p) {
if (size > CLICK_LALLOC_MAX_SMALL)
vfree((void *) p);
else
kfree((void *) p);
click_dmalloc_curnew--;
}
}If the amount of memory requested is less than CLICK_LALLOC_MAX_SMALL,
CLICK_ALLOC and kfree are used as previously. If the amount is greater, on
the other hand, the functions make calls to vmalloc and the corresponding
vfree.
The creation of this document was partly funded by the EU FP7 CHANGE (257422) Project, http://www.change-project.eu/