2012/8

bash 网络接口

我很早以前就见过 /dev/tcp/<host>/<port> 这个接口,但一直以为是某个 BSD 内核实现了一个特殊的文件系统,因为 Linux 上面很明显没有 /dev/tcp 这个目录。直到今天我才发现,这个目录其实是 bash 自己实现的!!这么以来就可以不借助wget,nc 来实现网络连接了!设计这么一个接口是要逆天了嘛!

使用这个接口很简单,如下所示:

bash-4.2$ cat </dev/tcp/time.nist.gov/13

56188 12-09-18 15:34:26 50 0 0 733.5 UTC(NIST) *

bash-4.2$ exec 3<>/dev/tcp/www.w3.org/80
bash-4.2$ echo -e “GET / HTTP/1.0nn” >&3
bash-4.2$ cat <&3
HTTP/1.1 200 OK
Date: Tue, 18 Sep 2012 15:41:08 GMT
Server: Apache/2
Content-Location: Home.html
Vary: negotiate,accept
TCN: choice
Last-Modified: Tue, 18 Sep 2012 14:06:27 GMT
ETag: “8f75-4c9fa65657ec0;89-3f26bd17a2f00”
Accept-Ranges: bytes
Content-Length: 36725
Cache-Control: max-age=600
Expires: Tue, 18 Sep 2012 15:51:08 GMT
P3P: policyref=”http://www.w3.org/2001/05/P3P/p3p.xml
Connection: close
Content-Type: text/html; charset=utf-8

在 bash 的源代码树 redir.c 文件中,我们不难发现下面的代码:

[c]
/ A list of pattern/value pairs for filenames that the redirection
code handles specially.
/
static STRING_INT_ALIST _redir_special_filenames[] = {

if !defined (HAVE_DEV_FD)

{ “/dev/fd/[0-9]*”, RF_DEVFD },

endif

if !defined (HAVE_DEV_STDIN)

{ “/dev/stderr”, RF_DEVSTDERR },
{ “/dev/stdin”, RF_DEVSTDIN },
{ “/dev/stdout”, RF_DEVSTDOUT },

endif

if defined (NETWORK_REDIRECTIONS)

{ “/dev/tcp//“, RF_DEVTCP },
{ “/dev/udp//“, RF_DEVUDP },

endif

{ (char *)NULL, -1 }
};


static int
redir_open (filename, flags, mode, ri)
char *filename;
int flags, mode;
enum r_instruction ri;
{
int fd, r;

r = find_string_in_alist (filename, _redir_special_filenames, 1);
if (r >= 0)
return (redir_special_open (r, filename, flags, mode, ri));

/ If we are in noclobber mode, you are not allowed to overwrite
existing files. Check before opening.
/
if (noclobber && CLOBBERING_REDIRECT (ri))
{
fd = noclobber_open (filename, flags, mode, ri);
if (fd == NOCLOBBER_REDIRECT)
return (NOCLOBBER_REDIRECT);
}
else
{
fd = open (filename, flags, mode);

if defined (AFS)

  if ((fd &lt; 0) &amp;&amp; (errno == EACCES))
    {
      fd = open (filename, flags &amp; ~O_CREAT, mode);
      errno = EACCES;       /* restore errno */
    }

endif / AFS /

}

return fd;
}

[/c]

可见,当 bash 发现重定向时它会先查看重定向的文件是不是特殊文件,如果是截获它,自行解释之,否则就打开这个文件。当然了,真正解释 /dev/tcp/HOST/PORT 的代码是在 lib/sh/netopen.c 中。

bash 的手册中也提到了这些特殊接口:

/dev/fd/fd
If fd is a valid integer, file descriptor fd is duplicated.
/dev/stdin
File descriptor 0 is duplicated.
/dev/stdout
File descriptor 1 is duplicated.
/dev/stderr
File descriptor 2 is duplicated.
/dev/tcp/host/port
If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts
to open a TCP connection to the corresponding socket.
/dev/udp/host/port
If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts
to open a UDP connection to the corresponding socket.

Linux 内核中的 KMP 实现

Linux 内核中使用到了字符串搜索,所以它也有 KMP 算法的实现,代码在 lib/ts_kmp.c 中。

Linux 内核中用到 KMP 算法的地方有三处:iptables string match 模块、iptables conntrack amanda 模块(不知道这个是用来干什么的)、以及 ematch qdisc。iptables string match 是通过字符串搜索来匹配一个包,然后进行相应的处理,比如用下面的命令可以阻止对domain.com服务器的HTTP请求:

iptables -I INPUT 1 -p tcp —dport 80 -m string —string “domain.com” —algo kmp -j DROP

至于 ematch qdisc,和它类似,可以通过字符串匹配到对应的包进行 QoS,比如这个例子

tc filter add dev eth0 parent 10:12 prio 10 protocol ip basic match ‘text(kmp foobar from 0 to 200)’ flowid 10:1

总之,在内核中实现 KMP 算法是有必要的。下面来看具体实现。

我们知道,KMP 算法中最核心的地方就是 prefix 的计算,也称为 next 数组,它用来表示当字符 pattern[i] 匹配失败后应该从 pattern[next[i]] 字符继续进行匹配,而不总是从头开始,因此它的时间复杂度是O(n)。如果你对 KMP 不熟悉的话,网上有很多介绍,我觉得这篇文章还算不错,在继续看下面的代码之前可以读一下它。

内核中实现比网上的很多代码都更容易理解,因为在匹配开始之前,它就先把 prefix 计算好了。计算 prefix 的函数是:

[c]
static inline void compute_prefix_tbl(const u8 pattern, unsigned int len,
unsigned int
prefix_tbl, int flags)
{
unsigned int k, q;
const u8 icase = flags & TS_IGNORECASE;

    for (k = 0, q = 1; q  0 &amp;&amp; (icase ? toupper(pattern[k]) : pattern[k])
                != (icase ? toupper(pattern[q]) : pattern[q]))
                    k = prefix_tbl[k-1];
            if ((icase ? toupper(pattern[k]) : pattern[k])
                == (icase ? toupper(pattern[q]) : pattern[q]))
                    k++;
            prefix_tbl[q] = k;
    }

}
[/c]

结合 KMP 实现的主函数来理解更一目了然:

[c]
static unsigned int kmp_find(struct ts_config conf, struct ts_state state)
{
struct ts_kmp kmp = ts_config_priv(conf);
unsigned int i, q = 0, text_len, consumed = state->offset;
const u8
text;
const int icase = conf->flags & TS_IGNORECASE;

    for (;;) {
            text_len = conf-&gt;get_next_block(consumed, &amp;text, conf, state);

            if (unlikely(text_len == 0))
                    break;

            for (i = 0; i  0 &amp;&amp; kmp-&gt;pattern[q]
                        != (icase ? toupper(text[i]) : text[i]))
                            q = kmp-&gt;prefix_tbl[q - 1];
                    if (kmp-&gt;pattern[q]
                        == (icase ? toupper(text[i]) : text[i]))
                            q++;
                    if (unlikely(q == kmp-&gt;pattern_len)) {
                            state-&gt;offset = consumed + i + 1;
                            return state-&gt;offset - kmp-&gt;pattern_len;
                    }
            }

            consumed += text_len;
    }

    return UINT_MAX;

}
[/c]

