Mer: Comparison with desktop distributions

Comes from a presentation of mer community.

Is Mer just yet another linux distribution? Many people would disagree since we break quite a lot of things (Maemo GTK is a big one!), and I'll tell you some of the ways we differ.

Like Maemo we focus on power saving, some things that make sense on desktop/laptop distributions simply doesn't make sense on mobile devices that's supposed to last on the same charge several days being always­connected.

A tablet still comes with limited storage space, so there might be a need to shrink packages or dependancies (why do we need a weather library for NetworkManager?); but not hard as on an embedded system; there's miles difference between 256m flash and 64mb flash.

Yes, you can't run Crysis on a tablet, it has CPU, memory and bandwidth constraints and apps should be suited towards that. But, what it can do is to be more powerful because of the environment and services surrounding it.

Simple component system for embedded system

1. Objective

• Separate interface and implementation
  • User depends on only interface not implementation, the implementation can evolve without breaking user.
  • User can use several implementation of one interface simultaneously.
• Modular
  • Component is a special module, more modular.
  • Manage the dependency relationship of software modules.
• Testable
  • The component is the test unit.
• Position transparent (single-thread/multi-thread transparent)
  • local/remote, same thread/different thread transparent

2. Interface

• Describe in IDL formally: language neutral
• Binary standard: vtable
• Implementation in C: function pointer structure

  typedef struct
  {
      void (*dvFooInit)(dvFooIntf intf);
      void (*dvFooDestroy)(dvFooIntf intf,
          FOO_DESCRIPTION sFooDesc);
      void (*dvFooBarEnable)(dvFooIntf intf, BOOL bEnable);
      ...
  } dvFooOps;
  
  typedef struct
  {
      dvFooOps *ops;
  } dvFoo;
  
  typedef dvFoo *dvFooIntf;

• Implementation in C++: class with only pure virtual method

  class dvFoo
  {
  public:
      virtual void dvFooInit(void) = 0;
      virtual int32 dvFooDesctroy(FOO_DESCRIPTION desc) = 0;
      virtual void dvFooBarEnable(BOOL bEnable) = 0;
      ...
  };
  
  typedef dvFoo *dvFooIntf;
  

• A tool can be developed to generate C++ and C implementation of interface from IDL automatically.
  

3. Component (object)

• Properties:
  • Software module that implement one or several interfaces. The interfaces is the API of component and should be stable.
  • The source code, document, configuration information, test code of component is organized in individual folder.
  • Every component has its own version number and can evolve individually.
  • Can be selected and configured via a configuration tool.
• Implementation
  • Implementation in C: fill function pointer structure

    dvFooOps opsfoo = {
        dvLisaFooInit,
        dvLisaFooDesctory,
        dvLisaFooBarEnable,
        ...
    };
    
    typedef struct
    {
        dvFooOps *ops;
        /* data members for Lisa */
    } dvLisaFoo;
    
    dvLisaFoo foo = {
        &opsfoo,
        /* data members for Lisa */
    };

    For driver implementation, instance number can be used as the data member.
  • Implementation in C++: inherit implemented interfaces

    class dvLisaFoo : public dvFoo
    {
        /* data members for Lisa */
    public:
        void dvFooInit(void);
        int32 dvFooDestroy(FOO_DESCRIPTION desc);
        void dvFooBarEnable(BOOL bEnable);
        ...
    };

    For driver implementation, instance number can be used as the data member.

4. Usage

After getting the pointer to the interface of the component, user of component can use the component via direct function call without need to know the implementation of component. (C user can use C++ implementation).

#define dvFooInit(intf) (intf)->ops->dvFooInit((intf))
#define dvFooDestroy(intf, sFooDesc) 
    (intf)->ops->dvFooDesctroy((intf), (sFooDesc))

dvFooIntf intf;
/* Get interface */
dvFooInit(intf);
dvFooDestroy(intf, sFooDesc);

5. Inter-thread (inter-process) component

If the the user and implementer of component is resided in different thread (or process), it is not sufficient to use direct function call simply. To use component across thread (process), the following mechanism is provided.

