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.