處理 Stack Overflow

直接看程式碼比較快：

#define _XOPEN_SOURCE 600

#include <stdio.h>
#include <stdlib.h>
#include <setjmp.h>
#include <signal.h>

sigjmp_buf stack_overflow_guard;

char alter_stack[4096];

void sigsegv_handler(int sig) {
  if (sig == SIGSEGV) {
    /* Jump to catch block */
    siglongjmp(stack_overflow_guard, sig);
  }
}

void install_sigsegv_handler() {
  /* Prepare alternating stack */
  stack_t stk;

  stk.ss_sp = alter_stack;
  stk.ss_size = sizeof(alter_stack);
  stk.ss_flags = 0;

  if (sigaltstack(&stk, NULL) == -1) {
    fprintf(stderr, "ERROR: Unable to setup alternative stack.\n");
    exit(EXIT_FAILURE);
  }

  /* Register SIGSEGV handler */
  struct sigaction act;

  act.sa_handler = &sigsegv_handler;
  sigfillset(&act.sa_mask);
  act.sa_flags |= SA_ONSTACK;

  if (sigaction(SIGSEGV, &act, NULL) == -1) {
    fprintf(stderr, "ERROR: Unable to instal signal handler.\n");
    exit(EXIT_FAILURE);
  }
}

int trigger_stack_overflow(int a, int b, int c, int d, int e) {
  return trigger_stack_overflow(a + 1, b + 1, c + 1, d + 1, e + 1) *
         trigger_stack_overflow(a - 1, b - 1, c - 1, d - 1, e - 1);
}

int main() {
  install_sigsegv_handler();

  if (sigsetjmp(stack_overflow_guard, 0) == 0) {
    printf("normal path, got: %d\n",
           trigger_stack_overflow(0, 0, 0, 0, 0));
  } else {
    printf("stack overflow\n");
  }

  return EXIT_SUCCESS;
}

LaTeX 與 Beamer

最近因為一些需要，必需使用 LaTeX 製作投影片，所以研究了一下 Beamer 的使用方法。其實寫起來並不困難，和一般的 LaTeX article 差不多。Beamer 的 document structure 如下：

\documentclass{beamer}
\usetheme{Singapore} %% 這一個是佈景主題 (選用)
\begin{document}

\title{Title}
\author{Author Name}
\institute{Institute}

\frame{\titlepage} %% 顯示標題頁面

%% ... 其他內容 ...

\end{document}

接下來和 article 一樣，可以分為 section 與 subsection，而每一個 section 和 subsection 可以由若干個 frame 組成。

\section{Section 1}
%% 如果你有需要，可以在這裡加上 \subsection{Subsection 1.1} 
\begin{frame}
  \frametitle{Frame 1.1}
  \begin{itemize}
    \item{Item 1}
    \item{Item 2}
  \end{itemize}
\end{frame}

我們可以看到每個 frame 都會有一個 frametitle，也就是每一頁上方的標題。而下面就是該頁的內容。如果你要條列出各個要點，可以使用 itemize。

最後如果你需要顯示大綱，可以在 titlepage 下面加上：

\section*{Outlines}
\begin{frame}
  \frametitle{Outlines}
  \tableofcontents
\end{frame}

不過因為要建立 tableofcontents 所以要執行 pdflatex 編譯你的投影片二次。這樣你就可以得到一個精美的投影片了。你可以在這裡下載到範例投影片與原始檔。

用 OpenMP 實作平行化的 Quicksort

OpenMP 和 Pthread 不同，我們沒有辦法很精確地控制有多少的 Thread 正在執行。所以如果要實作 Quicksort，我們不能直接使用 Recursion。相反地，我們必須引入 Threading Pool 的概念，讓各個 Thread 主動去某個工作清單拿工作。概念程式碼如下：

void quicksort_impl(sort_value_t array[],
                    stack_t *s,
                    size_t *busy_threads) {
  int idle = 1;

  size_t begin = 0;
  size_t end = 0;

  /* We should loop forever until everyone is idle */
  while (1) {
    while (idle) {
      /* This thread is idling.
         Try to get a new task from the stack. */

#pragma omp critical
      if (!stack_empty(s)) {
        /* Get the pending sort range, start work now! */
        sort_range_t *range = stack_top(s);
        begin = range->begin;
        end = range->end;
        stack_pop(s);

        ++*busy_threads;
        idle = 0;
      }

      /* If everyone finished his work, then leave now ... */
      if (*busy_threads == 0) {
        return;
      }
    }

    size_t size = end - begin;

    if (size <= 50) {
      sort_value_t *seg = array + begin;

      /* Use backward insertion sort when the sort range is small */
      size_t i, j;
      for (i = 1; i < size; ++i) {
        sort_value_t cur = seg[i];
        /* Move the number backward if they are greater than cur */
        for (j = i; j > 0 && seg[j - 1] > cur; --j) {
          seg[j] = seg[j - 1];
        }
        seg[j] = cur;
      }

      /* Mark begin as end so that we can acquire next sort range */
      begin = end;

#pragma omp critical
      --*busy_threads;

      idle = 1;

      /* Finished our range continue to acquire next range */
      continue;
    }


    /* Partition our range */
    sort_value_t *seg = array + begin;

    size_t pivot_index = rand() % size;
    SWAP(seg[0], seg[pivot_index]);
    sort_value_t pivot = seg[0];

    size_t left = 1;
    size_t right = size - 1;

    while (left < right) {
      while (seg[left] <= pivot && left < right) { left++; }
      while (seg[right] >= pivot && left < right) { right--; }
      SWAP(seg[left], seg[right]);
    }

    if (seg[left] > pivot) {
      left--;
    }
    SWAP(seg[0], seg[left]);

    /* Push left subrange to stack */
#pragma omp critical
    {
      sort_range_t range;
      range.begin = begin;
      range.end = begin + left;
      stack_push(s, &range);
    }

    /* Continue to sort right subrange */
    begin += left + 1;
  }
}

void quicksort(sort_value_t array[], size_t size) {
  size_t busy_threads = 0;
  stack_t *s = stack_new();
  sort_range_t all = { 0 , size };
  stack_push(s, &all);

  /* Run quicksort_impl in parallel */
#pragma omp parallel
  quicksort_impl(array, s, &busy_threads);

  stack_delete(s);
}