• A proxy is provided in user thread (process), which is the representative of the component which implemented in different thread (process). The user can use the proxy in same way of component in single thread environment. The proxy implement the interface with inter-thread (inter-process) communication (such as message sending and receiving).
• A stub is provided in implementation thread (process), which is the representative of the user which is in different thread (process). The stub use the component in the same way of user in single thread environment. The stub simulate the user with inter-thread (inter-process) communication (such as message receiving and sending).
• A simple implementation of inter-thread inter-process provides a simple mutual exclusion resolution like crude force serialization between all functions of one component.
• In implementation, the implementing thread id can be used in proxy as the data member.
• A tool can be developed to generate proxy and stub implementation of interface from IDL automatically.

6. Component manager (component directory/component factory)

In order to get the interface of component, a component manager should be provided. The simplest component manager is as follow:

• Create all components before using components. Such as, all device driver components are created using the source code generated by configuration tool. All middleware components are created using the source code generated by configuration tool too.
• Component managers have lists of all components of system. Such as the device driver manager has the list of all device driver components.
• Component manager provide a interface to get the interfaces of components. Such as all the interfaces of device driver components can be gotten from device driver manager.
• For inter-thread (inter-process) components, the proxy and stub is created before using as that of the component. The proxy instead of component itself is in the list of components in component manager. The user of component will get the proxy, it is desirable.

GTK+ Map Viewer

Recently, I developed a simple map viewer for my Zaurus with GTK+.

Because most map image file is very big, from several MB to tens MB, it is very inconvenient to view map with ordinary image viewer, especially for embedded system like PDA and mobile phone.

This program is developed to facilitate map viewing, the basic idea behind it is:

1. The big map image file is splitted into many small image files, loaded on demand to reduce memory requirement.
2. The big map image file is pre-scaled too, because scaling a big image file is also a memory/CPU hungry task.
   

Some other useful feature for a map viewer is also provided. For example, personal marks can be added to a map. A map making tools is also provided to facilitate splitting and scaling the big map image file.

The source code of the program can be download from:
http://linux-mcr700.sourceforge.net/gviewmap-0.1.tar.gz

Stack-less multi-task system (2) -- implementation

The basic idea behind implementation:

1. Replace implicit C stack with explict link stack.
2. Use label to record PC.
3. Store task state in heap instead of stack.
4. Only functions will sleep directly or indirectly need to deal with stack explictly, other functions aren't affected.
   

Performance comparison:

1. Task stack space is saved, only one stack is needed.
2. Task switching time may be a little longer because of task swithing executing path will go through all functions invoked before sleep. But, if the task is small enough and function invoking depth is short, the task switching time will be affordable.
   

Sample Code:

#include <stdlib.h>
#include <assert.h>
#include <string.h>

struct stack
{
 short   stk_label;
 void    *stk_data;
 struct stack *stk_prev;
 struct stack *stk_next;
};

#define TASK_STATE_RUN         0
#define TASK_STATE_SLEEP       1

struct task
{
 short    tsk_state;
 void     (*tsk_entry)(void);
 struct stack tsk_stk;
 struct stack *tsk_stk_curr;
};

extern struct task tasks[];
struct task *task_curr;

void sleep(void)
{
 task_curr->tsk_state = TASK_STATE_SLEEP;
}

void wakeup(int task_id)
{
 tasks[task_id].tsk_state = TASK_STATE_RUN;
}

/* return code */
#define RC_SUCCESS    0
#define RC_FAILED     1
#define RC_PENDING    2

void push_stack()
{
 if (!task_curr->tsk_stk_curr->stk_next) {
  struct stack *stk;

  stk = malloc(sizeof(struct stack));
  assert(stk);
  memset(stk, 0, sizeof(*stk));
  stk->stk_prev = task_curr->tsk_stk_curr;
  task_curr->tsk_stk_curr->stk_next = stk;
 }
 task_curr->tsk_stk_curr = task_curr->tsk_stk_curr->stk_next;
}

void pop_stack()
{
 struct stack *stk;

 stk = task_curr->tsk_stk_curr->stk_prev;
 assert(stk->stk_next->stk_next == NULL);
 free(stk->stk_next);
 stk->stk_next = NULL;
 task_curr->tsk_stk_curr = stk;
}