内核中的 KMP 函数接口是封装过的,你不能直接调用它。如果你的内核模块中要使用它,可以参考 lib/textsearch.c 中给的例子:

[c]
int pos;
struct ts_config conf;
struct ts_state state;
const char
pattern = “chicken”;
const char *example = “We dance the funky chicken”;

conf = textsearch_prepare(“kmp”, pattern, strlen(pattern),
GFP_KERNEL, TS_AUTOLOAD);
if (IS_ERR(conf)) {
err = PTR_ERR(conf);
goto errout;
}

pos = textsearch_find_continuous(conf, &state, example, strlen(example));
if (pos != UINT_MAX)
panic(“Oh my god, dancing chickens at %dn”, pos);

textsearch_destroy(conf);
[/c]

撤销 git 操作

今天脑抽了一下,在做 git rebase -i 的时候无意识地把某一个 commit 给合并到前一个 commit 里去了,结果是该 commit 丢失,而且前一个 commit 也搞砸了。怎么能撤销这个操作呢?

Google 搜索了一下,发现了还有 git reflog 这个命令,可以查看 git 命令的历史记录,比如我刚才的操作:

324c85e HEAD@{0}: rebase -i (finish): returning to refs/heads/ipv6
324c85e HEAD@{1}: checkout: moving from ipv6 to 324c85e
324c85e HEAD@{2}: rebase -i (finish): returning to refs/heads/ipv6
324c85e HEAD@{3}: rebase -i (pick): ipv6: use xxxx
9fc8e64 HEAD@{4}: rebase -i (fixup): ipv6: unify xxxx
2ea2149 HEAD@{5}: rebase -i (fixup): updating HEAD
8d1f07b HEAD@{6}: checkout: moving from ipv6 to 8d1f07b
0e118d2 HEAD@{7}: commit: ipv6: separate xxxx

可以看出 HEAD@{7} 这个点就是我应该重置回去的,然后执行 git reset HEAD@{7} 就行了!

通过 git reflog 也可以撤销 git reset 的操作,非常实用。

另外,我很惊讶似乎还有不少人不知道 git rebase -i 这个命令。这个命令真的十分强大,我几乎天天都在用,它既可以用来合并补丁,也可以用来切割补丁,还能修改 commit 的记录(具体可自行参考 git-rebase 的手册),可以说是 git 命令中的一把瑞士军刀啊!不过如果你的 git tree 是 public 的,最好不用或者少用 git rebase,我用 git rebase 大多都是在自己的非 public 的树上。

关于 schedule() 函数

今天在 LKML 上看到一个补丁:http://permalink.gmane.org/gmane.linux.kernel/1337629,它对 schedule() 函数做了很好的注释,分享一下:

+ *
+ * The main means of driving the scheduler and thus entering this function are:
+ *
+ *   1\. Explicit blocking: mutex, semaphore, waitqueue, etc.
+ *
+ *   2\. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
+ *      paths. For example, see arch/x86/entry_64.S.
+ *
+ *      To drive preemption between tasks, the scheduler sets the flag in timer
+ *      interrupt handler scheduler_tick().
+ *
+ *   3\. Wakeups don't really cause entry into schedule(). They add a
+ *      task to the run-queue and that's it.
+ *
+ *      Now, if the new task added to the run-queue preempts the current
+ *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
+ *      called on the nearest possible occasion:
+ *
+ *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
+ *
+ *         - in syscall or exception context, at the next outmost
+ *           preempt_enable(). (this might be as soon as the wake_up()'s
+ *           spin_unlock()!)
+ *
+ *         - in IRQ context, return from interrupt-handler to
+ *           preemptible context
+ *
+ *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
+ *         then at the next:
+ *
+ *          - cond_resched() call
+ *          - explicit schedule() call
+ *          - return from syscall or exception to user-space
+ *          - return from interrupt-handler to user-space