#define TEST_TASK_LABEL1    0
#define TEST_TASK_LABEL2    1
#define TEST_TASK_LABEL3    2

#define TEST_TASK_SUB_LABEL1   0
#define TEST_TASK_SUB_LABEL2   1

void test_task_label1(void)
{
 /* everything as normal, without sleep */
}

int test_task_label2(void)
{
 int rc = RC_SUCCESS;

 push_stack();

 switch (task_curr->tsk_stk_curr->stk_label) {
 case TEST_TASK_SUB_LABEL1:
  task_curr->tsk_stk_curr->stk_label = TEST_TASK_SUB_LABEL2;
  rc = RC_PENDING;
  sleep();
  break;
 case TEST_TASK_SUB_LABEL2:
  break;
 }
 if (rc != RC_PENDING)
  pop_stack();
 return rc;
}

void test_task(void)
{
 switch (task_curr->tsk_stk.stk_label) {
 case TEST_TASK_LABEL1:
  test_task_label1();
  task_curr->tsk_stk.stk_label = TEST_TASK_LABEL2;
  task_curr->tsk_stk.stk_data = malloc(10);
  sleep();
  break;
 case TEST_TASK_LABEL2:
  if (test_task_label2() == RC_PENDING) {
   break;
  }
  task_curr->tsk_stk.stk_label = TEST_TASK_LABEL3;
 case TEST_TASK_LABEL3:
  break;
 default:
  assert(0);
  break;
 }
}

void test_task2(void)
{
 wakeup(0);
}

struct task tasks[2] =
{
 {
  TASK_STATE_RUN,
  test_task,
  { 0, NULL, NULL, NULL },
  NULL,
 },
 {
  TASK_STATE_RUN,
  test_task2,
  { 0, NULL, NULL, NULL},
  NULL,
 },
};

void schedule(void)
{
 int i;

 for (i = 0; i < 2; i++) {
  if (tasks[i].tsk_state == TASK_STATE_RUN) {
   task_curr = &tasks[i];
   task_curr->tsk_stk_curr = &task_curr->tsk_stk;
   tasks[i].tsk_entry();
  }
 }
}

int main(int argc, char *argv[])
{
 for (;;)
  schedule();
 return 0;
}

Stack-less multi-task system

In traditional multi-task operating system, there is one stack for one task. The stack is mainly used for storing call chain, function parameters and local variables, that is, the context of the task. When task is switched, the stack of task is switched too.

The problem of stack based multi-task system is the size of stack should be the maximum possible size that the stack maybe grow to. In Linux system, the size of kernel task stack is 4kB or 8kB. But, in 99% condition, only small part of whole stack is used. The efficiency of stack memory usage is low.

Another solution is that all tasks share the same stack. When task is executed, the stack is used for storing call chain, function parameters and local variables as that of task based multi-task. When task is about to be switched out of CPU, it saves all state (context) needed to continue the work elsewhere (such as global variable, malloced memory) and hands the stack to the task to be switched into CPU. The new task will ruin all the contents in the stack and use it exclusively until the next switching.

The problem of stack-less multi-task system is that when switching point is deeply nested, it is hard to storing all state needed in a modular way. For example, when a "page fault" occurs in a memory mapped page, the handler will go through memory subsystem and file system and maybe be switched out of CPU for waiting for disk reading. How can the task save the state of memory subsystem and file system in a modular way? So, the stack-less multi-task system is used mainly in the kernel of micro-kernel operating system, because there are only few simple subsystems, the state saving can be done in a modular or manageable way.

A resolution is adaptive stack scheme. If task is working for a system call that have very small stack usage (such as the wait in POSIX), all the state needed is stored elsewhere and the stack is freed, otherwise the stack is preserved. But this resolution is not very effective if most system calls use more stack.

I think another possible resolution is split task into more small tasks. Because every task is so small, its state can be stored without refer to other subsystem, that is in a modular way. And because the overhead of task is much less than before, the total overhead is not too much. Perhaps one small task corresponds one subsystem in traditional system. For example, the memory system, file system can be tasks too. In this system, create a process turns to create several tasks.